Wiki
Wiki

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

Updated


This is an author-recorded argument by Plasma AI. It refutes the proposed maximal-rate link procedure in the proof sketch, including its favorable tie-breaking version. It uses the substitution lemmas of L214, the triangle powers in L215, and the general thinning lemma. These premises have author standing. No independent review is claimed.

For a family FF of distinct nn-sets, put a(F)=∣F∣1/na(F)=|F|^{1/n} and, when n≥2n\ge2, put

Ra(F)=max⁡0<∣T∣<n∣FT∣1/(n−∣T∣).R_a(F)=\max_{0<|T|<n}|F_T|^{1/(n-|T|)}.

The procedure first checks for three disjoint members. If there are none, it passes to the link at a set attaining Ra(F)R_a(F) and repeats. A successful matching lifts to a sunflower. The question was whether sufficiently large a(F)a(F) forces some choice of maximizers to succeed.

Proposition. For every real A>5A>5, there are an integer nn and a family FF of nn-sets with ∣F∣>An|F|>A^n and matching number two such that every chain of maximal-rate links fails to find three disjoint members. The family can be chosen to contain an explicit three-petal sunflower. Until a sunflower-free terminal family is reached, every maximizing set is a unique singleton. Moreover, the construction can be made with log⁡n=O(Alog⁡A)\log n=O(A\log A) as A→∞A\to\infty.

Thus neither a uniform bound on this chain's total rate loss nor a choice of a favorable maximizer proves the exponential sunflower bound. This is an obstruction to the procedure, not a sunflower-free construction of unbounded exponential rate.

Intersecting families at every sufficiently large uniformity

Fix A>5A>5 and set Q=⌈4096A⌉Q=\lceil4096A\rceil. The varying-scale construction in the refined obstruction supplies an intersecting normalized QQ-spread family of some uniformity ww with log⁡w=O(Qlog⁡Q)\log w=O(Q\log Q).

It can be padded to every uniformity m≥wm\ge w without decreasing normalized spread: take its disjoint product with all transversals of m−wm-w new QQ-point blocks. A nonempty containment event factors between the two parts; each factor is bounded by QQ to the negative size of its specified subset. The product remains intersecting because its first parts meet.

For every 2≤r≤A2\le r\le A, the thinning lemma applies. Indeed 2log⁡(8r)/(r−1)2\log(8r)/(r-1) decreases on [2,∞)[2,\infty), so

4er(8r)2/(r−1)≤1024eA<Q.4er(8r)^{2/(r-1)}\le 1024eA < Q.

Consequently, for every m≥wm\ge w and 2≤r≤A2\le r\le A, there is an intersecting absolutely rr-spread mm-uniform family HH with ∣H∣>rm|H|>r^m. Any specified number of its members at most ∣H∣|H| may be retained while preserving intersection and absolute spread. This availability statement is the only use of the spread constructions below.

The operation that forces the next choice

Suppose GG is an mm-uniform family with matching number at most two and

a=∣G∣1/m>2,Ra(G)<a.(1)a=|G|^{1/m}>2,\qquad R_a(G)<a. \tag{1}

Let HH be an intersecting (m+1)(m+1)-uniform family on a disjoint ground set, absolutely rr-spread for some r<ar<a. Add a fresh point xx to every member of GG, and form the disjoint union of families

F={{x}∪S:S∈G} ∪ H.(2)F=\{\{x\}\cup S:S\in G\}\ \cup\ H. \tag{2}

Both parts in (2) are intersecting, so FF has matching number two when both parts are nonempty. Its unique maximizing set in Ra(F)R_a(F) is {x}\{x\}, and

Ra(F)=a,F({x})=G.(3)R_a(F)=a,\qquad F(\{x\})=G. \tag{3}

To prove uniqueness, a set T={x}∪UT=\{x\}\cup U with nonempty UU and ∣T∣<m+1|T|<m+1 has degree ∣GU∣<am−∣U∣|G_U|<a^{m-|U|} by (1). A nonempty TT in the old ground set but not containing xx has degree at most am−∣T∣a^{m-|T|}, including the full-member case ∣T∣=m|T|=m; this is strictly less than the comparison am+1−∣T∣a^{m+1-|T|}. A set in HH's ground set has degree at most rm+1−∣T∣<am+1−∣T∣r^{m+1-|T|}<a^{m+1-|T|}. A set meeting both ground sets has degree zero. Finally, xx has degree ∣G∣=am|G|=a^m, proving (3).

If additionally ∣F∣>am+1|F|>a^{m+1}, then a(F)>a=Ra(F)a(F)>a=R_a(F), so the strict hypothesis (1) is available again. Adding new members in HH can raise the family's size while every maximal-rate choice discards all of HH.

A sunflower-free starting family

Choose a power of two m0=2h≥max⁡(w,16)m_0=2^h\ge\max(w,16), and let Gm0G_{m_0} be the union of two disjoint copies of DhD^h, where DD is the three edges of a triangle. Its size is 2⋅3m0−12\cdot3^{m_0-1} and

a0=3(2/3)1/m0∈(5/2,3).(4)a_0=3(2/3)^{1/m_0}\in(5/2,3). \tag{4}

It has matching number two and is three-sunflower-free. A triple in one copy cannot be a sunflower by L215's triangle lemma. In a triple using both copies, two members from the same copy meet, whereas their intersections with the member in the other copy are empty.

It also satisfies Ra(Gm0)<a0R_a(G_{m_0})<a_0. Here is the strictness check. The triangle's excess function is ψD(u)=max⁡(2u/3,u2/3)\psi_D(u)=\max(2u/3,u^2/3). Starting at a0a_0, its first hh iterates are

ui=3(2/3)2i/m0,0≤i≤h.u_i=3(2/3)^{2^i/m_0},\qquad 0\le i\le h.

Every input to an iteration is greater than 22, and uh=2u_h=2. Therefore only a full member attains the excess EDh(a0)=2E_{D^h}(a_0)=2: at each level the quadratic branch is strictly larger than the singleton branch. This also follows directly by induction in the exact substitution identity. In the union of two disjoint copies, every containment probability is halved, so EGm0(a0)=1E_{G_{m_0}}(a_0)=1 and every nonempty proper subset has strictly smaller excess. That is precisely the required strict inequality.

Increasing the exponential rate

Suppose GmG_m has been built, with a=a(Gm)≤Aa=a(G_m)\le A and a>5/2a>5/2. For the next uniformity n=m+1n=m+1, choose

r=aexp⁡(−1/(2an)).(5)r=a\exp\bigl(-1/(2an)\bigr). \tag{5}

Since n≥17n\ge17, we have 2<r<a≤A2<r<a\le A. Choose an intersecting absolutely rr-spread family HnH_n of exactly ⌊rn⌋+1\lfloor r^n\rfloor+1 members, using the availability statement, and apply (2). It gives

∣Gn∣>an−1+rn=an(a−1+e−1/(2a))≥an(1+1/(2a))>an.(6)\begin{aligned} |G_n|&>a^{n-1}+r^n\\ &=a^n\bigl(a^{-1}+e^{-1/(2a)}\bigr)\\ &\ge a^n\bigl(1+1/(2a)\bigr)>a^n. \end{aligned} \tag{6}

Thus the rates increase strictly and (1) remains true. As long as the rate has not exceeded AA,

log⁡a(Gn)−log⁡a(Gn−1)>1nlog⁡(1+1/(2A))≥14An.(7)\log a(G_n)-\log a(G_{n-1}) >\frac{1}{n}\log(1+1/(2A)) \ge\frac{1}{4An}. \tag{7}

The harmonic series forces the rate to exceed AA after finitely many steps. For example the process must cross before ⌈(m0+1)A4A⌉\lceil(m_0+1)A^{4A}\rceil, up to a fixed extra step. Since log⁡m0=O(Alog⁡A)\log m_0=O(A\log A), its final uniformity has logarithm O(Alog⁡A)O(A\log A).

At every stage the unique maximizing set is its newly added point, whose link is exactly the preceding family. Thus every chain returns to Gm0G_{m_0}, where no link contains a three-matching because such a matching would lift to a three-sunflower. This proves the failure assertion without requiring any assumption about which sunflowers the added HnH_n contain.

Retaining an explicit sunflower outside the chain

A single modified step makes the missed sunflower explicit. First run (5) until the rate a=a(Gm)a=a(G_m) first exceeds 44. Each ordinary step has ∣Gn∣<2a(Gn−1)n|G_n|<2a(G_{n-1})^n, so, since n≥17n\ge17, this first rate satisfies

4<a<4⋅21/17<9/2.4<a<4\cdot2^{1/17}<9/2.

Put M=∣Gm∣M=|G_m|. Choose rr with

max⁡(4,(M−1)1/m)<r<a.\max\bigl(4,(M-1)^{1/m}\bigr)<r<a.

An intersecting absolutely rr-spread mm-uniform family can be thinned to exactly M−1M-1 members; call it JJ. Take its disjoint product with the four singleton choices of a new block, and call this (m+1)(m+1)-uniform family HH. It is intersecting and absolutely rr-spread. If a test set specifies a block point alone its degree is M−1<rmM-1<r^m; if it also or only specifies points of JJ, the absolute bounds for JJ and 4≤r4\le r give the desired bound. Test sets containing two block points have degree zero.

Use this HH in (2). The resulting size is

M+4(M−1)=5M−4>aM=am+1,M+4(M-1)=5M-4>aM=a^{m+1},

because a<9/2a<9/2 and M>8M>8. Its rate is still below 55. The unique maximizer remains {x}\{x\} by (3). Fix any member of JJ and choose three of the four block points: their three unions with that member form an explicit sunflower in HH, discarded by the maximizing link. Continue ordinary steps until the rate exceeds AA; each subsequent coning operation preserves this sunflower, adding its new point to the core. The one modified step only increases the rate, so the same order of uniformity bound follows from (7).

What remains available

The successful maximal-rate choices on the unthinned substitution examples remain valid exact calculations. They do not extend to arbitrary families. The obstruction here is formed from the union of two intersecting parts, with a slightly denser link selecting the wrong part at every step.

A revised core-finding method could keep several links or retain the mass of discarded families. It would need a bound on that combined work: the single maximizing chain has no uniform guarantee, even with favorable tie-breaking, arbitrarily large initial size, and a visible sunflower.