Hamilton cycles in sparse robustly expanding digraphs

被引:0
|
作者
Lo, Allan [1 ]
Patel, Viresh [2 ]
机构
[1] Univ Birmingham, Sch Math, Birmingham, W Midlands, England
[2] Univ Amsterdam, Korteweg Vries Inst Wiskunde, NL-1090 GE Amsterdam, Netherlands
基金
欧洲研究理事会;
关键词
ORIENTED GRAPHS; REGULAR EXPANDERS; DECOMPOSITIONS; TOURNAMENTS;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 Szemeredi'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 sparser robustly expanding digraphs.
引用
收藏
页数:21
相关论文
共 20 条
  • [1] Hamilton cycles in dense regular digraphs and oriented graphs
    Lo, Allan
    Patel, Viresh
    Yildiz, Mehmet Akif
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 164 : 119 - 160
  • [2] Optimal covers with Hamilton cycles in random graphs
    Hefetz, Dan
    Kuehn, Daniela
    Lapinskas, John
    Osthus, Deryk
    COMBINATORICA, 2014, 34 (05) : 573 - 596
  • [3] γ-CYCLES IN ARC-COLORED DIGRAPHS
    Galeana-Sanchez, Hortensia
    Gaytan-Gomez, Guadalupe
    Rojas-Monroy, Rocio
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) : 103 - 116
  • [4] Hamilton cycles in pseudorandom graphs
    Glock, Stefan
    Correia, David Munha
    Sudakov, Benny
    ADVANCES IN MATHEMATICS, 2024, 458
  • [5] Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
    Kuehn, Daniela
    Lapinskas, John
    Osthus, Deryk
    Patel, Viresh
    PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 2014, 109 : 733 - 762
  • [6] Packing, counting and covering Hamilton cycles in random directed graphs
    Ferber, Asaf
    Kronenberg, Gal
    Long, Eoin
    ISRAEL JOURNAL OF MATHEMATICS, 2017, 220 (01) : 57 - 87
  • [7] Counting and packing Hamilton cycles in dense graphs and oriented graphs
    Ferber, Asaf
    Krivelevich, Michael
    Sudakov, Benny
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 196 - 220
  • [8] HAMILTON CYCLES IN BIDIRECTED COMPLETE GRAPHS
    Busch, Arthur
    Mutar, Mohammed A.
    Slilaty, Daniel
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2022, 17 (02) : 137 - 149
  • [9] A survey on Hamilton cycles in directed graphs
    Kuehn, Daniela
    Osthus, Deryk
    EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (05) : 750 - 766
  • [10] Cycles with two blocks in k-chromatic digraphs
    Kim, Ringi
    Kim, Seog-Jin
    Ma, Jie
    Park, Boram
    JOURNAL OF GRAPH THEORY, 2018, 88 (04) : 592 - 605