Sabotage the Mantel Theorem
Sabotage the Mantel 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 $\mathbb{P}$ 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 $\mathbb{P}$ lies within certain ranges.
Natalie Behague、Debsoumya Chakraborti、Xizhi Liu
数学
Natalie Behague,Debsoumya Chakraborti,Xizhi Liu.Sabotage the Mantel Theorem[EB/OL].(2025-06-30)[2025-07-16].https://arxiv.org/abs/2506.23794.点此复制
评论