Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs. (English) Zbl 1220.05083
Summary: A hamiltonian path (cycle) in an \(n\)-vertex 3-uniform hypergraph is a (cyclic) ordering of the vertices in which every three consecutive vertices form an edge. For large \(n\), we prove an analog of the celebrated Dirac theorem for graphs: there exists \(n_{0}\) such that every \(n\)-vertex 3-uniform hypergraph \(H\), \(n \geqslant n_{0}\), in which each pair of vertices belongs to at least \(n/2 - 1 \left(\lfloor n/2\rfloor\right)\) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.
References:
| [1] | Bermond, J. C., Hypergraphes hamiltoniens, (Probl‘emes combinatoires et théorie des graphes. Probl‘emes combinatoires et théorie des graphes, Orsay, 1976. Probl‘emes combinatoires et théorie des graphes. Probl‘emes combinatoires et théorie des graphes, Orsay, 1976, Colloq. Internat. CNRS, vol. 260 (1978)), 39-43 · Zbl 0413.05041 |
| [2] | E. Buss, H. Hàn, M. Schacht, Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs, submitted for publication.; E. Buss, H. Hàn, M. Schacht, Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs, submitted for publication. · Zbl 1274.05335 |
| [3] | Dirac, G. A., Some theorems of abstract graphs, Proc. Lond. Math. Soc. (3), 69-81 (1952) · Zbl 0047.17001 |
| [4] | Gyárfás, A.; Lehel, J.; Sárközy, G.; Schelp, R., Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs, J. Combin. Theory Ser. B, 98, 342-358 (2008) · Zbl 1140.05028 |
| [5] | Frankl, P.; Rödl, V., Extremal problems on set systems, Random Structures Algorithms, 20, 2, 131-164 (2002) · Zbl 0995.05141 |
| [6] | Hàn, H.; Person, Y.; Schacht, M., On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math., 23, 2, 732-748 (2009) · Zbl 1191.05074 |
| [7] | Hàn, H.; Schacht, M., Dirac-type results for loose Hamilton cycles in uniform hypergraphs, J. Combin. Theory Ser. B, 100, 3, 332-346 (2010) · Zbl 1209.05161 |
| [8] | Haxell, P.; Łuczak, T.; Peng, Y.; Rödl, V.; Ruciński, A.; Simonovits, M.; Skokan, J., The Ramsey number for hypergraph cycles I, J. Combin. Theory Ser. A, 113, 67-83 (2006) · Zbl 1089.05053 |
| [9] | Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs (2000), John Wiley and Sons: John Wiley and Sons New York · Zbl 0968.05003 |
| [10] | Katona, Gy. Y.; Kierstead, H. A., Hamiltonian chains in hypergraphs, J. Graph Theory, 30, 205-212 (1999) · Zbl 0924.05050 |
| [11] | I. Khan, Perfect Matching in 3 uniform hypergraphs with large vertex degree, submitted for publication.; I. Khan, Perfect Matching in 3 uniform hypergraphs with large vertex degree, submitted for publication. |
| [12] | Kővari, P.; Sós, V. P.; Turán, T., On a problem of Zarankiewicz, Colloq. Math., 3, 50-57 (1954) · Zbl 0055.00704 |
| [13] | Kühn, D.; Mycroft, R.; Osthus, D., Hamilton \(l\)-cycles in \(k\)-graphs, J. Combin. Theory Ser. A, 117, 910-927 (2010) · Zbl 1219.05107 |
| [14] | Kühn, D.; Osthus, D., Loose Hamilton cycles in 3-uniform hypergraphs of large minimum degree, J. Combin. Theory Ser. B, 96, 767-821 (2006) · Zbl 1109.05065 |
| [15] | D. Kühn, D. Osthus, A. Treglown, Matchings in 3-uniform hypergraphs, submitted for publication.; D. Kühn, D. Osthus, A. Treglown, Matchings in 3-uniform hypergraphs, submitted for publication. · Zbl 1262.05128 |
| [16] | Levitt, I.; Sárközy, G.; Szemerédi, E., How to avoid using the Regularity Lemma; Pósaʼs Conjecture revisited, Discrete Math., 310, 630-641 (2010) · Zbl 1188.05080 |
| [17] | Ore, O., Hamilton connected graphs, J. Math. Pures Appl. (9), 42, 21-27 (1963) · Zbl 0106.37103 |
| [18] | Pikhurko, O., Perfect matchings and K3 4-tilings in hypergraphs of large codegree, Graphs Combin., 24, 4, 391-404 (2008) · Zbl 1205.05184 |
| [19] | Rödl, V.; Ruciński, A.; Szemerédi, E., A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput., 15, 1-2, 229-251 (2006) · Zbl 1082.05057 |
| [20] | Rödl, V.; Ruciński, A.; Szemerédi, E., An approximate Dirac-type theorem for \(k\)-uniform hypergraphs, Combinatorica, 28, 2, 229-260 (2008) · Zbl 1164.05051 |
| [21] | Rödl, V.; Ruciński, A.; Szemerédi, E., Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A, 116, 3, 613-636 (2009) · Zbl 1214.05130 |
| [22] | Sidorenko, A. F., Inequalities for functional generated by bipartite graphs, Discrete Math. Appl., 3, 3, 50-65 (1991), (in Russian) · Zbl 0737.05061 |
| [23] | Sidorenko, A. F., A correlation inequality for bipartite graphs, Graphs Combin., 9, 201-204 (1993) · Zbl 0777.05096 |
| [24] | Szemerédi, E., Regular partitions of graphs, (Problèmes combinatoires et théorie des graphes. Problèmes combinatoires et théorie des graphes, Orsay, 1976. Problèmes combinatoires et théorie des graphes. Problèmes combinatoires et théorie des graphes, Orsay, 1976, Colloq. Internat. CNRS, vol. 260 (1978), CNRS: CNRS Paris), 399-401 · Zbl 0413.05055 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
