Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2021 | Accepted Version + Supplemental Material
Journal Article Open

Many disjoint triangles in co-triangle-free graphs

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
Files (178.5 kB)
Name Size Download all
md5:d32e73d0eb4f06f66be1e11e2aa09f85
154.0 kB Preview Download
md5:360d792205f5dbdfa3adc64087c557b2
14.7 kB Preview Download
md5:c78bda49be168fe921686e6d105c5ff5
9.9 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023