Wiki
Wiki

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

Updated


Source. Published p. 261, Theorem 1.1, and p. 271 (PDF).

Statement. For each 0<η<1/40<\eta<1/4 there is ϵ>0\epsilon>0 such that if ηn<l<(1/2−η)n\eta n<l<(1/2-\eta)n is an integer and a family F⊆2[n]\mathcal F\subseteq2^{[n]} has no distinct members intersecting in exactly ll points, then ∣F∣≤(2−ϵ)n|\mathcal F|\le(2-\epsilon)^n. The conclusion also holds under the stronger convention forbidding the intersection for every ordered pair, including the diagonal.

Proof. Under the stronger convention apply theorem_1_4 to two copies of F\mathcal F and take square roots.

Under the distinct-member convention, remove the sets of size exactly ll. The remaining family has no forbidden cross pair even on the diagonal, so its size is at most 2ne−cn/22^n e^{-cn/2}. The removed layer has at most 2nH(l/n)≤2nH(1/2−η)2^{nH(l/n)}\le2^{nH(1/2-\eta)} members. Since H(1/2−η)<1H(1/2-\eta)<1, their sum is bounded by (2−ϵ)n(2-\epsilon)^n for some ϵ>0\epsilon>0 and sufficiently large nn. The finitely many smaller admissible n,ln,l can be included by reducing ϵ\epsilon: the full cube contains distinct sets with intersection ll, so its size cannot be attained by an avoiding family. □\square

Source precision. The source defines the extremal quantity using distinct members, then says simply to set the two families equal. The layer deletion above makes that diagonal issue explicit.

Bears on. #703, specifically its proportional forbidden-intersection question. This source page makes no new status claim about other parameter regimes in that problem.

Dependencies. theorem_1_4, entropy_estimates.