A threshold result for loose Hamiltonicity in random regular uniform hypergraphs

DOI10.1016/J.JCTB.2019.11.001MaRDI QIDQ1985454zbMATH OpenOpenAlexFDO

Authors Daniel Altman, Catherine Greenhill, M. I. Isaev, Reshma Ramadurai

Publication date 7 April 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclehypergraphrandom hypergraphthreshold

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $mathcalG(n,r,s)$ denote a uniformly random $r$-regular $s$-uniform hypergraph on $n$ vertices, where $s$ is a fixed constant and $r=r(n)$ may grow with $n$. An $ell$-overlapping Hamilton cycle is a Hamilton cycle in which successive edges overlap in precisely $ell$ vertices, and 1-overlapping Hamilton cycles are called loose Hamilton cycles. When $r,sgeq3$ are fixed integers, we establish a threshold result for the property of containing a loose Hamilton cycle. This partially verifies a conjecture of Dudek, Frieze, Rucinski and Sileikis (2015). In this setting, we also find the asymptotic distribution of the number of loose Hamilton cycles in $mathcalG(n,r,s)$. Finally we prove that for $ell=2,ldots,s-1$ and for $r$ growing moderately as $noinfty$, the probability that $mathcalG(n,r,s)$ has a $ell$-overlapping Hamilton cycle tends to zero.

Recommendations

• Loose Hamilton cycles in random uniform hypergraphs
• Regular hypergraphs: asymptotic counting and loose Hamilton cycles
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Loose Hamilton Cycles in Regular Hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs

Cites work

• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Approximate counting of regular hypergraphs
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Complex martingales and asymptotic enumeration
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 863476 (Why is no real title available?)
• Loose Hamilton Cycles in Regular Hypergraphs
• On the number of perfect matchings in random lifts
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Tight Hamilton cycles in random hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs

Cited in

(6)

• scientific article; zbMATH DE number 5630514 (Why is no real title available?)
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Regular hypergraphs: asymptotic counting and loose Hamilton cycles
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Spanning trees in random regular uniform hypergraphs
• Hamiltonicity of graphs perturbed by a random regular graph

This page was built for publication: A threshold result for loose Hamiltonicity in random regular uniform hypergraphs

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