A note on the minimum size of Turán systems
Xizhi Liu, Oleg Pikhurko · 2025
Read A note on the minimum size of Turán systems by Xizhi Liu, Oleg Pikhurko (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-15457.txt.
Introduction
Xizhi Liu and Oleg Pikhurko bound the smallest size of Turán systems in a short note from 2025. A Turán system is a hypergraph where every large vertex set holds at least one edge. Past bounds covered two ranges for the gap between the two size parameters, set by Sidorenko and by later authors. The note fills the last open middle range, giving upper bounds where none were known before. Readers in extremal combinatorics get the missing case that completes the range picture for Turán system size.
Catalog record
| CREATOR | Xizhi Liu, Oleg Pikhurko |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-15457
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on the minimum size of Turán systems Xizhi Liu, Oleg Pikhurko Abstract For positive integers n ≥ s > r n\geq s>r , a Turán ( n , s , r ) (n,s,r) -system is an n n -vertex r r -graph in which every set of s s vertices contains at least one edge. Let T ( n , s , r ) T(n,s,r) denote the the minimum size of a Turán ( n , s , r ) (n,s,r) -system. Upper bounds on T ( n , s , r ) T(n,s,r) were established by Sidorenko [ Sid97 ] for the case s − r = Ω ( r / ln r ) s-r=\Omega(r/\ln r) (based on a construction of Frankl–Rödl [ FR85 ] ) and by a number of authors in the case s − r = O ( 1 ) s-r=O(1) . In this note, we establish upper bounds in the remaining range O ( 1 ) < s − r = O ( r / ln r ) O(1)<s-r=O(r/\ln r) . 1 Introduction Given an integer r\geq 2 , an r -uniform hypergraph (henceforth an r -graph ) \mathcal{H} is a collection of r -subsets of some set V . We call V the vertex set of \mathcal{H} and denote it by V(\mathcal{H}) . When V is understood, we usually identify a hypergraph \mathcal{H} with its set of edges. For positive integers n\geq s>r , a Turán (n,s,r) -system is an r -graph \mathcal{H} on an n -set V such that every s -subset S\subseteq V contains at least one edge from \mathcal{H} . Denote by T(n,s,r) the smallest size (i.e. the number of edges) of a Turán (n,s,r) -system. Observe that T(n,s,r)=\binom{n}{r}-\mathrm{ex}(n,K_{s}^{r}) , where \mathrm{ex}(n,K_{s}^{r}) denotes the Turán number of the complete r -graph on s vertices K_{s}^{r} . A simple averaging argument shows that \mathrm{ex}(n,K_{s}^{r})/\binom{n}{r} is non-increasing (see e.g. [ KNS64 ] ), and hence the following limit exists: \displaystyle t(s,r)\coloneqq\lim_{n\to\infty}\frac{T(n,s,r)}{\binom{n}{r}}. (1) Determining the value of t(s,r) is a central topic in Extremal Combinatorics. The seminal Turán Theorem [ Tur41 ] established that t(s,2)=\frac{1}{s-1} for all s\geq 3 (with the case s=3 solved earlier by Mantel [ Man07 ] ). However, the exact value of t(s,r) remains unknown for any pair (s,t) satisfying s>r\geq 3 , despite decades of active attempts. Erdős [ Erd81 ] offered $500 for the determination of t(s,r) for any s>r\geq 3 . Turán and other researchers conjectured that t(s,3)=\frac{4}{(s-1)^{2}} for s\geq 4 . Various constructions achieving this bound are known (see e.g. [ Sid95 ] ). For r\geq 4 , there is no general conjectured value for t(s,r) , except for the case (s,r)=(5,4) (see [ Gir90 , Mar09 ] ). For further related results, we refer the reader to surveys such as [ dC94 , Für91 , Sid95 , Kee11 ] . In this note, we focus on the case where r\to\infty , and all asymptotics are taken with respect to r unless otherwise specified. The trivial lower bound is t(s,r)\geq{1}/{\binom{s}{r}} , which follows e.g. from the monotonicity of the ratio in ( 1 ). For convenience, let us define \displaystyle\mu(s,r)\coloneqq t(s,r)\cdot\binom{s}{r}. Thus \mu(s,r) is always at least 1. The best-known general lower bound, t(s,r)\geq 1/{\binom{s-1}{r-1}} (i.e. \mu(s,r)\geq s/r ) is due to de Caen [ dC83a ] . In particular, t(r+1,r)\geq\frac{1}{r} , a result that was independently proved by de Caen [ dC83b ] , Sidorenko [ Sid82 ] , and Tazawa and Shirakura [ TS83 ] . Further improvements on t(r+1,r) in lower order terms were made by Giraud (unpublished), Chung–Lu [ CL99 ] , and Lu–Zhao [ LZ09 ] . Improving previous upper bounds established by Sidorenko [ Sid81 ] , Kim–Roush [ KR83 ] , Frankl–Rödl [ FR85 ] , and Sidorenko [ Sid97 ] , the second author established the following upper bound, which disproved the conjecture of de Caen [ dC94 ] that r\cdot t(r+1,r)\to\infty . Theorem 1 ( [ Pik24 ] ) . For every integer R\geq 1 , it holds that \displaystyle\mu(r+R,r)\leq\alpha+o(1),\quad\text{as}\ r\to\infty, where \alpha\coloneqq{(c_{0}+1)^{R+1}}/{c_{0}^{R}} with c_{0}=c_{0}(R) being the largest real root of the equation \mathrm{e}^{x}=(x+1)^{R+1} . In particular, \mu(r+1,r)\leq 4.911 for all sufficiently large r . An immediate corollary of Theorem 1 (for derivation see [ Pik24 , Corollary 1.3] ) is that, for all sufficiently large R , \displaystyle\limsup_{r\to\infty}~\mu(r+R,r)\leq R\ln R+3R\ln\ln R=(1+o(1))R\ln R. (2) This improves asymptotically the previous bound by Frankl–Rödl [ FR85 ] which states that, for any fixed R\geq 1 , we have \displaystyle\mu(r+R,r)\leq(1+o_{R}(1))R(R+4)\ln r,\quad\mbox{as $r\to\infty$}. For the case R\geq\frac{r}{\log_{2}r} , Sidorenko [ Sid97 ] (by analyzing the construction of Frankl–Rödl [ FR85 ] in this regime) proved that \displaystyle\mu(r+R,r)\leq(1+o(1))R\ln\binom{r+R}{R}. (3) Although Turán systems were actively studied, it seems that no general upper bounds on t(r+R,r) have been published in the intermediate regime 1\ll R\leq r/\log_{2}r . This is the case we address in this note. In brief, we show that Sidorenko’s bound in ( 3 ) applies in the whole range as along as R is sufficiently large, while the asymptotic bound in ( 2 ) can be extended from constant R to any R=o(\sqrt{r}) . Theorem 2 . For every \varepsilon>0 , there exists r_{0} such that the following statements hold for all r,R satisfying R\geq r_{0} . (i) It holds that \mu(r+R,r)\leq(1+\varepsilon)R\ln\binom{r+R}{R} . (ii) Suppose that R\leq\sqrt{18r\ln r} . Then \displaystyle\mu(r+R,r)\leq\mathrm{e}^{18R^{2}/r}\cdot(1+\varepsilon)R\ln R. 2 Proofs In this section, we prove Theorem 2 . We will use the following notation. For an integer n\geq 1 and a set X , we denote [n]:=\{1,\dots,n\} and \binom{X}{n}:=\{Y\subseteq X:|Y|=n\} . Let us begin with the proof of Theorem 2 (i) . Proof of Theorem 2 (i) . Given \varepsilon>0 , let r_{0} be sufficiently large. Take any r,R with R\geq r_{0} . By ( 3 ), we can assume that e.g. R\leq\frac{r}{\ln r} . Let s\coloneqq r+R . Define \displaystyle N\coloneqq\left\lfloor r(r-1){s\choose R}/(2R)\right\rfloor\quad\text{and}\quad\ell\coloneqq\left\lfloor{s\choose R}/\ln\left({s\choose R}^{2}{N-s\choose R}\right)\right\rfloor. In the rest of the proof, we repeat the construction of Frankl and Rödl [ FR85 , Theorem 3] , arguing that our choices of N and \ell give the stated bound. Consider a random colouring c:{[N]\choose r}\to[\ell] . For each s -set A\in{[N]\choose s} we have a bad event that some colour is not present in {A\choose r} . Its probability p is at most \ell(1-1/\ell)^{{s\choose r}}\leq\ell\mathrm{e}^{-{s\choose R}/\ell} (note that \binom{s}{r}=\binom{s}{s-r}=\binom{s}{R} ). Define the obvious dependency graph D on {[N]\choose s} where A\sim B if |A\cap B|\geq r (including loops). It is regular of degree \Delta:=\sum_{i=r}^{s}{s\choose i}{N-s\choose s-i} . We want to apply the Lovász Local Lemma [ EL75 ] (see also e.g. [ AS16 , Corollary 5.1.2] ), so we have to check that \mathrm{e}p\Delta<1 , for which it suffices to prove \displaystyle\mathrm{e}^{{s\choose R}/\ell}>\mathrm{e}\ell\Delta. (4) First, we estimate \Delta . Consider the ratio of two consecutive terms: \frac{{s\choose i+1}{N-s\choose s-i-1}}{{s\choose i}{N-s\choose s-i}}=\frac{(s-i)^{2}}{(i+1)(N-2s+i+1)}. Since 3\leq R\leq s/2 and N\geq{s\choose R}\geq{s\choose 3} , this ratio is at most say 1/2 for every i\in[r,s] and thus we can bound \displaystyle\Delta\leq 2{s\choose r}{N-s\choose s-r}=2{s\choose R}{N-s\choose R}. (5) Thus and by the choice of \ell we have \mathrm{e}^{{s\choose r}/\ell}\geq{s\choose R}^{2}{N-s\choose R}\geq\mathrm{e}\cdot\frac{{s\choose R}}{2\ln{s\choose R}}\cdot 2{s\choose R}{N-s\choose R}\geq\mathrm{e}\ell\Delta, as desired. (In fact, our definition of