{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,1]],"date-time":"2022-11-01T04:51:23Z","timestamp":1667278283993},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A diregular bipartite tournament is a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in- and out-degree. In 1981 Jackson showed that a diregular bipartite tournament contains a Hamilton cycle, and conjectured that in fact its edge set can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: for every<jats:italic>\u03b5<\/jats:italic>\u00a0&gt;\u00a00 there exists<jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub>such that every diregular bipartite tournament on 2<jats:italic>n<\/jats:italic>\u2265<jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub>vertices contains a collection of (1\/2\u2013<jats:italic>\u03b5<\/jats:italic>)<jats:italic>n<\/jats:italic>cycles of length at least (2\u2013<jats:italic>\u03b5<\/jats:italic>)<jats:italic>n<\/jats:italic>. Increasing the degree by a small proportion allows us to prove the existence of many Hamilton cycles: for every<jats:italic>c<\/jats:italic>\u00a0&gt;\u00a01\/2 and<jats:italic>\u03b5<\/jats:italic>\u00a0&gt;\u00a00 there exists<jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub>such that every<jats:italic>cn<\/jats:italic>-regular bipartite digraph on 2<jats:italic>n<\/jats:italic>\u2265<jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub>vertices contains (1\u2212<jats:italic>\u03b5<\/jats:italic>)<jats:italic>cn<\/jats:italic>edge-disjoint Hamilton cycles.<\/jats:p>","DOI":"10.1017\/s0963548320000152","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T10:28:41Z","timestamp":1593512921000},"page":"886-899","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["An approximate version of Jackson\u2019s conjecture"],"prefix":"10.1017","volume":"29","author":[{"given":"Anita","family":"Liebenau","sequence":"first","affiliation":[]},{"given":"Yanitsa","family":"Pehova","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"key":"S0963548320000152_ref18","unstructured":"[18] Nash-Williams, C. St J. A. (1970) Hamiltonian lines in graphs whose vertices have sufficiently large valencies. In Combinatorial Theory and its Applications III (Proc. Colloq., Balatonf\u00fcred, 1969), pp. 813\u2013819, North-Holland."},{"key":"S0963548320000152_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00017-4"},{"key":"S0963548320000152_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000468"},{"key":"S0963548320000152_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2013.01.005"},{"key":"S0963548320000152_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.10.006"},{"key":"S0963548320000152_ref4","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/1154"},{"key":"S0963548320000152_ref1","volume-title":"The Probabilistic Method","author":"Alon","year":"2016"},{"key":"S0963548320000152_ref16","unstructured":"[16] K\u00fchn, D. , Osthus, D. and Treglown, A. (2010) Hamilton decompositions of regular tournaments. Proc. London Math. Soc. 101 303\u2013335."},{"key":"S0963548320000152_ref10","first-page":"5","article-title":"On the 1-factors and Hamilton circuits of complete n-colorable graphs","volume":"19","author":"Hetyei","year":"1975","journal-title":"Acta Acad. Paedagog. Civitate Pecs Ser. 6 Math. Phys. Chem. Tech"},{"key":"S0963548320000152_ref5","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548320000152_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90020-0"},{"key":"S0963548320000152_ref3","first-page":"9","volume-title":"Series","author":"Alspach","year":"1990"},{"key":"S0963548320000152_ref8","first-page":"495","article-title":"Une condition suffisante d\u2019existence d\u2019un circuit Hamiltonien","volume":"251","author":"Ghouila-Houri","year":"1960","journal-title":"CR Acad. Sci. Paris"},{"key":"S0963548320000152_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90039-X"},{"key":"S0963548320000152_ref2","first-page":"7","article-title":"The wonderful Walecki construction","volume":"52","author":"Alspach","year":"2008","journal-title":"Bull. Inst. Combin. Appl 52"},{"key":"S0963548320000152_ref21","doi-asserted-by":"publisher","DOI":"10.2307\/2308928"},{"key":"S0963548320000152_ref7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316339831","volume-title":"Introduction to Random Graphs","author":"Frieze","year":"2015"},{"key":"S0963548320000152_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050204"},{"key":"S0963548320000152_ref19","first-page":"157","volume-title":"Studies in Pure Mathematics: Papers Presented to Richard Rado","author":"Nash-Williams","year":"1971"},{"key":"S0963548320000152_ref13","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdn065"},{"key":"S0963548320000152_ref6","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx085"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T05:27:17Z","timestamp":1667194037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000152\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,30]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S0963548320000152"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000152","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}