Counting and packing Hamilton -cycles in dense hypergraphs

DOI10.4310/JOC.2016.V7.N1.A6zbMATH Open1331.05160arXiv1406.3091OpenAlexW2962739781MaRDI QIDQ5963389FDOQ5963389

Asaf Ferber, Michael Krivelevich, Benny Sudakov

Publication date: 19 February 2016

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider problems about packing and counting Hamilton $ell$-cycles in hypergraphs of large minimum degree. Given a hypergraph $mathcalH$, for a $d$-subset $AsubseteqV(mathcalH)$, we denote by $d_{mathcalH}(A)$ the number of distinct emph{edges} $finE(mathcalH)$ for which $Asubseteqf$, and set $delt{a}_d(mathcalH)$ to be the minimum $d_{mathcalH}(A)$ over all $AsubseteqV(mathcalH)$ of size $d$. We show that if a $k$-uniform hypergraph on $n$ vertices $mathcalH$ satisfies $delt{a}_{k-1}(mathcalH)geqalphan$ for some $alpha>1/2$, then for every $ell<k/2$ $mathcalH$ contains $(1-o(1){)}^{n}cdotn!cdotleft(fracalphaell!(k-2ell)!ight{)}^{fracnk-ell}$ Hamilton $ell$-cycles. The exponent above is easily seen to be optimal. In addition, we show that if $delt{a}_{k-1}(mathcalH)geqalphan$ for $alpha>1/2$, then $mathcalH$ contains $f(alpha)n$ edge-disjoint Hamilton $ell$-cycles for an explicit function $f(alpha)>0$. For the case where every $(k-1)$-tuple $XsubsetV(mathcalH)$ satisfies $d_{mathcalH}(X)in(alphapmo(1))n$, we show that $mathcalH$ contains edge-disjoint Haimlton $ell$-cycles which cover all but $oleft(|E(mathcalH)|ight)$ edges of $mathcalH$. As a tool we prove the following result which might be of independent interest: For a bipartite graph $G$ with both parts of size $n$, with minimum degree at least $deltan$, where $delta>1/2$, and for $p=omega(logn/n)$ the following holds. If $G$ contains an $r$-factor for $r=Theta(n)$, then by retaining edges of $G$ with probability $p$ independently at random, w.h.p the resulting graph contains a $(1-o(1))rp$-factor.

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

Recommendations

• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Packing tight Hamilton cycles in uniform hypergraphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• On Hamiltonian cycles in hypergraphs with dense link graphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs

zbMATH Keywords

\(k\)-uniform hypergraph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65)

Cited In (9)

• Number of 1-factorizations of regular high-degree graphs
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Property (T) in density-type models of random groups
• Decomposing hypergraphs into cycle factors
• Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Counting Hamilton cycles in Dirac hypergraphs

This page was built for publication: Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs

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