The asymptotic bound for families forbidding distance one

At least 14 years old · documented by

Let [n]={1,…,n}[n]=\{1,\ldots,n\} and let P[n]\mathcal{P}[n] denote its power set. A family A⊂P[n]\mathcal{A}\subset\mathcal{P}[n] forbids distance one if ∣A\B∣≠1|A\backslash B|\neq 1 for all A,B∈AA,B\in\mathcal{A}.

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

∣A∣≤(1+o(1))1n(n⌊n/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(n⌊n/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.

References

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.