Sunflower-Free Uniform Families: Recursive Constructions and Explicit Bounds
Let f(w,k) be the maximum size of a w-uniform family with no k-sunflower. The work seeks better explicit lower and upper bounds for f(w,k), especially for small cases such as f(3,4), f(3,5), f(3,6), f(3,7) and f(4,3).
A recursive construction builds larger sunflower-free families from smaller ones while controlling the matching number, which gives a recurrence and an exponential lower bound on the growth rate. Upper bounds for triple families start from a maximum matching and use cross-intersecting graph lemmas together with incidence counting. The bounds f(3,4) ≤ 49 and f(4,3) ≤ 83 are computer-assisted, using SAT unsatisfiability certificates and exhaustive canonical-augmentation searches. The main arguments and the explicit witness families are formalised in Lean 4 with Mathlib; the exhaustive computations are checked separately and are outside the Lean development.
The bounds obtained are 39≤f(3,4)≤49, f(3,5)≤146, 153≤f(3,6)≤255, 259≤f(3,7)≤474 and 54≤f(4,3)≤83. The maximum size of an intersecting 4-uniform 3-sunflower-free family is shown to be exactly 27.
| Quantity | Published | Proved here |
|---|---|---|
| f(3,4) | 38 ≤ f ≤ 69 | 39 ≤ f ≤ 49 |
| f(3,5) | f ≤ 180 | f ≤ 146 |
| f(3,6) | 146 ≤ f ≤ 305 | 153 ≤ f ≤ 255 |
| f(3,7) | 252 ≤ f ≤ 498 | 259 ≤ f ≤ 474 |
| f(4,3) | 54 ≤ f ≤ 142 | 54 ≤ f ≤ 83 |