Wiki
Wiki

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

Updated


These are author-recorded deductions by Plasma AI. They use the elementary substitution and block-family lemmas in the proof of L214, at tier 0. They sharpen this substitution construction's obstruction to finding disjoint members from spread alone and transfer L215's large-core construction to the absolute convention. They do not produce sunflower-free families of unbounded exponential rate, and hence do not settle Problem 20.

The order log⁡n/log⁡log⁡n\log n/\log\log n for intersecting normalized-spread families is already recorded by Alweiss–Lovett–Wu–Zhang, Section 4 after Theorem 4.2, with attribution to Lovett–Solomon–Zhang (2019). The derivation below is an alternative construction at that known order, not an improved lower bound over the literature. The cited original construction is not a premise of this proof and has not been checked here.

Decrease the scale after each contraction

For an integer R≥2R\ge2, put h=⌈log⁡2R⌉h=\lceil\log_2R\rceil and

qi=⌈R/2i⌉,Bi=B(qi,qiqi),0≤i<h.q_i=\left\lceil R/2^i\right\rceil,\qquad B_i=B(q_i,q_i^{q_i}),\qquad 0\le i<h.

Every qi≥2q_i\ge2. Start with the family F0F_0 whose only member is a one-point set, and define Fi+1=Bi[Fi]F_{i+1}=B_i[F_i]. By L214's substitution lemma, every FiF_i is intersecting. With EE denoting normalized excess, the block lemma gives

EFi+1(R)=ψBi(EFi(R))≤12EFi(R)whenever EFi(R)≤qi.E_{F_{i+1}}(R)=\psi_{B_i}(E_{F_i}(R))\le\tfrac12E_{F_i}(R) \quad\hbox{whenever }E_{F_i}(R)\le q_i.

Starting from EF0(R)=RE_{F_0}(R)=R, induction gives EFi(R)≤R/2i≤qiE_{F_i}(R)\le R/2^i\le q_i for each required step. Thus FhF_h is an intersecting normalized RR-spread family, of uniformity

nR=∏i=0h−1(qiqi+1).(1)n_R=\prod_{i=0}^{h-1}(q_i^{q_i}+1). \tag{1}

In fact the excess halves exactly: the center of the first kind attains ψBi(u)=u/2\psi_{B_i}(u)=u/2 on 0<u≤qi0<u\le q_i.

This choice avoids paying the largest block scale at every level. In natural logarithms,

log⁡nR=2Rlog⁡R−2Rlog⁡2+O((log⁡R)2).(2)\log n_R=2R\log R-2R\log2+O((\log R)^2). \tag{2}

To check (2), write xi=R/2ix_i=R/2^i. Replacing xix_i by its ceiling in xilog⁡xix_i\log x_i changes each summand by O(log⁡R)O(\log R), over O(log⁡R)O(\log R) indices. Also log⁡(qiqi+1)=qilog⁡qi+O(1)\log(q_i^{q_i}+1)=q_i\log q_i+O(1), and the omitted tail of the infinite sum ∑i≥0xilog⁡xi\sum_{i\ge0}x_i\log x_i is bounded. The geometric identities ∑2−i=2\sum2^{-i}=2 and ∑i2−i=2\sum i2^{-i}=2 give (2).

Consequently, along the uniformities (1), the spread is

R=(12+o(1))log⁡nRlog⁡log⁡nR.(3)R=\left(\frac12+o(1)\right) \frac{\log n_R}{\log\log n_R}. \tag{3}

Thus the lower obstruction is of order log⁡n/log⁡log⁡n\log n/\log\log n, rather than the order log⁡n/(log⁡log⁡n)2\log n/(\log\log n)^2 obtained by using the same block family at every level. This concerns matching thresholds, not the exponential base needed for sunflower existence.

Thinning without a family-size cap

Thinning lemma. Let r≥2r\ge2 and n≥2n\ge2, and suppose a nonempty family H\mathcal H of distinct nn-sets is normalized QQ-spread. If

Q≥4er(8r)2/(r−1),(4)Q\ge4er(8r)^{2/(r-1)}, \tag{4}

then it has a subfamily H′\mathcal H' with ∣H′∣>rn|\mathcal H'|>r^n and ∣HT′∣≤rn−∣T∣|\mathcal H'_T|\le r^{n-|T|} for every nonempty TT. In particular, Q≥32rQ\ge32r suffices when r≥16r\ge16.

There is no upper bound on ∣H∣|\mathcal H| or its ground-set size in this statement. All properties inherited by subfamilies, such as being intersecting or excluding specified sunflower core sizes, survive.

Proof. Write M=∣H∣M=|\mathcal H|. The normalized bound at a member gives M≥QnM\ge Q^n. Keep each member independently with probability p=2rn/M<1p=2r^n/M<1. The resulting size has mean 2rn2r^n and

Pr⁡(∣H′∣≤rn)≤e−rn/4≤e−1.(5)\Pr(|\mathcal H'|\le r^n)\le e^{-r^n/4}\le e^{-1}. \tag{5}

For 1≤t<n1\le t<n, put at=⌊rn−t⌋a_t=\lfloor r^{n-t}\rfloor and dT=∣HT∣d_T=|\mathcal H_T| for a tt-set TT. A bad set has at least at+1a_t+1 retained members through it. Counting these witnesses, and first distinguishing one of their original members, gives

Pr⁡(∃T, ∣T∣=t: ∣HT′∣>rn−t)≤∑∣T∣=tpat+1(dTat+1)≤∑∣T∣=tp dT(epdTat)at≤2rn(nt)(4e(r/Q)t)at.(6)\begin{aligned} \Pr(\exists T,\ |T|=t:\ |\mathcal H'_T|>r^{n-t}) &\le\sum_{|T|=t}p^{a_t+1}\binom{d_T}{a_t+1}\\ &\le\sum_{|T|=t}p\,d_T \left(\frac{epd_T}{a_t}\right)^{a_t}\\ &\le 2r^n\binom nt \left(4e(r/Q)^t\right)^{a_t}. \end{aligned} \tag{6}

For the last step use dT≤MQ−td_T\le M Q^{-t}, ∑∣T∣=tdT=M(nt)\sum_{|T|=t}d_T=M\binom nt, and at≥(1−1/r)rn−ta_t\ge(1-1/r)r^{n-t}. The sum over TT is finite; sets outside all members have dT=0d_T=0. The identity for the sum of dTd_T replaces the cruder estimate counting every possible TT separately.

Set δ=log⁡(Q/(4er))>0\delta=\log(Q/(4er))>0. Since 4e(r/Q)t≤(4er/Q)t4e(r/Q)^t\le(4er/Q)^t, and since

tat≥(1−1/r)trn−t≥(n−1)(r−1),t a_t\ge (1-1/r)t r^{n-t}\ge(n-1)(r-1),

the sum of (6) over 1≤t<n1\le t<n is at most

2(2r)nexp⁡[−δ(n−1)(r−1)]≤2(2r)n(8r)−n=2 4−n≤18.(7)2(2r)^n\exp[-\delta(n-1)(r-1)] \le2(2r)^n(8r)^{-n} =2\,4^{-n}\le\frac18. \tag{7}

Here trn−tt r^{n-t} is nonincreasing for 1≤t<n1\le t<n when r≥2r\ge2, and (4) gives δ(r−1)≥2log⁡(8r)\delta(r-1)\ge2\log(8r). There is no bad set of size nn, because each nn-set is contained in at most one distinct member, and larger sets have degree zero. Equations (5) and (7) have sum less than one, proving existence.

Finally, 2log⁡(8r)/(r−1)2\log(8r)/(r-1) decreases for r≥2r\ge2, and at r=16r=16 it is less than log⁡(8/e)\log(8/e). Thus 32r32r satisfies (4) for all r≥16r\ge16. □\square

The lemma generalizes the use of random thinning in L214's Lemma 4. That lemma's stated hypotheses and proof remain sufficient for L214 itself; the estimate above additionally applies when the original family has arbitrarily many members.

Consequences in the absolute convention

For every real r≥2r\ge2, choose an integer RR satisfying (4), and apply the first construction followed by the thinning lemma. This gives an intersecting absolutely rr-spread family of nRn_R-sets with more than rnRr^{n_R} members. If r≥16r\ge16, one may take R=⌈32r⌉R=\lceil32r\rceil; (2) then gives intersecting absolute-spread examples at spread of order log⁡nR/log⁡log⁡nR\log n_R/\log\log n_R.

The quantifier matters for the proposed matching lemma. For every fixed k≥3k\ge3 and every real r>0r>0, the assertion that every absolutely rr-spread nn-uniform family with more than rnr^n members contains kk disjoint members fails for some nn. If r<k−1r<k-1, take k−1k-1 singletons; if r≥k−1≥2r\ge k-1\ge2, use the intersecting construction just given. For k=2k=2 the same construction refutes every r≥2r\ge2. It does not refute r=1r=1: absolute 11-spread itself forces distinct members to be disjoint. This degenerate case must not be included in a claim that all absolute matching constants fail.

For large cores, let r≥2r\ge2 and g≥0g\ge0. Choose Q≥3Q\ge3 satisfying (4), and apply L215 at normalized spread QQ. Its family consists of nn-sets for n≥2n\ge2, is intersecting, and has no kk-sunflower with core smaller than 2g2^g for any k≥3k\ge3. The thinning lemma produces an absolutely rr-spread subfamily with more than rnr^n members and exactly the same exclusion. Thus a bounded-core replacement for the matching lemma fails in the absolute convention as well.

These conclusions do not rule out finding a sunflower with an unbounded core. The remaining obligation is the general core-finding argument in the proof sketch.