Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity

DOI10.1016/J.JCTB.2016.09.003zbMATH Open1350.05110arXiv1508.06677OpenAlexW3098804474WikidataQ57401402 ScholiaQ57401402MaRDI QIDQ345119FDOQ345119

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

Publication date: 25 November 2016

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

Abstract: We establish an inclusion relation between two uniform models of random $k$-graphs (for constant $kge2$) on $n$ labeled vertices: $mathbb{G}^{(k)}(n,m)$, the random $k$-graph with $m$ edges, and $mathbb{R}^{(k)}(n,d)$, the random $d$-regular $k$-graph. We show that if $nlognllmll{n}^k$ we can choose $d=d(n)simkm/n$ and couple $mathbb{G}^{(k)}(n,m)$ and $mathbb{R}^{(k)}(n,d)$ so that the latter contains the former with probability tending to one as $noinfty$. This extends an earlier result of Kim and Vu about "sandwiching random graphs". In view of known threshold theorems on the existence of different types of Hamilton cycles in $mathbb{G}^{(k)}(n,m)$, our result allows us to find conditions under which $mathbb{R}^{(k)}(n,d)$ is Hamiltonian. In particular, for $kge3$ we conclude that if $n^{k-2}lldll{n}^{k-1}$, then a.a.s. $mathbb{R}^{(k)}(n,d)$ contains a tight Hamilton cycle.

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

Recommendations

• Loose Hamilton Cycles in Regular Hypergraphs
• Regular hypergraphs: asymptotic counting and loose Hamilton cycles
• Tight Hamilton cycles in random uniform hypergraphs
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Tight Hamilton cycles in random hypergraphs

zbMATH Keywords

Hamilton cyclerandom regular graphrandom hypergraphmonotone graph property

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• Random graphs.
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Random regular graphs of high degree
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• It's a small world for random surfers
• Almost all regular graphs are hamiltonian
• Tight Hamilton cycles in random uniform hypergraphs
• Tight Hamilton cycles in random hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Generating Random Regular Graphs Quickly
• Sandwiching random graphs: universality between random graph models
• Introduction to Random Graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Title not available (Why is that?)
• Loose Hamilton Cycles in Regular Hypergraphs
• Generating random regular graphs

Cited In (10)

• A threshold result for loose Hamiltonicity in random regular uniform hypergraphs
• Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
• Sandwiching biregular random graphs
• On some multicolor Ramsey properties of random graphs
• The number of perfect matchings, and the nesting properties, of random regular graphs
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Rainbow connection of random regular graphs
• Sandwiching dense random regular graphs between binomial random graphs
• The average distance and the diameter of dense random regular graphs
• Edge correlations in Random regular hypergraphs and applications to subgraph testing

This page was built for publication: Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity

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