Submit progress

on Erdős–Szemerédi $3$-sunflower-free capacity ($C_{49}$)

The statement

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$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.