Cycles with many chords
OPEN ACCESS
Loading...
Author / Producer
Date
2024-08
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 $ 2{n}^{3/2} $ edges contains such a cycle. We significantly improve this old bound by showing that $ \Omega \left(n\kern0.2em {\log}^8n\right) $ 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
65 (1)
Pages / Article No.
3 - 16
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
chords; cycles; random walks
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)