Published January 2021
| Accepted Version + Supplemental Material
Journal Article
Open
Many disjoint triangles in co-triangle-free graphs
- Creators
- Tyomkyn, Mykhaylo
Abstract
We prove that any n-vertex graph whose complement is triangle-free contains n²/12 – o(n²) edge-disjoint triangles. This is tight for the disjoint union of two cliques of order n/2. We also prove a corresponding stability theorem, that all large graphs attaining the above bound are close to being bipartite. Our results answer a question of Alon and Linial, and make progress on a conjecture of Erdős.
Additional Information
© The Author(s), 2020. Published by Cambridge University Press. Received 28 January 2020; revised 15 June 2020; first published online 14 August 2020. I would like to thank David Conlon for helpful discussions and Olga Goulko for help with setting up the computer simulation.Attached Files
Accepted Version - 2001.00763.pdf
Supplemental Material - S096354832000036Xsup001.txt
Supplemental Material - S096354832000036Xsup002.txt
Files
2001.00763.pdf
Additional details
- Eprint ID
- 108473
- DOI
- 10.1017/s096354832000036x
- Resolver ID
- CaltechAUTHORS:20210318-085323811
- Created
-
2021-03-19Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field