Many pentagons in triple systems
Dhruv Mubayi, Jozsef Solymosi · 2025
Read Many pentagons in triple systems by Dhruv Mubayi, Jozsef Solymosi (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-2501-15861.txt.
Introduction
Dhruv Mubayi and Jozsef Solymosi prove that dense systems of triples always contain many five-cycles, in a 2025 paper. A linear triple system is a set of points with chosen triples, no two triples sharing more than one point. A pentagon is a ring of five triples linked in a cycle. Earlier work by Jiang and Yepremyan had asked how many pentagons such a system must hold, with no solid answer.
The authors show that once the number of triples passes a threshold, pentagons number at least a fixed power ratio of triples to points. They also prove a broader result: graphs far from being triangle-free hold many odd cycles of every length, improving the best bound known. The work yields geometry theorems about point sets rich in copies of one triangle shape, plus a construction showing how far one exponent there can be pushed.
Catalog record
| CREATOR | Dhruv Mubayi, Jozsef Solymosi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-15861
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Many pentagons in triple systems Dhruv Mubayi, Jozsef Solymosi Abstract We prove that every n n vertex linear triple system with m m edges has at least m 6 / n 7 m^{6}/n^{7} copies of a pentagon, provided m > 100 n 3 / 2 m>100\,n^{3/2} . This provides the first nontrivial bound for a question posed by Jiang and Yepremyan. More generally, for each ℓ ≥ 2 \ell\geq 2 , we prove that there is a constant c c such that if an n n -vertex graph is ε \varepsilon -far from being triangle-free, with ε ≫ n − 1 / 3 ℓ \varepsilon\gg n^{-1/3\ell} , then it has at least c ε 3 ℓ n 2 ℓ + 1 c\,\varepsilon^{3\ell}n^{2\ell+1} copies of C 2 ℓ + 1 C_{2\ell+1} . This improves the previous best bound of c ε 4 ℓ + 2 n 2 ℓ + 1 c\,\varepsilon^{4\ell+2}n^{2\ell+1} due to Gishboliner, Shapira and Wigderson. Our result also yields some geometric theorems, including the following. For n n large, every n n -point set in the plane with at least 60 n 11 / 6 60\,n^{11/6} triangles similar to a given triangle T T , contains two triangles sharing a special point, called the harmonic point. In the other direction, we give a construction showing that the exponent 11 / 6 ≈ 1.83 11/6\approx 1.83 cannot be reduced to anything smaller than ≈ 1.726 \approx 1.726 . 1 Introduction We consider the supersaturation problem for odd cycles in linear 3-graphs (triple systems) and show some applications of this question. A (loose or linear) cycle C_{k} is the 3-graph containing k distinct vertices v_{1},\ldots,v_{k} and k distinct edges e_{1},\ldots,e_{k} such that e_{i} is obtained by enlarging \{v_{i},v_{i+1}\} by a new vertex w_{i} such that w_{1},\ldots,w_{k} are all distinct and distinct from all the v_{j} s. In other words (taking indices modulo k ), V(C_{k})=\{v_{1},\ldots,v_{k},w_{1},\ldots,w_{k}\}\qquad\hbox{ and }\qquad E(C_{k})=\{v_{i}v_{i+1}w_{i}:i=1\ldots,k\}. A triple system is linear if every pair of vertices lies in at most one edge. A natural extremal problem is to determine the Turán number \mathrm{ex}_{L}(n,C_{k}) , defined as the maximum number of edges in an n -vertex linear triple system that contains no copy of C_{k} as a (not necessarily induced) subgraph. We are especially interested in the case when k=2\ell+1 is odd. The case of C_{3} is special as determining \mathrm{ex}_{L}(n,C_{3}) is, apart from constant multiplicative factors, equivalent to the well-known (6,3) -problem of Brown-Erdős-Sós. Here, famous results of Behrend [ 2 ] and Ruzsa-Szemerédi [ 16 ] show that \mathrm{ex}_{L}(n,C_{3})=n^{2-o(1)} with the o(1) term being a function of intense study over the years. We are mainly concerned with the case of C_{5} , henceforth called the pentagon. The first author, Kostochka, and Verstraëte proved that \mathrm{ex}_{L}(n,C_{5})=\Omega(n^{3/2}) while writing the paper [ 13 ] in 2013. Theorem 1.2 in Collier-Cartaino, Graber, Jiang [ 4 ] refers to this result. This was later published in [ 6 ] by Ergemlidze, Győri, Methuku. More generally, the upper bound \mathrm{ex}_{L}(n,C_{2\ell+1})=O(n^{1+1/\ell}) was proved in [ 4 ] ; no corresponding lower bound is known for any \ell>2 . Many extremal problems exhibit the property that when the underlying (typically large) discrete object is dense enough to contain a given forbidden subobject, it contains many of them. In our context, this means that n -vertex triple systems with m edges contain many pentagons when m is much larger than n^{3/2} . Indeed, our main result quantifies this dependence. Theorem 1.1 . Let n>10 and let H be an n -vertex linear triple system with m>100\,n^{3/2} edges. Then the number of copies of C_{5} in H is at least m^{6}/n^{7} . Sidorenko’s conjecture states that the homomorphism density of a graph G in a graph W is at least the edge density of W raised to the power e , where e is the number of edges in G . This is known to be false for some hypergraphs, but deciding if it is true for the pentagon when the underlying triple system is linear seems interesting. Namely, can the quantity m^{6}/n^{7} in Theorem 1.1 be improved to m^{5}/n^{5} , which, if true, would be sharp in order of magnitude as shown by random triple systems? This problem was posed by Jiang and Yepremyan [ 10 ] . We believed that no such improvement is possible, and in fact, after our preprint was made public, this was shown to be true by Methuku (personal communication), who gave a construction where the number of C_{5} is O((m^{5}/n^{5})^{1-\varepsilon}) . Further, we conjecture that the truth is \Theta(m^{6}/n^{7}) , but this remains open. The following result provides some motivation for our conjecture. Throughout this paper, we use standard asymptotic notation. Proposition 1.2 . Suppose that for all n there exists a linear triple system H on n vertices and m=\Theta(n^{3/2}) edges, with maximum degree O(n^{1/2}) , at most O(n^{3/2}) copies of C_{3} , and at most O(n^{2}) copies of C_{k} for k=4,5 . Then, the bound m^{6}/n^{7} in Theorem 1.1 is tight in order of magnitude. We provide a construction of a linear H as in Proposition 1.2 with no copies of C_{3} and C_{5} , but the number of copies of C_{4} is \Omega(n^{5/2}) . We remark that a linear 3-graph H as in Proposition 1.2 with no of copies of C_{k} for each 3\leq k\leq 5 does not exist, as it was shown by Conlon, Fox, Sudakov, and Zhao [ 3 ] that any such H has o(n^{3/2}) edges. A natural generalization of Theorem 1.1 has an application to a problem concerning quantitative aspects of removal lemmas in graphs, which are, in turn, connected to questions about property testing. Say that an n -vertex graph G is \varepsilon -far from being triangle-free if the minimum number of edges required to be removed from G to make G triangle-free is at least \varepsilon n^{2} . Gishboliner, Shapira and Wigderson [ 9 ] proved that there is a constant c such that if \varepsilon>0 and n is sufficiently large in terms of \varepsilon , and G is \varepsilon -far from being triangle-free, then G has at least c\,\varepsilon^{4\ell+2}n^{2\ell+1} copies of C_{2\ell+1} . We improve this as follows. We write a\gg b to denote that there is a sufficiently large constant C>0 such that a>C\,b . Theorem 1.3 . Fix \ell\geq 2 . There is a constant c such that if an n -vertex graph G is \varepsilon -far from being triangle-free, with \varepsilon\gg n^{-1/3\ell} , then G has at least c\,\varepsilon^{3\ell}n^{2\ell+1} copies of C_{2\ell+1} . The lower bound requirement on \varepsilon in Theorem 1.3 can be weakened, but we make no attempt to optimize its value (the optimal value would be n^{-1+1/\ell} ). We note that the exponent 3\ell of \varepsilon cannot be improved to anything smaller than 2\ell+1 as shown by random graphs. This paper summarizes unpublished works by the authors previously presented in seminars and conferences like in [ 17 , 18 ] . The following related results were published independently by others: a proof of a slight weakening of Theorem 1.1 , and Theorem 1.3 for \ell=2 was published recently in [ 8 ] ,