Abstract: I will talk about novel methods for constructing nearly Hamiltonian cycles in sublinear expanders, along with new techniques for finding sublinear expanders with good regularity properties in general graphs. These methods are of independent interest due to their potential for various applications.
In particular, using these tools, we make significant progress toward a long-standing conjecture of Verstraëte, which asserts that for any graph F, nearly all vertices of every d-regular graph G of order n can be covered by vertex-disjoint F-subdivisions.
Over the past two decades, this conjecture has been proven in certain special cases, including when F is a tree (Kelmans, Mubayi, and Sudakov, 2001) or a cycle (Alon, 2003). In 2005, Kühn and Osthus confirmed the conjecture for dense graphs G, i.e., when d = Ω(n). However, their proof relies on Szemerédi’s regularity lemma and the Blow-up lemma, so it does not extend to sparser graphs. We significantly extend their results by proving Verstraëte’s conjecture for all graphs G with at least polylogarithmic degree.
Among other applications, our methods also show that in every d-regular graph with sufficiently large degree, nearly all vertices can be partitioned into n/(d+1) cycles, thus asymptotically confirming, in a stronger form, a well-known conjecture of Magnant and Martin (2009) for graphs with at least polylogarithmic degree. This is joint work with Shoham Letzter and Benny Sudakov.