|国家预印本平台
首页|Sabotage the Mantel Theorem

Sabotage the Mantel Theorem

Sabotage the Mantel Theorem

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论