Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments

Alon, 1994, The algorithmic aspects of the regularity lemma, J. Algorithms, 16, 80, 10.1006/jagm.1994.1005 Alon, 2004, Algorithms with large domination ratio, J. Algorithms, 50, 118, 10.1016/j.jalgor.2003.09.003 Alon, 2004, Testing subgraphs in directed graphs, J. Comput. System Sci., 69, 354, 10.1016/j.jcss.2004.04.008 Alspach, 2008, The wonderful Walecki construction, Bull. Inst. Combin. Appl., 52, 7 Alspach, 1990, Decompositions into cycles. I. Hamilton decompositions, 9 Alspach, 2012, Paley graphs have Hamilton decompositions, Discrete Math., 312, 113, 10.1016/j.disc.2011.06.003 Bang-Jensen, 2000 Bermond, 1981, Cycles in digraphs — a survey, J. Graph Theory, 5, 1, 10.1002/jgt.3190050102 Bollobás, 1985, On matchings and Hamiltonian cycles in random graphs, vol. 118, 23 Bondy, 1995, Basic graph theory: paths and circuits, 3 Christofides, 2010, A semi-exact degree condition for Hamilton cycles in digraphs, SIAM J. Discrete Math., 24, 709, 10.1137/090761756 Christofides, 2012, Finding Hamilton cycles in robustly expanding digraphs, J. Graph Algorithms Appl., 16, 337, 10.7155/jgaa.00261 Christofides, 2012, Edge-disjoint Hamilton cycles in graphs, J. Combin. Theory B, 102, 1035, 10.1016/j.jctb.2011.10.005 B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case, Preprint. B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions, Preprint. Frieze, 2005, On packing Hamilton cycles in ε-regular graphs, J. Combin. Theory B, 94, 159, 10.1016/j.jctb.2004.12.003 Frieze, 2008, On two Hamilton cycle problems in random graphs, Israel J. Math., 166, 221, 10.1007/s11856-008-1028-8 Glover, 1997, The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms, J. Oper. Res. Soc., 48, 502, 10.1057/palgrave.jors.2600392 Gutin, 2001, TSP tour domination and Hamilton cycle decompositions of regular graphs, Oper. Res. Lett., 28, 107, 10.1016/S0167-6377(01)00053-0 Häggkvist, 1993, Hamilton cycles in oriented graphs, Combin. Probab. Comput., 2, 25, 10.1017/S0963548300000468 Häggkvist, 1997, Oriented Hamilton cycles in oriented graphs, 339 Jackson, 1981, Long paths and cycles in oriented graphs, J. Graph Theory, 5, 145, 10.1002/jgt.3190050204 Janson, 2000 Keevash, 2009, An exact minimum degree condition for Hamilton cycles in oriented graphs, J. Lond. Math. Soc., 79, 144, 10.1112/jlms/jdn065 Kelly, 2008, A Dirac-type result on Hamilton cycles in oriented graphs, Combin. Probab. Comput., 17, 689, 10.1017/S0963548308009218 F. Knox, D. Kühn, D. Osthus, Edge-disjoint Hamilton cycles in random graphs, Preprint. Komlós, 1997, Blow-up lemma, Combinatorica, 17, 109, 10.1007/BF01196135 Komlós, 1998, An algorithmic version of the blow-up lemma, Random Structures Algorithms, 12, 297, 10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q Kómlos, 1998, Proof of the Seymour conjecture for large graphs, Ann. Combin., 2, 43, 10.1007/BF01626028 Krivelevich, 2012, Optimal packings of Hamilton cycles in sparse random graphs, SIAM J. Discrete Math., 26, 964, 10.1137/110849171 D. Kühn, J. Lapinskas, D. Osthus, Optimal packings of Hamilton cycles in graphs of high minimum degree, Combin. Probab. Comput. (in press). D. Kühn, A. Lo, D. Osthus, A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures I: the two cliques case, Preprint. D. Kühn, A. Lo, D. Osthus, Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case, Preprint. Kühn, 2009, Embedding large subgraphs into dense graphs, vol. 365, 137 D. Kühn, D. Osthus, Hamilton decompositions of regular expanders: applications, Preprint. Kühn, 2012, A survey on Hamilton cycles in directed graphs, European J. Combin., 33, 750, 10.1016/j.ejc.2011.09.030 Kühn, 2010, Hamiltonian degree sequences in digraphs, J. Combin. Theory B, 100, 367, 10.1016/j.jctb.2009.11.004 Kühn, 2010, Hamilton decompositions of regular tournaments, Proc. London Math. Soc., 101, 303, 10.1112/plms/pdp062 Lucas, 1892 Moon, 1968 Nash-Williams, 1971, Hamiltonian arcs and circuits, 197 D. Osthus, K. Staden, Approximate Hamilton decompositions of regular robustly expanding digraphs, Preprint. Perkovic, 1997, Edge coloring regular graphs of high degree, Discrete Math., 165/166, 567, 10.1016/S0012-365X(96)00202-6 Strivastav, 1996, Algorithmic Chernoff–Hoeffding inequalities in integer programming, Random Structures Algorithms, 8, 27, 10.1002/(SICI)1098-2418(199601)8:1<27::AID-RSA2>3.0.CO;2-T Thomassen, 1979, Long cycles in digraphs with constraints on the degrees, vol. 38, 211 Thomassen, 1982, Edge-disjoint Hamiltonian paths and cycles in tournaments, Proc. Lond. Math. Soc., 45, 151, 10.1112/plms/s3-45.1.151 Tillson, 1980, A Hamiltonian decomposition of K2m∗, 2m≥8, J. Combin. Theory B, 29, 68, 10.1016/0095-8956(80)90044-1 Zhang, 1980, Every regular tournament has two arc-disjoint Hamilton cycles, J. Qufu Normal College, 70