Sabotaging Mantel's Theorem
One of the earliest results in extremal graph theory, Mantel's theorem, states that the maximum number of edges in a triangle-free graph $G$ on $n$ vertices is $\lfloor n^2/4 \rfloor$. We investigate how this extremal bound is affected when $G$ is additionally required to contain a prescribed graph $H$ as a subgraph. We establish general upper and lower bounds for this problem, which are tight in the exponent for random triangle-free graphs and graphs generated by the triangle-free process, when the size of $H$ lies within certain ranges.
Authors
- Natalie Behague (ORCID: https://orcid.org/0000-0001-6616-1606)
- Debsoumya Chakraborti
- Xizhi Liu
Institutions
- University of Science and Technology of China (CN)
- University of Warwick (GB)
- University College London (GB)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2026-02-26
- DOI
- https://doi.org/10.37236/14324
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- European Commission
- National Natural Science Foundation of China