Nemanja Draganić, Abhishek Methuku, David Munhá Correia, Benny Sudakov

Cycles with many chords

  • Applied Mathematics
  • Computer Graphics and Computer-Aided Design
  • General Mathematics
  • Software
Save to CiteDrive Show PDF

AbstractHow many edges in an ‐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 ‐vertex graph with edges contains such a cycle. We significantly improve this old bound by showing that 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.

Need a simple solution for managing your BibTeX entries? Explore CiteDrive!

  • Web-based, modern reference management
  • Collaborate and share with fellow researchers
  • Integration with Overleaf
  • Comprehensive BibTeX/BibLaTeX support
  • Save articles and websites directly from your browser
  • Search for new articles from a database of tens of millions of references
Try out CiteDrive

More from our Archive