Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-07T05:18:37.207Z Has data issue: false hasContentIssue false
  • English
  • Français

Loose Hamilton Cycles in Regular Hypergraphs

Published online by Cambridge University Press:  24 September 2014

ANDRZEJ DUDEK ,
ALAN FRIEZE ,
ANDRZEJ RUCIŃSKI  and
MATAS ŠILEIKIS
ANDRZEJ DUDEK
Affiliation:
Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA (e-mail: andrzej.dudek@wmich.edu)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: alan@random.math.cmu.edu)
ANDRZEJ RUCIŃSKI
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland (e-mail: rucinski@amu.edu.pl)
MATAS ŠILEIKIS
Affiliation:
Department of Mathematics, Uppsala University, Box 480, 751 06 Uppsala, Sweden (e-mail: matas.sileikis@math.uu.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We establish a relation between two uniform models of random k-graphs (for constant k ⩾ 3) on n labelled vertices: ℍ(k)(n,m), the random k-graph with exactly m edges, and ℍ(k)(n,d), the random d-regular k-graph. By extending the switching technique of McKay and Wormald to k-graphs, we show that, for some range of d = d(n) and a constant c > 0, if m ~ cnd, then one can couple ℍ(k)(n,m) and ℍ(k)(n,d) so that the latter contains the former with probability tending to one as n → ∞. In view of known results on the existence of a loose Hamilton cycle in ℍ(k)(n,m), we conclude that ℍ(k)(n,d) contains a loose Hamilton cycle when d ≫ log n (or just d ⩾ C log n, if k = 3) and d = o(n1/2).

Keywords

Primary 05C6505C80Secondary 05C38
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 1: Honouring the Memory of Philippe Flajolet - Part 3 , January 2015 , pp. 179 - 194
Copyright
Copyright © Cambridge University Press 2014 

References

[1] Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation, Vol. 2 of Oxford Studies in Probability, Oxford Science Publications, The Clarendon Press.Google Scholar
[2] Bender, E. A. and Canfield, E. R. (1978) The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theory Ser. A 24 296–307.Google Scholar
[3] Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin. 1 311–316.Google Scholar
[4] Bollobás, B. (2001) Random Graphs, second edition, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[5] Bollobás, B. and Frieze, A. M. (1985) On matchings and Hamiltonian cycles in random graphs. In Random Graphs '83: Poznań 1983, Vol. 118 of North-Holland Mathematics Studies, North-Holland, pp. 23–46.Google Scholar
[6] Chvátal, V. (1991) Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Alg. 2 11–28.Google Scholar
[7] Cooper, C., Frieze, A. and Reed, B. (2002) Random regular graphs of non-constant degree: Connectivity and Hamiltonicity. Combin. Probab. Comput. 11 249–261.Google Scholar
[8] Dudek, A. and Frieze, A. (2011) Loose Hamilton cycles in random uniform hypergraphs. Electron. J. Combin. 18 #48.CrossRefGoogle Scholar
[9] Dudek, A. and Frieze, A. (2013) Tight Hamilton cycles in random uniform hypergraphs. Random Struct. Alg. 42 374–385.Google Scholar
[10] Dudek, A., Frieze, A., Loh, P.-S. and Speiss, S. (2012) Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs. Electron. J. Combin. 19 #44.CrossRefGoogle Scholar
[11] Dudek, A., Frieze, A., Ruciński, A. and Šileikis, M. (2013) Approximate counting of regular hypergraphs. Inform. Process. Lett. 113 785–788.Google Scholar
[12] Frieze, A. (2010) Loose Hamilton cycles in random 3-uniform hypergraphs. Electron. J. Combin. 17 note 28.CrossRefGoogle Scholar
[13] Janson, S., Łuczak, T. and Rucinski, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.Google Scholar
[14] Kim, J. H. and Vu, V. H. (2004) Sandwiching random graphs: Universality between random graph models. Adv. Math. 188 444–469.CrossRefGoogle Scholar
[15] Knuth, D. E. (1976) Big omicron and big omega and big theta. SIGACT News 8 18–24.Google Scholar
[16] Krivelevich, M., Sudakov, B., Vu, V. H. and Wormald, N. C. (2001) Random regular graphs of high degree. Random Struct. Alg. 18 346–363.Google Scholar
[17] McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Vol. 16 of Algorithms and Combinatorics, Springer, pp. 195–248.Google Scholar
[18] McKay, B. D. and Wormald, N. C. (1990) Uniform generation of random regular graphs of moderate degree. J. Algorithms 11 52–67.Google Scholar
[19] Robinson, R. W. and Wormald, N. C. (1992) Almost all cubic graphs are Hamiltonian. Random Struct. Alg. 3 117–125.Google Scholar
[20] Robinson, R. W. and Wormald, N. C. (1994) Almost all regular graphs are Hamiltonian. Random Struct. Alg. 5 363–374.Google Scholar
[21] Wormald, N. C. (1999) Models of random regular graphs. In Surveys in Combinatorics: Canterbury 1999, Vol. 267 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 239–298.Google Scholar