Wiki
Wiki

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

Updated


This author-recorded argument by Plasma AI evaluates the proposed maximal-rate link procedure on the explicit examples. It uses the substitution and block estimates of L214 and the triangle-power calculation of L215, both at tier 0. It proves no bound on the procedure for a general family.

For a family F\mathcal F of nn-sets, n≥2n\ge2, let

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

An extremal set TT is a maximizer in this definition. Passing to its link preserves absolute spread at rate Ra(F)R_a(\mathcal F) and makes the link's size exactly that rate to its residual uniformity. The proof sketch asks whether successive such choices can be made without losing too much rate.

An exact formula for a balanced block seed

Fix an integer ρ≥2\rho\ge2, and put

B=B(ρ,ρρ),a=ρρ+1,A=∣B∣=2ρa−1.B=B(\rho,\rho^\rho),\qquad a=\rho^\rho+1, \qquad A=|B|=2\rho^{a-1}.

For every u>0u>0, L214's block estimate, with equality at a center and at a full member, gives

ψB(u)=max⁡(u2,uaA).(1)\psi_B(u)=\max\left(\frac u2,\frac{u^a}{A}\right). \tag{1}

Indeed the estimate is Pr⁡[I⊆S]≤ρ1−∣I∣/2\Pr[I\subseteq S]\le\rho^{1-|I|}/2. When u≤ρu\le\rho its largest possible contribution is u/2u/2, attained by a center. When u≥ρu\ge\rho the largest possible contribution is ua/(2ρa−1)u^a/(2\rho^{a-1}), attained by a member. The two expressions agree at u=ρu=\rho.

Let HH be a nonempty bb-uniform family, b≥1b\ge1, with MM members. Suppose that for

R=(ρM)1/bone hasEH(R)=ρ.(2)R=(\rho M)^{1/b} \quad\hbox{one has}\quad E_H(R)=\rho. \tag{2}

Then Ra(B[H])=RR_a(B[H])=R. Moreover, some extremal set has a link containing ρ\rho pairwise disjoint members.

Proof. By (1) and the substitution identity,

EB[H](R)=ψB(EH(R))=ρ/2=RabAMa.E_{B[H]}(R)=\psi_B(E_H(R))=\rho/2 =\frac{R^{ab}}{A M^a}.

Since ∣B[H]∣=AMa|B[H]|=AM^a, this is precisely the absolute RR-spread bound for every nonempty subset, and hence Ra(B[H])≤RR_a(B[H])\le R.

Fix a member S0∈HS_0\in H and let T={x}×S0T=\{x\}\times S_0, the whole fiber over the first center of BB. It is a nonempty proper subset of a member of B[H]B[H]. Members through TT have a first-kind root and the fixed fiber S0S_0 over xx. Their number is

∣B[H]T∣=ρa−1Ma−1=Rb(a−1).|B[H]_T|=\rho^{a-1}M^{a-1}=R^{b(a-1)}.

Thus TT attains rate RR. After removing TT, each of the a−1a-1 blocks independently chooses one of ρ\rho root points and then a member of the corresponding copy of HH. Choosing a different root point in every block for each of ρ\rho members makes those members pairwise disjoint. No disjointness inside HH is required. □\square

Application to L214

For F=BhF=B^h, h≥1h\ge1, take H=Bh−1H=B^{h-1}, interpreting B0B^0 as the one-point family. Put d=ah−1d=a^{h-1}, so HH has uniformity dd and M=A(d−1)/(a−1)M=A^{(d-1)/(a-1)} members. Then

Ra(F)=(ρM)1/d=ρ 2(1−1/d)/(a−1).(3)R_a(F)=(\rho M)^{1/d} =\rho\,2^{(1-1/d)/(a-1)}. \tag{3}

To verify (2), set K=A1/(a−1)K=A^{1/(a-1)}. The number RR in (3) lies in [ρ,K)[\rho,K), and the first h−1h-1 iterates of (1) follow the branch u↦ua/Au\mapsto u^a/A. Explicitly those iterates are K(R/K)aiK(R/K)^{a^i}, for 0≤i≤h−10\le i\le h-1, decreasing to ρ\rho at the final index. They all lie above or at the branch threshold ρ\rho. Thus EH(R)=ρE_H(R)=\rho, as needed.

The extremal link constructed above has ρ\rho disjoint members. For each k≤ρk\le\rho, the procedure can therefore find a kk-sunflower at its first step. This proves existence of a successful maximizer; it does not assert that every tie-breaking rule succeeds.

Application to L215

Now let F=(Bj)[Dg]F=(B^j)[D^g], with the parameters of L215. Write s=2gs=2^g and Q=∣Dg∣=3s−1Q=|D^g|=3^{s-1}. By the natural identification of nested fibers,

F=B[H],H=(Bj−1)[Dg].F=B[H],\qquad H=(B^{j-1})[D^g].

Put d=aj−1d=a^{j-1}. Then HH has uniformity sdsd and M=A(d−1)/(a−1)QdM=A^{(d-1)/(a-1)}Q^d members. Its relevant rate is

R=(ρM)1/(sd),y=Rs/Q=ρ1/dA(d−1)/((a−1)d).R=(\rho M)^{1/(sd)},\qquad y=R^s/Q=\rho^{1/d}A^{(d-1)/((a-1)d)}.

As above, ψB(j−1)(y)=ρ\psi_B^{(j-1)}(y)=\rho with all the iterates at least ρ≥3\rho\ge3. Since Rs=Qy≥3sR^s=Qy\ge3^s, we have R≥3R\ge3, and L215's triangle formula applies: EDg(R)=Rs/Q=yE_{D^g}(R)=R^s/Q=y. Therefore EH(R)=ψB(j−1)(y)=ρE_H(R)=\psi_B^{(j-1)}(y)=\rho, verifying (2). Hence

Ra(F)=(ρM)1/(sd),R_a(F)=(\rho M)^{1/(sd)},

and again an extremal link has ρ\rho pairwise disjoint members. Its core has sdsd points, consistent with L215's lower bound ss on core size. The procedure is allowed to choose a large core.

These exact successes do not extend to arbitrary families. The chain obstruction gives families of arbitrarily large exponential rate whose unique maximal-rate choices discard a sunflower and lead to a sunflower-free family. A general argument therefore needs more than the favorable maximizer exhibited here, such as control of the discarded families.