Open Collections

How redundant is Mantelâ s Theorem

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: Freie Universität Berlin

2020-09-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75865

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/