Erdős–Szemerédi $3$-sunflower-free capacity

Description of constant

A family of three distinct sets $A,B,C$ is a $3$-sunflower (or $\Delta$-system) if \(A\cap B \ =\ A\cap C \ =\ B\cap C.\) A family of sets is sunflower-free if it contains no $3$-sunflower (equivalently, no sunflower of any size $\ge 3$).

Let $[n]:=\{1,2,\dots,n\}$ and let $f(n)$ denote the maximum size of a sunflower-free family $\mathcal{F}\subseteq 2^{[n]}$. Define \(C_{49}\ :=\ \mu^{\mathrm S}\_3\ :=\ \limsup\_{n\to\infty} f(n)^{1/n}.\) A standard tensor power argument shows that the limsup is in fact a limit: \(\mu^{\mathrm S}\_3\ =\ \lim\_{n\to\infty} f(n)^{1/n}\) (see e.g. [TZ2025, (1.2)]).

Existence of the limit

The limit exists. One convenient way to see this is to reduce to uniform families and then apply a tensor-power (direct sum) argument (see also [TZ2025]).

For $0\le r\le n$, let $f_{r}(n)$ denote the maximum size of a sunflower-free $r$-uniform family $\mathcal{F}\subseteq \binom{[n]}{r}$, and set \(g(n)\ :=\ \max_{0\le r\le n} f\_{r}(n).\) Then \(g(n)\ \le\ f(n)\ \le\ (n+1)\,g(n),\) since any family $\mathcal{F}\subseteq 2^{[n]}$ decomposes as the disjoint union of its uniform layers $\mathcal{F}\cap\binom{[n]}{r}$ and one layer must have size at least $\lvert\mathcal{F}\rvert/(n+1)$.

Now let $X,Y$ be disjoint sets with $\lvert X\rvert=n$ and $\lvert Y\rvert=m$, and let $\mathcal{F}\subseteq \binom{X}{r}$ and $\mathcal{G}\subseteq \binom{Y}{s}$ be sunflower-free. Define the product family \(\mathcal{F}\otimes\mathcal{G}\ :=\ \{A\cup B:\ A\in\mathcal{F},\ B\in\mathcal{G}\}\ \subseteq\ \binom{X\cup Y}{r+s}.\) Then $\mathcal{F}\otimes\mathcal{G}$ is sunflower-free. Indeed, suppose that three distinct members $A_i\cup B_i$ ($i=1,2,3$) form a $3$-sunflower in $X\cup Y$. Since $X$ and $Y$ are disjoint, the equalities \((A_1\cup B_1)\cap(A_2\cup B_2)\ =\ (A_1\cup B_1)\cap(A_3\cup B_3)\ =\ (A_2\cup B_2)\cap(A_3\cup B_3)\) imply \(A_1\cap A_2\ =\ A_1\cap A_3\ =\ A_2\cap A_3\) and \(B_1\cap B_2\ =\ B_1\cap B_3\ =\ B_2\cap B_3.\) If two of the $A_i$ coincide, say $A_1=A_2$, then $A_1=A_1\cap A_2=A_1\cap A_3\subseteq A_3$, and uniformity forces $A_1=A_3$. Thus either $(A_1,A_2,A_3)$ is a triple of distinct sets forming a $3$-sunflower in $\mathcal{F}$, or all three $A_i$ coincide; similarly for the $B_i$. Since the unions $A_i\cup B_i$ are distinct, at least one of the triples $(A_1,A_2,A_3)$ or $(B_1,B_2,B_3)$ consists of three distinct sets, giving a contradiction.

Consequently $g(n+m)\ge g(n)g(m)$, so $\log g(n)$ is superadditive. By Fekete’s lemma, the limit $\lim_{n\to\infty} g(n)^{1/n}$ exists. Since $f(n)$ and $g(n)$ differ by at most the factor $(n+1)$, it follows that $\lim_{n\to\infty} f(n)^{1/n}$ exists as well.

Trivially $1\le \mu^{\mathrm S}_3 \le 2$.

Known upper bounds

Bound Reference Comments
$2$ Trivial $f(n)\le 2^n$.
$\frac{3}{2^{2/3}} \approx 1.8898815748$ [NS2017] They prove $\lvert\mathcal{F}\rvert \le 3(n+1) \sum_{k=0}^{\lfloor n/3\rfloor} \binom{n}{k} \le \left(\frac{3}{2^{2/3}}\right)^{n(1+o(1))}$ for sunflower-free $\mathcal{F}\subseteq 2^{[n]}$.

Known lower bounds

Bound Reference Comments
$1$ Trivial $f(n)\ge 1$.
$>1.551$ [DEGKM1997] This lower bound is obtained from a construction of Deuber–Erdős–Gunderson–Kostochka–Meyer. The numerical value is stated in [FPP2024], [TZ2025].
$\ge 1.554$ (unpublished) [NS2017] The arXiv preprint version of [NS2017] records $\mu^{\mathrm S}_3\ge 1.554$, citing an unpublished manuscript of the first author.
$\ge 1.5617847$* [IRSI2026] Uses the gluing construction of [DEGKM1997] (Lemmas 3.1, 4.4), with the chain counted exactly by a $2\times 2$ transfer matrix instead of an averaging step, and a new Sperner sunflower-free base family on 20 points (6127 sets). This gives $\mu^{\mathrm S}_3\ge\rho^{1/18}$, where $\rho\approx 3056.1945$ is the Perron root of the matrix with rows $(1884,1360)$ and $(1081,1802)$. Certificate and two independently written checkers at [IRSI2026] (tag v1.0). Found by AI agents; see the disclosure there.
$\ge 1.5621220$* [IRSI2026] Same construction as the previous row, with a new Sperner sunflower-free base family on 20 points (6150 sets; layer sizes 7, 10, 11, 12, 13 with 2, 360, 1108, 3600, 1080 sets; ports $u=18$, $v=19$). The transfer matrix has rows $(1802,1360)$ and $(1080,1908)$, characteristic polynomial $x^2-3710x+1969416$, Perron root $\rho = 1855+\sqrt{1471609}\approx 3068.0989$, so $\mu^{\mathrm S}_3\ge\rho^{1/18} = 1.5621220560\ldots$. Certificate and two independently written checkers at [IRSI2026] (tag v1.1; certificate SHA-256 c12d0dd6…fc7b). Found by AI agents; see the disclosure there.
$\ge 1.5647730$* [IRSI2026] Same construction, with a new Sperner sunflower-free base family on 20 points (6341 sets; layer sizes 7, 10, 11, 12, 13 with 2, 551, 1108, 3600, 1080 sets; ports $u=18$, $v=19$). The transfer matrix has rows $(1993,1360)$ and $(1080,1908)$, characteristic polynomial $x^2-3901x+2333844$, Perron root $\rho = (3901+\sqrt{5882425})/2\approx 3163.1856$, so $\mu^{\mathrm S}_3\ge\rho^{1/18} = 1.5647730960\ldots$. Certificate and three checkers at [IRSI2026] (tag v1.2; certificate SHA-256 7472112c…4e82e), one of them written independently by a model from a different provider (OpenAI). Found by AI agents; see the disclosure there.
$\ge 1.5664286$* [Cla2026] Same chain construction and exact transfer-matrix count as [IRSI2026], with a much smaller base family: 75 sets on 10 points. Identify the points with the edges of $K_5$ and take the edge sets of the 5 stars $K_{1,4}$, the 10 complete bipartite graphs $K_{2,3}$, and the 60 graphs whose complement in $K_5$ is a chair (the tree with degree sequence $3,2,1,1,1$). The family is $S_5$-invariant, Sperner and 3-sunflower-free: a two-page proof by hand, using only elementary facts about $K_5$, is in PROOF.md at [Cla2026] (refereed by an independent AI agent, not yet checked by a human), and a brute-force check over all 67525 triples is also provided. Every edge lies in 44 members and every pair of edges in 24, so for any choice of ports the transfer matrix has rows $(20,24)$ and $(11,20)$, with Perron root $20+2\sqrt{66}$, and each copy adds 8 points: $\mu^{\mathrm S}_3\ge(20+2\sqrt{66})^{1/8} = 1.5664286\ldots$.
$\ge 1.5666969$* [Cla2026] Alternate the previous family with a second base family: 121 sets on $\mathbb{Z}_{11}$, the images of $\{0,1,2,3,4,5,6\}$, $\{0,1,2,3,4,6,7\}$ and $\{0,1,2,6,9\}$ under $x\mapsto ax+b$ with $a$ a nonzero square mod 11 (transfer matrix rows $(31,44)$ and $(15,31)$; the link of every point is a copy of the previous family). The product of the two transfer matrices has rows $(980,1624)$ and $(641,1104)$, Perron root $1042+2\sqrt{261207}$, and one period adds 17 points: $\mu^{\mathrm S}_3\ge(1042+2\sqrt{261207})^{1/17} = 1.5666969\ldots$. Verification script (standard-library Python, about 15 seconds) and proofs at [Cla2026].
$\ge 1.5675517$* [Syl2026] Same chain construction and exact transfer-matrix count as [IRSI2026], with base families built by gluing (by [DEGKM1997], Lemma 4.4) copies of the two families of [Cla2026], the 75-set family $F$ on the edges of $K_5$ and the 121-set family $H$ on $\mathbb{Z}_{11}$, into a tree. A first step already beats the previous row: glue $H$ (at $0$) to $F$ at the edge $(0,3)$ and chain at the edges $(0,1)\to(0,2)$; this 4349-set family on 19 points gives the transfer matrix with rows $(1123,1481)$, $(622,1123)$ and $\mu^{\mathrm S}_3\ge(1123+\sqrt{921182})^{1/17}=1.5675245\ldots$. Better: let the gadget $G$ be $F$ with copies of $H$ glued at the edges $(1,2)$ and $(1,4)$, rooted at $(0,1)$ (250659 sets on 28 points, 98308 avoiding and 152351 containing the root), and let the chain unit be $F$ with ports $(0,1)\to(0,2)$ and copies of $G$ glued at $(0,3)$ and $(0,4)$ (62 points, 60 added per unit). Its port counts are $N_{00}=148811965456$, $N_{01}=N_{10}=279351870092$, $N_{11}=378843386627$, so $\mu^{\mathrm S}_3\ge\rho^{1/60}=1.5675517\ldots$ with $\rho=279351870092+\sqrt{378843386627\cdot 148811965456}$. Verification script (standard-library Python, about 15 seconds, including an exhaustive check of $G$) and proofs at [Syl2026]. Found by an AI agent; see the disclosure there.
$\ge 1.5678015$* [Syl2026] Same chain construction and exact transfer-matrix count as [IRSI2026], with a 19-point base family built from the two families $F$ (75 sets on the edges of $K_5$) and $H$ (121 sets on $\mathbb{Z}_{11}$) of [Cla2026]. Glue $H$ (at $0$) to $F$ at the edge $(0,3)$ by [DEGKM1997], Lemma 4.4 (4349 sets on 19 points), and add 15 sets contained in the $F$-part (listed at [Syl2026]). The resulting family $\hat B$ has 4364 sets and is Sperner and 3-sunflower-free by an exhaustive check. Chaining copies of $\hat B$ at the edges $(0,1)\to(0,2)$ gives the transfer matrix with rows $(1127,1488)$ and $(622,1127)$, with Perron root $1127+\sqrt{925536}$, and each copy adds 17 points: the chain families have at least $c\rho^k$ members on $17k+2$ points, so $\mu^{\mathrm S}_3\ge(1127+\sqrt{925536})^{1/17} = 1.5678015\ldots$. Verification script (standard-library Python, about 6 seconds, including the exhaustive check of $\hat B$) and proofs at [Syl2026]. Found by an AI agent; see the disclosure there.
$\ge 1.5678599$* [Kos2026] Same chain construction and exact transfer-matrix count as [IRSI2026], with a 28-point base family built from the two families $F$ (75 sets on the edges of $K_5$) and $H$ (121 sets on $\mathbb{Z}_{11}$) of [Cla2026], extending the augmentation proposed in PR #237 to two pendants. Glue a copy of $H$ (at $0$) to $F$ at the edge $(0,3)$ and another at the edge $(0,4)$ by [DEGKM1997], Lemma 4.4 (250659 sets on 28 points). Then, at each pendant, add 15 sets whose part in that pendant is empty, and add 20 sets lying inside the first copy of $H$ and one set made of three $K_5$ edges and all of the second copy (all listed at [Kos2026]). The resulting family has 252292 sets and is Sperner and 3-sunflower-free by an exhaustive check. Chaining copies at the edges $(0,1)\to(0,2)$ gives port counts $N_{00}=33969$, $N_{01}=N_{10}=64728$, $N_{11}=88867$, i.e. the transfer matrix with rows $(64728,88867)$ and $(33969,64728)$, with Perron root $64728+\sqrt{3018723123}$, and each copy adds 26 points: the chain families have at least $c\rho^k$ members on $26k+2$ points, so $\mu^{\mathrm S}_3\ge(64728+\sqrt{3018723123})^{1/26} = 1.5678599\ldots$. Certificate (SHA-256 10ee18f9…4838), a C checker for the exhaustive check, and a standard-library Python script that rebuilds the family from this description and recomputes $\rho$ are at [Kos2026]; the family was also checked exhaustively by an independent checker written from the certificate format alone. Found by an AI agent; see the disclosure there.

References

Contribution notes

Prepared with assistance from ChatGPT 5.2.

The [Cla2026] rows were found and prepared with Claude (Anthropic, Claude Opus 5.5): computer search for the base families, the verification script, and the text; the families, the chain count and the literature were re-checked independently by a second Claude agent working from the statement only.

The [Syl2026] rows were found and checked with an AI agent (Grok Bot, running the V3R1T4S kit, https://github.com/elder-plinius/V3R1T4S) directed by Sylla (GitHub: xSyllaa), who takes responsibility for the submission: computer search over glued and augmented copies of the [Cla2026] families, the verification scripts, and the text. Each construction was re-checked by three fresh-context AI reviewers (separate sessions of the same agent pipeline, each with its own code); no human mathematician has checked the argument. The [Kos2026] row was found and prepared with Claude (Anthropic, Claude Opus 5.5), directed by Dennis Koshta, who takes responsibility for the submission: computer search over augmented multi-pendant gluings of the [Cla2026] families, the certificate, the checkers, and the text. The certificate was checked exhaustively by a second Claude agent with its own checker, written from the certificate format specification only, without access to the construction code; no human mathematician has checked the argument.

← Back to the table of constants