Packing and counting arbitrary Hamilton cycles in random digraphs

DOI10.1002/RSA.20796MaRDI QIDQ5381053zbMATH OpenOpenAlexWikidataFDO

Authors Asaf Ferber, Eoin Long

Publication date 7 June 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

digraphsHamilton cyclespacking

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in $calD(n,p)$ for nearly optimal $p$ (up to a $lo{g}^{c}n$ factor). In particular, we show that given $t=(1-o(1))np$ Hamilton cycles $C_1,ldots,C_t$, each of which is oriented arbitrarily, a digraph $DsimcalD(n,p)$ w.h.p. contains edge disjoint copies of $C_1,ldots,C_t$, provided $p=omega(lo{g}^{3}n/n)$. We also show that given an arbitrarily oriented $n$-vertex cycle $C$, a random digraph $DsimcalD(n,p)$ w.h.p. contains $(1pmo(1))n!p^n$ copies of $C$, provided $pgeqlo{g}^{1+o(1)}n/n$.

Recommendations

• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Counting Hamilton cycles in sparse random directed graphs
• Arbitrary orientations of Hamilton cycles in digraphs
• On the existence of Hamilton cycles with a periodic pattern in a random digraph

Cites work

• An algorithm for finding hamilton cycles in random directed graphs
• Arbitrary orientations of Hamilton cycles in digraphs
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Clutter percolation and random graphs
• Concentration Inequalities and Martingale Inequalities: A Survey
• Edge-disjoint Hamilton cycles in random graphs
• Hamilton cycles in highly connected and expanding graphs
• Hamilton decompositions of regular expanders: applications
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On the Number of Hamilton Cycles in Sparse Random Graphs
• On two Hamilton cycle problems in random graphs
• Optimal packings of Hamilton cycles in sparse random graphs
• Oriented hamilton cycles in digraphs
• Packing perfect matchings in random hypergraphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Paths and Cycles in Tournaments
• Robust Hamiltonicity of random directed graphs: extended abstract
• Semi-degree threshold for anti-directed Hamiltonian cycles
• Some Theorems on Abstract Graphs
• The Evolution of Random Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(20)

• Packing arborescences in random digraphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On the existence of Hamilton cycles with a periodic pattern in a random digraph
• Longest cycles in sparse random digraphs
• Packing directed Hamilton cycles online
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• 4-cycles in mixing digraphs
• Hamilton Cycles in Random Lifts of Directed Graphs
• Counting the Number of Hamilton Cycles in Random Digraphs
• Counting Hamilton cycles in sparse random directed graphs
• Packing arborescences in random digraphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Counting orientations of random graphs with no directed k‐cycles
• Spanning cycles in random directed graphs
• On oriented cycles in randomly perturbed digraphs
• Number of subgraphs and their converses in tournaments and new digraph polynomials
• Cycles of every length and orientation in randomly perturbed digraphs (extended abstract)

This page was built for publication: Packing and counting arbitrary Hamilton cycles in random digraphs

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