Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


These author-recorded arguments are by Plasma AI. The theorems they support are the claims L214, which proves that intersecting families can be arbitrarily spread and refutes Rao's suggested r = O(p) matching lemma, and L215, which shows that spread does not force a sunflower with a bounded core. The proof of L214 holds the lemmas used below. This page explains the mechanism, the further author-recorded observations that are not part of either claim, and what remains open. The attack it serves is recorded in the editable proof sketch for Problem 20.

Intersecting families with unbounded normalized spread are already known: Alweiss–Lovett–Wu–Zhang, Section 4 after Theorem 4.2, records spread Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n), citing Lovett–Solomon–Zhang (2019). The explicit constructions here are not a novelty claim for that existence result or its asymptotic order.

The route this closes

Write nn for the size of the sets and kk for the number of petals, as in Problem 20. A family F\mathcal F of nn-sets is absolutely RR-spread if every nonempty TT lies in at most Rn−∣T∣R^{n-|T|} members, and normalized RR-spread if every nonempty TT lies in at most R−∣T∣∣F∣R^{-|T|}|\mathcal F| members, which forces ∣F∣≥Rn|\mathcal F|\ge R^n.

The matching lemma M(k)M(k) asks for a constant RkR_k such that every absolutely RkR_k-spread family of nn-sets with more than RknR_k^n members has kk pairwise disjoint members, for every nn. It would give f(n,k)≤⌊Rkn⌋+1f(n,k)\le\lfloor R_k^n\rfloor+1, and settle the strict form of Problem 20 after enlarging the base, for example to Rk+2R_k+2. Given ∣F∣>Rkn|\mathcal F|>R_k^n, choose an inclusion-maximal TT with ∣FT∣>Rkn−∣T∣|\mathcal F_T|>R_k^{n-|T|}; the empty set qualifies, and ∣T∣<n|T|<n since an nn-set lies in at most one member. The link {S∖T:S∈FT}\{S\setminus T:S\in\mathcal F_T\} is absolutely RkR_k-spread by maximality and has more than Rkn−∣T∣R_k^{n-|T|} members, and kk disjoint members of it lift to a kk-sunflower with core TT. This is the remark accompanying Rao's Lemma 2, whose source says the lemma might hold with r(p,k)=O(p)r(p,k)=O(p), and Bell–Chueluecha–Warnke's Lemma 2 is M(k)M(k) with RkR_k replaced by Cklog⁡nCk\log n.

L214 gives intersecting families, hence families without two disjoint members, that are absolutely rr-spread with more than rnr^n members for every real r≥16r\ge16, and normalized ρ\rho-spread for every integer ρ≥2\rho\ge2. The general thinning lemma extends the absolute examples to every r≥2r\ge2. Thus M(k)M(k) fails for every k≥3k\ge3: if r<k−1r<k-1, use k−1k-1 singletons, and if r≥k−1r\ge k-1, use an intersecting example. For k=2k=2 the examples refute every r≥2r\ge2, but not r=1r=1, where absolute spread itself forces disjointness. The converse of the link argument needs no lemma: Problem 20 with constant ckc_k gives a kk-sunflower in every family with more than cknc_k^n members, spread or not. So Problem 20 is equivalent to the spread form

SF(kk). For each k≥3k\ge3 there is RkR_k such that every absolutely RkR_k-spread family of nn-sets with more than RknR_k^n members contains a kk-sunflower,

and the families of L214 show that the sunflower in SF(kk) cannot always be taken with an empty core.

Substitution and the seed quantity

For an aa-uniform family GG and a uniform family HH, the substitution G[H]G[H] replaces each point ii of a member A∈GA\in G by a member SiS_i of a copy of HH placed over ii; its powers are G1=GG^1=G and Gh+1=G[Gh]G^{h+1}=G[G^h]. Two members of G[H]G[H] meet whenever GG and HH are intersecting, because their root sets share a point ii and their fibers over ii meet. The key fact is that spread behaves exactly under substitution. With the excess EF(R)=max⁡T≠∅Pr⁡[T⊆S]R∣T∣E_{\mathcal F}(R)=\max_{T\ne\varnothing}\Pr[T\subseteq S]R^{|T|} of a uniform random member SS, and ψG(E)=max⁡I≠∅Pr⁡[I⊆A]E∣I∣\psi_G(E)=\max_{I\ne\varnothing}\Pr[I\subseteq A]E^{|I|} for a uniform random A∈GA\in G, Lemma 2 of the L214 proof gives

EG[H](R)=ψG(EH(R)),EGh(R)=ψG(h)(R),E_{G[H]}(R)=\psi_G\bigl(E_H(R)\bigr),\qquad E_{G^h}(R)=\psi_G^{(h)}(R),

and F\mathcal F is normalized RR-spread exactly when EF(R)≤1E_{\mathcal F}(R)\le1.

Proposition (author-recorded). Let GG be an intersecting aa-uniform family, a≥2a\ge2, in which no point lies in every member, and put

ρ(G)=min⁡∣I∣≥2Pr⁡[I⊆A]−1/(∣I∣−1),\rho(G)=\min_{|I|\ge2}\Pr[I\subseteq A]^{-1/(|I|-1)},

the minimum over sets II contained in a member. Then the largest RR for which GhG^h is normalized RR-spread tends to ρ(G)\rho(G) as h→∞h\to\infty, and it is at most ρ(G)\rho(G) for every hh.

Proof. If R>ρ(G)R>\rho(G), some II with ∣I∣≥2|I|\ge2 has Pr⁡[I⊆A]R∣I∣−1>1\Pr[I\subseteq A]R^{|I|-1}>1, so ψG(E)>E\psi_G(E)>E for every E≥RE\ge R and the iterates from RR never fall to 11. If 1≤R<ρ(G)1\le R<\rho(G), then on [1,R][1,R] every term of ψG\psi_G is below the identity: sets with ∣I∣≥2|I|\ge2 give Pr⁡[I⊆A]E∣I∣≤E(E/ρ(G))∣I∣−1<E\Pr[I\subseteq A]E^{|I|}\le E(E/\rho(G))^{|I|-1}<E, and singletons give at most p1E<Ep_1E<E, where p1<1p_1<1 is the largest point probability. By continuity ψG(E)≤E−δ\psi_G(E)\le E-\delta on [1,R][1,R] for some δ>0\delta>0, so the iterates fall below 11, and they stay there because ψG(E)≤E\psi_G(E)\le E for E≤1E\le1. □\square

So building spread intersecting families reduces to one level: a seed must make every set of two or more points rare, with the singletons free except for p1<1p_1<1. Three seeds show the range.

  • The triangle, the three 22-subsets of a 33-set, has ρ=3\rho=3. Its powers are the minterm families of recursive majority of three, whose spread rises to 33; it is 1.51.5 at h=1h=1 and about 2.122.12, 2.522.52, 2.752.75 and 2.872.87 at h=2,3,4,5h=2,3,4,5.
  • The Hilton–Milner type seed, {B}\{B\} together with all sets {x}∪B′\{x\}\cup B' where B′B' is an (a−1)(a-1)-subset of a set Y⊇BY\supseteq B meeting the aa-set BB, has ρ\rho close to aa when ∣Y∣|Y| is large compared with a2a^2, so spread is unbounded already. Its point xx lies in all members but one, so the leaf reached through xx at every level of GhG^h lies in a fraction (1−1/∣G∣)h(1-1/|G|)^h of the members; spread RR needs at least ∣G∣ln⁡R|G|\ln R levels, and the uniformity is doubly exponential in the spread.
  • The two-star block seed B(ρ,ρρ)B(\rho,\rho^\rho) of L214 has ρ(G)=21/ρρρ\rho(G)=2^{1/\rho^\rho}\rho and p1=1/2p_1=1/2: both centers lie in half of the members, the members of the first kind are a product family of spread exactly ρ\rho, and a member of the second kind must contain a whole block YiY_i, which the ρρ\rho^\rho blocks make as rare as ρ\rho-spread requires. Its excess halves at each level, so ⌈log⁡2ρ⌉\lceil\log_2\rho\rceil levels suffice.

Rate and every large n

The block seed gives normalized spread ρ\rho at uniformity n=(ρρ+1)⌈log⁡2ρ⌉n=(\rho^\rho+1)^{\lceil\log_2\rho\rceil}, so log⁡2n=(1+o(1))ρ(log⁡2ρ)2\log_2n=(1+o(1))\rho(\log_2\rho)^2 and the spread is (1+o(1))log⁡2n/(log⁡2log⁡2n)2(1+o(1))\log_2n/(\log_2\log_2n)^2. The absolute form loses the factor 1616 of L214's thinning lemma.

Remark (author-recorded): every large nn. Let N0=(ρρ+1)hN_0=(\rho^\rho+1)^h with h=⌈log⁡2ρ⌉h=\lceil\log_2\rho\rceil, and let n≥(ρ+1)N0n\ge(\rho+1)N_0. Write n=qN0+jn=qN_0+j with q=⌊n/N0⌋≥ρ+1q=\lfloor n/N_0\rfloor\ge\rho+1 and 0≤j<N00\le j<N_0. The family B(ρ,q−1)[B(ρ,ρρ)h]B(\rho,q-1)[B(\rho,\rho^\rho)^h] is intersecting, qN0qN_0-uniform and normalized ρ\rho-spread: the inner power is normalized ρ\rho-spread by L214, and Lemma 3 of the L214 proof gives ψB(ρ,q−1)(E)≤E\psi_{B(\rho,q-1)}(E)\le E for E≤ρE\le\rho. Add to each member jj new points of its own. A set TT meeting the new points of a member lies in that member only, so the result is normalized RR-spread for R=ρqN0/nR=\rho^{qN_0/n}, which is at least ρ(ρ+1)/(ρ+2)=(1−o(1))ρ\rho^{(\rho+1)/(\rho+2)}=(1-o(1))\rho. Choosing the largest ρ\rho with (ρ+1)N0≤n(\rho+1)N_0\le n, every large nn carries an intersecting family of nn-sets with normalized spread at least (1−o(1))log⁡2n/(log⁡2log⁡2n)2(1-o(1))\log_2n/(\log_2\log_2n)^2.

In the absolute form, Bell–Chueluecha–Warnke's Lemma 2 caps the spread of an intersecting family at Clog⁡nC\log n. In the normalized form, a uniformly weighted family is spread in the weighted sense of Alweiss, Lovett, Wu and Zhang exactly when it is normalized spread, and a uniformly random half of the ground set contains a member of an intersecting family with probability at most 1/21/2, since the half and its complement cannot both contain one. Their Theorem 2.5 with α=β=1/2\alpha=\beta=1/2 therefore caps the normalized spread at O(log⁡nlog⁡log⁡n)O(\log n\log\log n), and Rao's improvement, which they record, at O(log⁡n)O(\log n). So the least spread that forces two disjoint members lies between clog⁡n/(log⁡log⁡n)2c\log n/(\log\log n)^2 and Clog⁡nC\log n. Through the link argument a matching lemma at spread RR gives f(n,k)≤⌊Rn⌋+1f(n,k)\le\lfloor R^n\rfloor+1; at the uniformities of L214 no valid matching lemma has RR below the spread of these families.

The same step appears outside the sunflower problem. Kupavskii and Zakharov's spread-approximation method (Spread approximations for forbidden intersections problems, arXiv:2203.13379v3, proof of Lemma 9, pp. 7--8) uses that two families of kk-sets whose measures are rr-spread with r>211log⁡2(2k)r>2^{11}\log_2(2k) cannot be cross-intersecting, by a random halving. An intersecting family is cross-intersecting with itself, so L214 shows that this logarithm cannot be replaced by a constant, nor by anything below clog⁡k/(log⁡log⁡k)2c\log k/(\log\log k)^2. This bears only on the generality of that step: their families are spread because they are homogeneous subfamilies of a complete layer, which the families of L214 are not, and no theorem of theirs is contradicted.

Where the sunflowers are

For Problem 20 the relevant question is how spread families with no kk disjoint members still contain kk-sunflowers. The core lemma, Lemma B in the proof of L215, answers this for substitutions. If GG is intersecting and HH is intersecting and free of kk-sunflowers, k≥3k\ge3, then the root sets of a kk-sunflower of G[H]G[H] form a kk-sunflower of GG with a nonempty core A∗A_*. Its core is the union of the common fibers over A∗A_*, so it consists of whole members of HH. In particular G[H]G[H] is free of kk-sunflowers when GG is.

Three consequences follow.

  • No sunflowers at spread below 10\sqrt{10}. The triangle has no 33-sunflower, so the recursive majority families are intersecting, 33-sunflower-free and have normalized spread approaching 33. A better seed is the family of ten triples of a 66-set {012,013,024,035,045,125,134,145,234,235}\{012,013,024,035,045,125,134,145,234,235\}. It contains one triple from each complementary pair, so it is intersecting, and every pair of points lies in exactly two triples. It is 33-sunflower-free, since a core of two points would need three triples through one pair, and the link of each point is a five-cycle, which has no three disjoint edges. Its seed quantity is ρ=10\rho=\sqrt{10}, from the triples, with p1=1/2p_1=1/2. Its powers are therefore intersecting, 33-sunflower-free and normalized RR-spread for every R<10R<\sqrt{10} once the power is large enough. So the threshold R3R_3 of SF(33) is at least 10\sqrt{10} in the normalized form. The same powers have 10(3h−1)/210^{(3^h-1)/2} members of size 3h3^h; how this compares with the published lower bounds for three-petal sunflowers was not checked here.
  • Cores of every size are forced. Substituting the triangle powers DgD^g into the block-family powers of L214 gives L215: for every R≥3R\ge3 and gg an intersecting family with RR-spread uniform measure in which every kk-sunflower, for every k≥3k\ge3, has a core of at least 2g2^g points. The outer block levels absorb the excess 3(R/3)2g3(R/3)^{2^g} that the inner triangle powers carry, halving it at each level. At fixed R>3R>3 these cores have about log⁡2log⁡2n/log⁡2(R/3)\log_2\log_2n/\log_2(R/3) points.
  • The block powers have one-point cores. In B(ρ,m)B(\rho,m) the members {x}∪T1,…,{x}∪Tρ\{x\}\cup T_1,\dots,\{x\}\cup T_\rho with pairwise disjoint transversals form a ρ\rho-sunflower with core {x}\{x\}. In B(ρ,m)hB(\rho,m)^h, take these members at the root, a ρ\rho-sunflower of B(ρ,m)h−1B(\rho,m)^{h-1} with a one-point core over xx, and arbitrary members over the other points. The core is the single leaf reached through xx at every level.

Remark (author-recorded): the core point can be light. With B=B(ρ,ρρ)B=B(\rho,\rho^\rho), the power BhB^h is normalized ρ\rho-spread for every h≥⌈log⁡2ρ⌉h\ge\lceil\log_2\rho\rceil, since the excess only decreases at further levels. Every point of BB lies in at most half of its members, so every point of BhB^h lies in at most a fraction 2−h2^{-h} of the members, far below the fraction 1/ρ1/\rho that spread allows. So a spread family without two disjoint members need not have any point of degree at least ∣F∣/(Cρ)|\mathcal F|/(C\rho), however large CC is. A recursion in the style of Erdős and Rado, which passes to the link of a point of large degree and loses only a constant factor, therefore fails at its first step. The leaf ℓ\ell reached through xx at every level nevertheless carries a good link: it lies in exactly a fraction 2−h2^{-h} of the members, and since EBh(ρ)≤ρ2−hE_{B^h}(\rho)\le\rho2^{-h}, every UU outside ℓ\ell satisfies Pr⁡[U∪{ℓ}⊆S]≤2−hρ−∣U∣\Pr[U\cup\{\ell\}\subseteq S]\le2^{-h}\rho^{-|U|}. So the link at ℓ\ell, with its own uniform measure, is again normalized ρ\rho-spread, and it contains the sunflower petals above. The point that leads to a sunflower is light, but no superset of it is heavier relative to its size.

So a proof of SF(kk) must produce sunflowers with nonempty cores, and in some spread families with cores of unbounded size; the core cannot be bounded in terms of kk and the spread alone.

Open questions

  • The exact threshold for two disjoint members. Close the gap between clog⁡n/log⁡log⁡nc\log n/\log\log n and Clog⁡nC\log n. The lower order is known from the source comparison above and is also attained by the varying-scale construction. A seed with ρ(G)≥ρ\rho(G)\ge\rho, p1≤1/2p_1\le1/2 and uniformity eo(ρlog⁡ρ)e^{o(\rho\log\rho)} would improve the lower bound; the block seed needs ρρ\rho^\rho blocks because each member of its second kind contains a whole block. No seed can do much better: if ρ(G)≥ρ\rho(G)\ge\rho and p1≤1/2p_1\le1/2, then ψG(E)≤max⁡(E/2,E2/ρ)=E/2\psi_G(E)\le\max(E/2,E^2/\rho)=E/2 for E≤ρ/2E\le\rho/2, so GhG^h with h=⌈log⁡2ρ⌉h=\lceil\log_2\rho\rceil is normalized (ρ/2)(\rho/2)-spread, and the normalized cap of order log⁡n\log n above forces log⁡a≥cρ/log⁡ρ\log a\ge c\rho/\log\rho for the uniformity aa of an intersecting seed GG.
  • Many petals. For kk disjoint members the products of blocks of size k−1k-1 give spread k−1k-1, and the intersecting examples give clog⁡n/log⁡log⁡nc\log n/\log\log n. The combined dependence on kk and nn is not determined by these constructions.
  • A core-finding lemma. SF(kk) is equivalent to Problem 20. A route through spread families must replace M(k)M(k) by a statement that produces a sunflower with a nonempty and possibly large core when the family has no kk disjoint members. By L215 such a core can need about log⁡log⁡n/log⁡R\log\log n/\log R points; a single choice of a large core or a recursion into links would both be consistent with this obstruction. The proof sketch records the candidate statements and their status.