Loose Hamilton Cycles in Regular Hypergraphs

DOI10.1017/S0963548314000406MaRDI QIDQ5364219zbMATH OpenWikidataFDO

Authors Andrzej Dudek, Andrzej Ruciński, M. Şileikis, Alan Frieze

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1426

Mathematics Subject Classification ID

Paths and cycles (05C38) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We establish a relation between two uniform models of random $k$-graphs (for constant $kge3$) on $n$ labeled vertices: $H(n,m)$, the random $k$-graph with exactly $m$ edges, and $H(n,d)$, the random $d$-regular $k$-graph. By extending to $k$-graphs the switching technique of McKay and Wormald, we show that, for some range of $d=d(n)$ and a constant $c>0$, if $msimcnd$, then one can couple $H(n,m)$ and $H(n,d)$ so that the latter contains the former with probability tending to one as $noinfty$. In view of known results on the existence of a loose Hamilton cycle in $H(n,m)$, we conclude that $H(n,d)$ contains a loose Hamilton cycle when $logn=o(d)$ (or just $dgeClogn$, if $k=3$) and $d=o(n^{1/2})$.

Recommendations

• Loose Hamilton cycles in hypergraphs
• Regular hypergraphs: asymptotic counting and loose Hamilton cycles
• Loose Hamilton cycles in random uniform hypergraphs
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Hamiltonian cycles in regular graphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• On hypergraphs without loose cycles
• Hamiltonian cycles in regular graphs of moderate degree
• Hamilton cycles in almost-regular 2-connected graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost all cubic graphs are Hamiltonian
• Almost all graphs with 1.44n edges are 3-colorable
• Almost all regular graphs are hamiltonian
• Approximate counting of regular hypergraphs
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• Random graphs.
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Random regular graphs of high degree
• Sandwiching random graphs: universality between random graph models
• The asymptotic number of labeled graphs with given degree sequences
• Tight Hamilton cycles in random uniform hypergraphs
• Uniform generation of random regular graphs of moderate degree

Cited in

(8)

• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• A threshold result for loose Hamiltonicity in random regular uniform hypergraphs
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Loose Hamilton cycles in random uniform hypergraphs
• Regular hypergraphs: asymptotic counting and loose Hamilton cycles
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs

This page was built for publication: Loose Hamilton Cycles in Regular Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364219)