Cycles with many chords

2023/06/15 by Draganić, Nemanja, Methuku, Abhishek, Correia, David Munhá +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2306.09157

Abstract

How many edges in an n-vertex graph will force the existence of a cycle with as many chords as it has vertices? Almost 30 years ago, Chen, Erdős and Staton considered this question and showed that any n-vertex graph with 2n^3/2 edges contains such a cycle. We significantly improve this old bound by showing that Ω(nlog⁸n) edges are enough to guarantee the existence of such a cycle. Our proof exploits a delicate interplay between certain properties of random walks in almost regular expanders. We argue that while the probability that a random walk of certain length in an almost regular expander is self-avoiding is very small, one can still guarantee that it spans many edges (and that it can be closed into a cycle) with large enough probability to ensure that these two events happen simultaneously.

Related

• The extremal number of cycles with all diagonals
• Cycle packing
• A note on the number of edges in a Hamiltonian graph with no repeated cycle length
• Improved bound on the number of cycle sets
• Pancyclicity when each cycle must pass exactly k Hamilton cycle chords