×

An approximate Dirac-type theorem for \(k\)-uniform hypergraphs. (English) Zbl 1164.05051

A \(k\)-uniform hypergraph is said to be hamiltonian if for some cyclic ordering of its vertex set, every \(k\) consecutive vertices form an edge. In this paper an approximate version for uniform hypergraphs of an analogous result to Dirac’s theorem for graphs is proved: For every \(k\geq 3\) and \(\gamma>0\), and for all \(n\) large enough, a sufficient condition for an \(n\)-vertex \(k\)-uniform hypergraph to be hamiltonian is that each \((k-1)\)-element set of vertices is contained in at least \((1/2+\gamma)n\) edges. This result is related to the following conjecture by Gy. Y. Katona and H. A. Kierstead [J. Graph Theory 30, 205-212 (1999; Zbl 0924.05050)]: Let \(H\) be a \(k\)-graph with \(n\geq k+1\) vertices. If every \((k-1)\)-element set of vertices is contained in at least \(\lfloor n/2\rfloor\) edges, then \(H\) is hamiltonian.

MSC:

05C65 Hypergraphs
05C45 Eulerian and Hamiltonian graphs
05D05 Extremal set theory

Citations:

Zbl 0924.05050
Full Text: DOI

References:

[1] N. Alon and J. Spencer: The Probabilistic Method, Second Edition, John Wiley and Sons, New York (2000). · Zbl 0996.05001
[2] J. C. Bermond, et al.: Hypergraphes hamiltoniens, Prob. Comb. Theorie Graph Orsay 260 (1976), 39–43.
[3] G. A. Dirac: Some theorems of abstract graphs, Proc. London Math. Soc. 3 (1952), 69–81. · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69
[4] P. Frankl and V. Rödl: Extremal problems on set systems, Random Struct. Algorithms 20(2) (2002), 131–164. · Zbl 0995.05141 · doi:10.1002/rsa.10017
[5] P. Haxell, T. Łuczak, Y. Peng, V. Rödl, A. Ruciński, M. Simonovits and J. Skokan: The Ramsey number for hypergraph cycles I, J. Combin. Theory Series A 113 (2006), 67–83. · Zbl 1089.05053 · doi:10.1016/j.jcta.2005.02.005
[6] S. Janson, T. Łuczak and A. Ruciński: Random Graphs, John Wiley and Sons, New York (2000). · Zbl 0968.05003
[7] Gy. Y. Katona and H. A. Kierstead: Hamiltonian chains in hypergraphs, J. Graph Theory 30(3) (1999), 205–212. · Zbl 0924.05050 · doi:10.1002/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O
[8] D. Kühn and D. Osthus: Loose Hamilton cycles in 3-uniform hypergraphs of large minimum degree, J. Combin. Theory Series B 96 (2006), 767–821. · Zbl 1109.05065 · doi:10.1016/j.jctb.2006.02.004
[9] V. Rödl, A. Ruciński and E. Szemerédi: A Dirac-type theorem for 3-uniform hypergraphs, Combinatorics, Probability and Computing 15(1–2) (2006), 229–251. · Zbl 1082.05057 · doi:10.1017/S0963548305007042
[10] E. Szemerédi: Regular partitions of graphs, in: Problemes combinatoires et theorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 399–401, Colloq. Internat. CNRS, 260, CNRS, Paris (1978).
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.