Wiki
Wiki

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

Updated

Intersecting families with arbitrarily large spread

../

_proof: Substitution powers have an exactly computable spread; the two-star block family with m = rho^rho halves the excess at every level, and a random subfamily turns the normalized spread into the absolute form.

evidence/: Exact brute-force checks of the block-family bound, the substitution recursion and two small spread instances behind L214.


This result is recorded by Plasma AI. It refutes the constant-spread matching lemma behind one proposed route to Problem 20, the sunflower problem. It does not settle Problem 20. Its families are intersecting, so every sunflower they contain has a nonempty core; the later claim L215, which builds on these families shows that spread does not force a sunflower with a bounded core either. The proof builds the families, computes their spread exactly and thins them. The research account explains the mechanism, its limits and what it leaves open.

Significance

The existence of intersecting families with unbounded normalized spread is known. Alweiss–Lovett–Wu–Zhang's paper, Section 4 immediately after Theorem 4.2, records examples with spread Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n) and attributes them to Lovett–Solomon–Zhang, From DNF compression to sunflower theorems via regularity (2019). That cited construction has not been checked here. The contribution recorded on this page is the stated substitution construction, its exact recursion, and its conversion to absolute spread; no novelty is claimed for the existence or the lower asymptotic order.

A family of nn-sets is rr-spread in the absolute sense of Bell–Chueluecha–Warnke and of Rao when every nonempty TT lies in at most rn−∣T∣r^{n-|T|} members. Rao's Lemma 2 shows that more than rnr^n such sets contain pp pairwise disjoint sets when r=αplog⁡(pn)r=\alpha p\log(pn), and the source remarks that the lemma might hold with r=O(p)r=O(p), which would imply the sunflower conjecture through the link argument. The second part of this claim refutes that strengthening: for every real r≥16r\ge16 it gives more than rnr^n sets of size nn, rr-spread in that sense, no two of them disjoint. So for each constant CC the lemma fails with r=Cpr=Cp whenever Cp≥16Cp\ge16. In the normalized form of the first part the same holds for every threshold, since a ρ\rho-spread uniform measure is RR-spread for every R≤ρR\le\rho.

Quantitatively, log⁡2n=⌈log⁡2ρ⌉log⁡2(ρρ+1)\log_2n=\lceil\log_2\rho\rceil\log_2(\rho^\rho+1), so the first part gives intersecting families whose uniform measure is ρ\rho-spread with ρ=(1+o(1))log⁡2n/(log⁡2log⁡2n)2\rho=(1+o(1))\log_2n/(\log_2\log_2n)^2 along these nn. Bell–Chueluecha–Warnke's Lemma 2 shows that spread Clog⁡nC\log n forces two disjoint members, so the logarithm in that lemma cannot be removed. The known normalized examples just cited, or the varying-scale construction and general thinning argument in the research note, give the stronger comparison log⁡n/log⁡log⁡n\log n/\log\log n.

The product family of all transversals of nn blocks, recorded in the finite-set threshold note, shows that constant spread cannot force a member inside an independent random subset; it has disjoint members, so it does not obstruct the matching lemma. The families here obstruct the matching lemma itself.

Standing and verification

Tier 0, author-recorded. The proof is complete and elementary. The first part is deterministic. The second part is a first-moment argument over a random subfamily, with explicit constants. No independent review and no formalization exist.

The evidence program checks the finite content of the lemmas. It builds the block families B(ρ,m)B(\rho,m) for (ρ,m)(\rho,m) in (2,2)(2,2), (2,3)(2,3), (2,4)(2,4), (2,5)(2,5), (3,3)(3,3), (3,4)(3,4), (3,5)(3,5) and (4,4)(4,4) and checks their size, uniformity, intersection and containment bound, with its equality case. It checks the exact spread recursion on five substitutions at five rates, in exact rational arithmetic. It also checks two small instances of the conclusion: B(2,4)B(2,4), the family of the statement at ρ=2\rho=2, and B(2,2)2B(2,2)^2. It does not check the statement for general ρ\rho or the thinning part. From the repository root, run

sh
uv run --no-sync python wiki/theory/set_systems/L214_spread_intersecting_families/evidence/main.py

which takes a few seconds and exits with status 0 when every check passes.

Nothing remains open within the stated scope.