An improved hypergraph Mantel’s Theorem
Daniel Iľkovič, Jun Yan · 2025
Read An improved hypergraph Mantel’s Theorem by Daniel Iľkovič, Jun Yan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-14474.txt.
Introduction
Daniel Ilkovic and Jun Yan improve a hypergraph version of Mantel's theorem, in work from 2025. Mantel's classic result caps the edges in a triangle free graph. The hypergraph version caps a family of triangle like shapes in uniform hypergraphs, where each edge holds the same number of points.
Recent work set the density cap for a whole family of such shapes and found the exact cap for large cases. The unique best shape was the balanced complete split hypergraph. Ilkovic and Yan show both results still hold for a much smaller subfamily. Their proof builds on the entropy method used before. A smaller banned family makes the theorem stronger.
Catalog record
| CREATOR | Daniel Iľkovič, Jun Yan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-14474
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An improved hypergraph Mantel’s Theorem Daniel Iľkovič, Jun Yan Abstract In a recent paper [ 1 ] , Chao and Yu used an entropy method to show that the Turán density of a certain family ℱ \mathcal{F} of ⌊ r / 2 ⌋ \left\lfloor r/2\right\rfloor triangle-like r r -uniform hypergraphs is r ! / r r r!/r^{r} . Later, Liu [ 8 ] determined for large n n the exact Turán number ex ( n , ℱ ) \ex(n,\mathcal{F}) of this family, and showed that the unique extremal graph is the balanced complete r r -partite r r -uniform hypergraph. These two results together can be viewed as a hypergraph version of Mantel’s Theorem. In this paper, building on their methods, we improve both of these results by showing that they still hold with a subfamily ℱ ′ ⊂ ℱ \mathcal{F}^{\prime}\subset\mathcal{F} of size ⌈ r / e ⌉ \left\lceil r/e\right\rceil in place of ℱ \mathcal{F} . 1 Introduction Given a family of r -uniform hypergraphs \mathcal{F} , an r -uniform hypergraph H is said to be \mathcal{F} -free if H does not contain any F\in\mathcal{F} as a subgraph. The famous Turán problem studies the following two quantities. • The Turán number \ex(n,\mathcal{F}) , which is the maximum number of edges in an \mathcal{F} -free r -uniform hypergraph on n vertices. • The Turán density \pi(\mathcal{F}) , which is defined to be \lim_{n\to\infty}\ex(n,\mathcal{F})/\binom{n}{r} . One can show using an averaging argument that \ex(n,\mathcal{F})/\binom{n}{r} is decreasing in n , which implies that the limit above always exists, so \pi(\mathcal{F}) is well-defined. In the case when r=2 , or equivalently on graphs, the Turán problem is well-understood. For \chi\geq 2 , define the Turán graph T(n,\chi) to be the balanced complete \chi -partite graph on n vertices. The earliest and most basic result in this area is Mantel’s Theorem, which states that for the triangle graph K_{3} , \pi(K_{3})=1/2 and \ex(n,K_{3})=\left\lfloor n^{2}/4\right\rfloor , with T(n,2) being the unique extremal graph. Turán’s Theorem generalises this to all cliques, asserting that \pi(K_{\chi+1})=1-1/\chi and \ex(n,K_{\chi+1})=|E(T(n,\chi))| , with T(n,\chi) being the unique extremal graph. For non-bipartite graphs, the Turán problem is solved asymptotically by the Erdős-Stone Theorem, which states that if \chi(F)=\chi+1\geq 3 , then \pi(F)=1-1/\chi and \ex(n,F)=\left(1-1/\chi+o(1)\right)\binom{n}{2} , with T(n,\chi) being an asymptotic extremal graph. For a general bipartite graph F , the Erdős-Stone theorem shows that \pi(F)=0 and \ex(n,F)=o(n^{2}) , but the exact asymptotic behaviour of \ex(n,F) remains an interesting open problem. In contrast, when r\geq 3 , the hypergraph Turán problem is notoriously difficult with very few known results. As an example, the Turán density is still unknown even for K_{4}^{(3)} , the complete 3 -uniform hypergraph on 4 vertices. For a comprehensive overview on known results in hypergraph Turán problems, we refer the readers to Keevash’s survey [ 7 ] . For every r\geq 2 and every family \mathcal{F} of r -uniform hypergraphs, a general result states that \pi(\mathcal{F})\geq r!/r^{r} if and only if no F\in\mathcal{F} is r -partite, and \pi(F)=0 otherwise. Noting that \pi(K_{3})=1/2=2!/2^{2} , a natural avenue of research is to generalise Mantel’s Theorem to r\geq 3 , by finding a family \mathcal{F} of hypergraph analogues of the triangle that satisfies \pi(\mathcal{F})=r!/r^{r} . This is further motivated by a major open conjecture of Erdős that states that for every r\geq 3 , there exists \varepsilon_{r}>r!/r^{r} such that there is no family \mathcal{F} of r -uniform hypergraphs with \pi(\mathcal{F})\in(r!/r^{r},\varepsilon_{r}) . It is known [ 4 ] that this conjecture is true if and only if there exists a finite family \mathcal{F} of r -uniform hypergraphs with \pi(\mathcal{F})=r!/r^{r} but the blowup density of every F\in\mathcal{F} is larger than r!/r^{r} . As such, a big obstacle towards Erdős’ conjecture is potentially the lack of characterisations, or even examples, of families satisfying \pi(\mathcal{F})=r!/r^{r} . One attempt at generalising Mantel’s Theorem to hypergraphs uses the r -uniform hypergraph \mathbb{T}_{r} with vertex set [2r-1] and edge set (see Figure 1a ) \{\{1,2,\ldots,r\},\{1,2,\ldots,r-1,r+1\},\{r,r+1,\ldots,2r-1\}\}. Let T^{r}(n) be the balanced complete r -partite r -uniform hypergraph on n vertices. Note that \mathbb{T}_{2}=K_{3} and T^{2}(n)=T(n,2) . In [ 2 ] , Frankl and Füredi showed that \pi(\mathbb{T}_{3})=3!/3^{3}=2/9 , and for large n the unique extremal graph is T^{3}(n) . In [ 12 ] , Pikhurko showed that \pi(\mathbb{T}_{4})=4!/4^{4}=3/32 , and for large n the unique extremal graph is T^{4}(n) . However, Frankl and Füredi [ 3 ] showed that \pi(\mathbb{T}_{5})>5!/5^{5} and \pi(\mathbb{T}_{6})>6!/6^{6} , so forbidding \mathbb{T}_{r} itself does not generalise Mantel’s Theorem in general. Determining \pi(\mathbb{T}_{r}) for r\geq 7 remains an open problem. Recently, Chao and Yu found the following generalisation of Mantel’s Theorem in their breakthrough paper [ 1 ] . For every 1\leq i\leq\left\lfloor r/2\right\rfloor , define the (r-i,i) -tent \Delta_{(r-i,i)} to be the r -uniform hypergraph with vertex set [2r-1] and edge set (see Figure 1b ) \{\{1,2,\ldots,r\},\{1,\ldots,i,r+1,\ldots,2r-i-1,2r-1\},\{i+1,\ldots,r,2r-i,\ldots,2r-1\}\}. Note that \Delta_{(r-1,1)}\cong\mathbb{T}_{r} . For 1\leq k\leq\left\lfloor r/2\right\rfloor , let \mathcal{F}_{r,k}=\{\Delta_{(r-i,i)}\mid 1\leq i\leq k\} . (a) \mathbb{T}_{r}\cong\Delta_{(r-1,1)} (b) Tent \Delta_{(5,3)} (c) Partial tent \Delta^{p}_{(5,3)} Figure 1: Examples of triangle-like hypergraphs Theorem 1.1 ( [ 1 , Theorem 1.4] ) . For every r\geq 2 , \pi(\mathcal{F}_{r,\left\lfloor r/2\right\rfloor})=r!/r^{r} . Chao and Yu’s proof of Theorem 1.1 used a novel entropy method, which reduced this Turán density problem to an optimisation problem whose optimal value is an upper bound on \pi(\mathcal{F}_{r,\left\lfloor r/2\right\rfloor}) . They then showed that the optimal value is r!/r^{r} , which combined with the fact that no F\in\mathcal{F}_{r,\left\lfloor r/2\right\rfloor} is r -partite gives the result. Soon after, using a powerful framework developed by Liu, Mubayi and Reiher [ 9 ] and refined by Hou, Liu and Zhao [ 6 ] to prove strong stability results in Turán problems, Liu [ 8 ] proved the following exact version of Theorem 1.1 . Theorem 1.2 ( [ 8 , Theorem 1.2] ) . For every r\geq 2 and every sufficiently large n , \ex(n,\mathcal{F}_{r,\left\lfloor r/2\right\rfloor})=|E(T^{r}(n))| , with T^{r}(n) being the unique extremal construction. In this paper, we improve both Theorem 1.1 and Theorem 1.2 . First, we show that forbidding a smaller family of tents still gives Turán density r!/r^{r} . Note that we start with r=4 as r=3 does not satisfy \left\lceil r/e\right\rceil\leq\left\lfloor r/2\right\rfloor . Theorem 1.3 . For every r\geq 4 , let k=\left\lceil r/e\right\rceil , then \pi(\mathcal{F}_{r,k})=r!/r^{r} . Our proof follows Chao and Yu’s entropy method, with most of the effort devoted to showing that the corresponding optimisation problem obtained using \mathcal{F}_{r,k} instead of \mathcal{F}_{r,\left\lfloor r/2\right\rfloor} still has the same optimal value r!/r^{r} . Moreover, we show that the value k=\left\lceil r/e\right\rceil cannot be improved using this method as the corresponding optimal value can exceed r!/r^{r} if k<\left\lceil r/e\right\rceil . We then proceed as in [ 8 ] to transform this density result into an exact Turán number result. Theorem 1.4 . For every r\geq 4 , let k=\left\lceil r/e\right\rceil , then for every sufficiently large n , \ex(n,\mathcal{F}_{r,k})=|E(T^{r}(n))| , with T^{r}(n) being the unique extremal construction. The rest of this paper is organized as follows. In Section 2 , we introduce the necessary definitions related to Chao and Yu’s entropy method and recall several of their key lemmas from [ 1 ] . This culminates in Section 2.4 where we adapt their method to reduce the