10.14288/1.0394208
Das, Shagnik
How redundant is Mantelâ s Theorem
Banff International Research Station for Mathematical Innovation and Discovery
2020
MovingImage
en
1
One of the all-time combinatorial classics, Mantel's Theorem asserts that if one forbids an $n$-vertex graph $G$ from containing any triangle, then $G$ can have at most $\frac{n^2}{4}$ edges. In this talk, we explore an extension of this theorem suggested by Gil Kalai. Suppose, for some $0 \le m \le \binom{n}{3}$, we can only forbid $m$ of the triangles from appearing in $G$. What choice of the forbidden triangles then minimises the maximum number of edges $G$ can have We determine the threshold at which Mantel's bound still holds, and bound how many extra edges appear when fewer triangles are forbidden. These results also generalise to larger cliques, thereby extending Turán's Theorem along the same lines. This is joint work with Ander Lamaison and Tuan Tran.
University of British Columbia
03rmrcq20