Hamilton cycles in sparse robustly expanding digraphs

MaRDI QIDQ1671669zbMATH OpenFDO

Authors Allan Lo, Viresh Patel

Publication date 7 September 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.04472, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p44

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

digraphHamilton cyclesrobust expanders

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Abstract: The notion of robust expansion has played a central role in the solution of several conjectures involving the packing of Hamilton cycles in graphs and directed graphs. These and other results usually rely on the fact that every robustly expanding (di)graph with suitably large minimum degree contains a Hamilton cycle. Previous proofs of this require Szemer'edi's Regularity Lemma and so this fact can only be applied to dense, sufficiently large robust expanders. We give a proof that does not use the Regularity Lemma and, indeed, we can apply our result to suitable sparse robustly expanding digraphs.

Recommendations

• Approximate Hamilton decompositions of robustly expanding regular digraphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Finding Hamilton cycles in robustly expanding digraphs
• Hamilton decompositions of regular expanders: applications
• A survey on Hamilton cycles in directed graphs

Cites work

• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3508537 (Why is no real title available?)
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A survey on Hamilton cycles in directed graphs
• An approximate version of Sumner's universal tournament conjecture
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Approximate Hamilton decompositions of robustly expanding regular digraphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Embedding spanning bipartite graphs of small bandwidth
• Finding Hamilton cycles in robustly expanding digraphs
• Graph theory
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Hamilton decompositions of regular tournaments
• Hamiltonian circuits in random graphs
• Hamiltonian degree sequences in digraphs
• Proof of the 1-factorization and Hamilton decomposition conjectures
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• Some Theorems on Abstract Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The robust component structure of dense regular graphs and applications
• Triangle Factors in Random Graphs

Cited in

(8)

• Cycle partitions of regular graphs
• Hamilton cycles in dense regular digraphs and oriented graphs
• Approximate Hamilton decompositions of robustly expanding regular digraphs
• Hamilton cycles in sparse locally connected graphs
• Hamilton cycles in quasirandom hypergraphs
• scientific article; zbMATH DE number 5064035 (Why is no real title available?)
• Finding Hamilton cycles in robustly expanding digraphs
• scientific article; zbMATH DE number 672355 (Why is no real title available?)

This page was built for publication: Hamilton cycles in sparse robustly expanding digraphs

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