On the quadratic 8-edge case of the Brown–Erdős–Sós problem
Oleg Pikhurko, Shumin Sun · 2025
Read On the quadratic 8-edge case of the Brown–Erdős–Sós problem by Oleg Pikhurko, Shumin Sun (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-2506-01739.txt.
Introduction
Oleg Pikhurko and Shumin Sun work on a long open problem in graph theory that dates to 1973, in a paper from 2025. The problem asks how many links a large network can hold while it avoids a small dense cluster of links. Past work found the growth rate for small cluster sizes, and two authors proved in recent years that the rate settles for each size.
The value of the rate was known only for cluster sizes two through seven. Pikhurko and Sun settle the next case, size eight, for networks where each link joins four or more points. For the case where each link joins three points, they give a lower bound that they believe is exact. The result fills a gap that had stood for more than fifty years.
Catalog record
| CREATOR | Oleg Pikhurko, Shumin Sun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01739
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the quadratic 8-edge case of the Brown–Erdős–Sós problem Oleg Pikhurko, Shumin Sun Abstract Let f ( r ) ( n , s , k ) f^{(r)}(n;s,k) be the maximum number of edges in an n n -vertex r r -uniform hypergraph containing no k k edges on at most s s vertices. Brown, Erdős and Sós conjectured in 1973 that the limit lim n → ∞ n − 2 f ( 3 ) ( n , k + 2 , k ) \lim_{n\rightarrow\infty}n^{-2}f^{(3)}(n;k+2,k) exists for all k k . Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity r ≥ 4 r\geq 4 : the limit lim n → ∞ n − 2 f ( r ) ( n , r k − 2 k + 2 , k ) \lim_{n\rightarrow\infty}n^{-2}f^{(r)}(n;rk-2k+2,k) exists for all r ≥ 3 r\geq 3 and k ≥ 2 k\geq 2 . The value of the limit is currently known for k ∈ { 2 , 3 , 4 , 5 , 6 , 7 } k\in\{2,3,4,5,6,7\} due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we look at the case k = 8 k=8 , determining the value of the limit for each r ≥ 4 r\geq 4 and presenting a lower bound for k = 3 k=3 that we conjecture to be sharp. 1 Introduction For an integer r\geq 2 , an r -uniform hypergraph (in short, r -graph ) H consists of a vertex set V(H) and an edge set E(H)\subseteq\binom{V(H)}{r} , that is, every edge is an r -element subset of V(H) . Given a family \mathcal{F} of r -graphs, the Turán number of \mathcal{F} , denoted by \mathrm{ex}(n;\mathcal{F}) , is defined as the maximum number of edges in an n -vertex r -graph containing no element of \mathcal{F} as a subgraph. In this note, we focus on the family \mathcal{F}^{(r)}(s,k) , consisting of all r -graphs with k edges and at most s vertices. Brown, Erdős and Sós [ 2 ] initiated the systematic investigation of the function f^{(r)}(n;s,k):=\mathrm{ex}(n;\mathcal{F}^{(r)}(s,k)). They showed that \Omega(n^{(rk-s)/(k-1)})=f^{(r)}(n;s,k)=O(n^{\lceil(rk-s)/(k-1)\rceil}). If t:=(rk-s)/(k-1) is an interger, i.e. s=rk-tk+t , then f^{(r)}(n;rk-tk+t,k)=\Theta(n^{t}) . In the sequel, we are mainly interested in the case when t=2 ; thus s=rk-2k+2 and the magnitude of the function is \Theta(n^{2}) . A natural question here is whether the limit \pi(r,k):=\lim_{n\to\infty}n^{-2}f^{(r)}(n;rk-2k+2,k) exists, which was originally conjectured by Brown, Erdős and Sós for r=3 . In their initial paper [ 2 ] , Brown, Erdős and Sós confirmed the conjecture for k=2 by observing that \pi(3,2)=1/6 . Many years later, Glock [ 9 ] solved the case k=3 and showed that \pi(3,3)=1/5 . In a recent work, Glock, Joos, Kim, Kühn, Lichev and Pikhurko [ 6 ] proved the case k=4 by showing that \pi(3,4)=7/36 . Building on their work, Delcourt and Postle [ 3 ] finally resolved the Brown–Erdős–Sós conjecture, namely, \pi(3,k) exists for any k\geq 2 , without determining its value. For more general case \pi(r,k) with uniformity r\geq 4 , the existence of limit was shortly confirmed by Shangguan [ 12 ] , following the approach of Delcourt and Postle (without explicit value). The natural remaining question is to determine the limiting values. Recently, a range of results regarding this direction has been established. Apart from values for r=3 mentioned above, the celebrated work of Rödl [ 11 ] on the existence of approximate Steiner systems (under the condition t=2 ) implies that \pi(r,2)=\frac{1}{r^{2}-r} for every r\geq 4 . Moreover, Glock, Joos, Kim, Kühn, Lichev and Pikhurko [ 6 ] proved that for every r\geq 4 , \pi(r,3)=\frac{1}{r^{2}-r-1}\quad\text{and}\quad\pi(r,4)=\frac{1}{r^{2}-r}. Very recently, Glock, Kim, Lichev, Pikhurko and Sun [ 8 ] obtained the limiting value for k\in\{5,7\} , which is same as k=3 . \pi(r,5)=\pi(r,7)=\frac{1}{r^{2}-r-1}\quad\text{for every $r\geq 3$.} They also resolved the case k=6 , however the value behaves differently when r=3 and r\geq 4 as follows: \pi(3,6)=\frac{61}{330}\quad\text{and\quad$\pi(r,6)=\frac{1}{r^{2}-r}$ for every $r\geq 4$.} Meanwhile, Letzter and Sgueglia [ 10 ] provided the exact value \pi(r,k)=\frac{1}{r^{2}-r} (1) for even integer k and r\geq r_{0}(k) sufficiently large. In their paper, they asked for the smallest r such that ( 1 ) holds. In this note, we determine the limit for k=8 and r\geq 4 as follows. Theorem 1.1 . For every r\geq 4 , we have \pi(r,8)=\frac{1}{r^{2}-r}. Moreover, we provide a lower bound for r=3 , which implies that r=4 is the smallest uniformity such that \pi(r,8)=\frac{1}{r^{2}-r} . Theorem 1.2 . \pi(3,8)\geq\frac{3}{16} . We conjecture that this lower bound is sharp. Conjecture 1.3 . \pi(3,8)=\frac{3}{16} . A connection to generalised Ramsey numbers. In a recent work, Bennett, Cushman and Dudek [ 1 ] found a connection between the Brown–Erdős–Sós function for 4 -graphs and generalised Ramsey numbers, that were introduced by Erdős and Shelah [ 5 ] and were first systematically studied by Erdős and Gyárfás [ 4 ] . For integers p,q such that p\geq 3 and 2\leq q\leq\tbinom{p}{2} , a (p,q) -colouring of K_{n} is a colouring of the edges of K_{n} such that every clique of size p receices at least q colours. The generalised Ramsey number \mathrm{GR}(n,p,q) is the minimum number of colours such that K_{n} has a (p,q) -colouring. Erdős and Gyárfás [ 4 ] proved among other results that for arbitrary p\geq 3 and q_{\rm{quad}}:=\tbinom{p}{2}-\lfloor p/2\rfloor+2 , it holds that \mathrm{GR}(n,p,q_{\rm{quad}})=\Omega(n^{2})\quad\text{and}\quad\mathrm{GR}(n,p,q_{\rm{quad}}-1)=o(n^{2}). Thus q_{\rm{quad}} is the threshold for quadratic growth. Bennett, Cushman and Dudek [ 1 ] showed the following connection between generalised Ramsey numbers and the Brown–Erdős–Sós function. Theorem 1.4 ( [ 1 ] *Theorem 3) . For all even p\geq 6 , we have \lim_{n\to\infty}\frac{\mathrm{GR}(n,p,q_{\rm{quad}})}{n^{2}}=\frac{1}{2}-\pi(4,\frac{p}{2}-1). In particular, the limit on the left exists by [ 12 ] . From Theorem 1.1 , together with Theorem 1.4 , we directly obtain the following asymptotic value of \mathrm{GR}(n,18,146) . Theorem 1.5 . \lim_{n\to\infty}\frac{\mathrm{GR}(n,18,146)}{n^{2}}=\frac{5}{12}.\qed Organisation. The remainder of this paper is organised as follows. We introduce some necessary definitions and notation in Section 2 . Section 3 provides the proofs of lower bounds in Theorem 1.1 and 1.2 . The proof of upper bound in Theorem 1.1 can be found in Section 4 . 2 Preliminaries Throughout the note, we shall use the following notation and terminology. For two integers m,n , we denote by [n] the set \{1,\dots,n\} and by [m,n] the set [n]\setminus[m-1]=\{m,\dots,n\} . For a set X , we define {X\choose m}:=\{Y\subseteq X:|Y|=m\} to be the family of all m -subsets of X . For simplicity, we often denote the unordered pair \{x,y\} (resp. triple \{x,y,z\} ) by xy (resp. xyz ). We will often identify an r -graph G with its edge set. In particular, if we specify only the edge set E(G) then the vertex set is assumed to be the union of these edges, that is, V(G)=\bigcup_{X\in E(G)}X . We let |G| be the number of edges of G and v(G) be the number of vertices of G . For two r -graphs G and H , we define their union G\cup H by E(G\cup H):=E(G)\cup E(H) , and their difference G\setminus H by E(G\setminus H):=E(G)\setminus E(H) . By a graph , we