BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

How redundant is Mantelâ s Theorem Das, Shagnik


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International