Sunflower combinatorics

Solution 1:

$\newcommand{\ms}{\mathscr}$What you call the core is also called the kernel of the sunflower. (By the way, another term for sunflower, especially in infinite combinatorics, is $\Delta$-system.)

The theorem as stated is false for $p=1$: if $p=1$, then $(p−1)^\ell\ell!=0$, but an empty family clearly does not contain a sunflower with one petal. With a small change, however, you can make it true even in the case $\ell=1$; the result, due to Erdős and Rado, is known as the

Sunflower Lemma: Let $\ms{A}$ be a family of sets such that $|A|\le\ell$ for each $A\in\ms{A}$. If $|\ms{A}|>(p-1)^\ell\ell!$, then $\ms{A}$ contains a sunflower with $p$ petals.

Proof: The proof is by induction on $\ell$. The result is clear for $\ell=1$: any $p$-subset of $\ms A$ is a sunflower with $p$ petals (and empty kernel). (Note that one of the petals may be empty, if $\varnothing\in\ms A$.)

Now suppose that $\ell\ge 2$, let $\ms A$ be family of more than $(p-1)^\ell\ell!$ sets of cardinality at most $\ell$, and let $\ms D=\{A_1,\dots,A_m\}$ be a maximal pairwise disjoint subfamily of $\ms A$. If $m\ge p$, $\ms D$ contains a sunflower with $p$ petals (and empty kernel), so assume that $m<p$. Let $D=\bigcup\ms D$; clearly $|D|\le m\ell\le(p-1)\ell$. Since $\ms D$ is maximal, $A\cap D\ne\varnothing$ for each $A\in\ms A$, so by the pigeonhole principle some $x\in D$ belongs to at least $$\left\lceil\frac{|\ms A|}{|D|}\right\rceil>\frac{(p-1)^\ell\ell!}{(p-1)\ell}=(p-1)^{\ell-1}(\ell-1)!$$ members of $\ms A$. Let $\ms{A}_0=\big\{A\setminus\{x\}:x\in A\in\ms A\big\}$; then each element of $\ms A_0$ has cardinality at most $\ell-1$, and $|\ms A_0|>(p-1)^{\ell-1}(\ell-1)!$, so by the induction hypothesis $\ms A_0$ contains a sunflower $\ms A$ with $p$ petals. Clearly $\big\{S\cup\{x\}:S\in\ms S\big\}$ is a subset of $\ms A$ that forms a sunflower with $p$ petals. $\dashv$

Let $\varphi(\ell,p)$ be the smallest positive integer such that each family of $\varphi(\ell,p)$ sets, each of cardinality at most $\ell$, contains a sunflower with $p$ petals. The sunflower lemma says that $\varphi(\ell,p)\le(p-1)^\ell\ell!+1$. The question asks to replace this bound by $(p-1)^\ell\ell!$ when $\ell>1$, and we saw above that for this improvement we must also require that $p>1$. Let’s see what happens when we try to prove the stronger result.

The induction step in the proof of the sunflower lemma still works: we get some $x\in D$ that belongs to at least $(p-1)^{\ell-1}(\ell-1)!$ members of $\ms A$, which is all that is needed to apply the induction hypothesis. To get the induction off the ground, however, we must show that if $\ms A$ is a family of $2(p-1)^2$ sets of cardinality at most $2$, then $\ms A$ contains a sunflower with $p$ petals.

This is clear when $p=2$: then $2(p-1)^2=2$, and any pair of sets of cardinality at most $2$ is a sunflower with two petals. Suppose that $p>2$. As before let $\ms D$ be a maximal pairwise disjoint subset of $\ms A$; if $|\ms D|\ge p$, we’re done, so suppose that $|\ms D|<p$. Let $D=\bigcup\ms D$; $|D|\le2(p-1)$. If $|D|<2(p-1)$, some $x\in D$ belongs to at least $p$ members of $\ms A$, and we can argue as before to find a sunflower in $\ms A$ with $p$ petals. Assume, then, that $|D|=2(p-1)$ and further that each $x\in D$ belongs to exactly $p-1$ members of $\ms A$. Then $\ms D$ contains exactly $p-1$ doubletons, and each point of $D$ is contained in exactly $p-1$ members of $\ms A$. For $x\in D$ let $\ms A_x=\{A\in\ms A:x\in A\}$; then for each $x\in D$ we have $|\ms A_x|=p-1$ and $|\ms A_x\cap\ms D|=1$, so $$|\ms A|=|\ms D|+\sum_{x\in D}\big(|\ms A_x|-1\big)=p-1+2(p-1)(p-2)=2(p-1)\left(p-\frac32\right)<2(p-1)^2\;,$$ which is a contradiction. Thus, $\ms A$ must in fact contain a sunflower with $p$ petals, and the induction does get off the ground.

This shows that the desired result holds provided that $p,\ell>1$.

Solution 2:

[The original formulation of the question had $|\mathcal A|\ge(p-1)^l l!$ rather than $|\mathcal A|>(p-1)^l l!$. The result is true in this case, but a somewhat more delicate argument in needed, which made me suspect the intended question had the strict inequality, as in the current version. Some of the comments below refer to this original formulation.]

Pretty sure there is a mistake in your statement, and what you want is to show that a family $\mathcal A$ with more than $(p-1)^l l!$ many sets of size at most $l$ contains $p$ that form a sunflower. (Sunflowers are also called $\Delta$-systems, by the way.)

A reasonable approach is by induction on $l$. The result is clear if $l=1$, since then we have at least $p$ distinct singleton sets in $\mathcal A$, which therefore are pairwise disjoint.

We may assume that we do not have $p$ disjoint sets, and also that no element $x_0$ belongs to too many sets in $\mathcal A$: If $x_0$ is in more than $(p-1)^{k-1}(k-1)!$ many sets, we can restrict to them, remove $x_0$ from each, and apply induction.

The key idea is to combine these two observations. Pick a maximal pairwise disjoint subfamily $\mathcal F$. Maximality buys us that any other set in $\mathcal A$ meets one of the sets in this subfamily. This gives you a way of bounding $|\mathcal A|$: There are at most $l-1$ sets in the disjoint subfamily, and any other set, must meet something in $\mathcal F$. But we have a bound on the number of times we can have any element. I'll leave the details to you.

Let me add that the original proof, in

Paul Erdős, and Richard Rado. Intersection theorems for systems of sets, Journal of the London Mathematical Society, 2nd. series 35 (1), (1960), 85–90. MR0111692 (22 #2554)

starts the same way, and obtains a somewhat better bound, by an inclusion-exclusion argument: It is enough to assume $$ |\mathcal A|> l!(p-1)^{l+1}\left(1-\frac1{2!(p-1)}-\frac2{3!(p-1)^2}-\dots-\frac{l-1}{l!(p-1)^{l-1}}\right). $$