The asymptotic bound for families forbidding distance one

Let [n]={1,,n}[n]=\{1,\ldots,n\} and let P[n]\mathcal{P}[n] denote its power set. A family AP[n]\mathcal{A}\subset\mathcal{P}[n] forbids distance one if A\B1|A\backslash B|\neq 1 for all A,BAA,B\in\mathcal{A}.

Distance-one extremal conjecture. Every family AP[n]\mathcal{A}\subset\mathcal{P}[n] that forbids distance one satisfies

A(1+o(1))1n(nn/2).|\mathcal{A}|\leq (1+o(1))\frac{1}{n}\binom{n}{\lfloor n/2\rfloor}.

The paper gives a family of at least 1n(nn/2)\frac{1}{n}\binom{n}{\lfloor n/2\rfloor} sets by selecting a residue class of the sum of the elements among the middle-level sets, and suspects that this lower bound is asymptotically best.

Sources & referencesView supporting material

Primary source

Imre Leader and Eoin Long, “Tilted Sperner Families”, arXiv:1101.4151 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.