The Griggs–Lu conjecture on asymptotic poset-free families

At least 15 years old · documented by

Let PP be a finite poset. Write

La(n,P):=max⁡{∣F∣:F⊆2[n], F is P-free}La(n,P):=\max\{|\mathcal F|:\mathcal F\subseteq 2^{[n]},\ \mathcal F\text{ is }P\text{-free}\}

and

La∗(n,P):=max⁡{∣F∣:F⊆2[n], F is induced P-free}.La^*(n,P):=\max\{|\mathcal F|:\mathcal F\subseteq 2^{[n]},\ \mathcal F\text{ is induced }P\text{-free}\}.

Define π(P)=lim⁡n→∞La(n,P)/(n⌊n/2⌋)\pi(P)=\lim_{n\to\infty}La(n,P)/\binom{n}{\lfloor n/2\rfloor} and π∗(P)=lim⁡n→∞La∗(n,P)/(n⌊n/2⌋)\pi^*(P)=\lim_{n\to\infty}La^*(n,P)/\binom{n}{\lfloor n/2\rfloor} when these limits exist. For a positive integer kk, the family ⋃i=1k([n]j+i)\bigcup_{i=1}^k\binom{[n]}{j+i} is the union of kk consecutive layers of 2[n]2^{[n]}. Griggs–Lu conjecture. (i) For any poset PP, let e(P)e(P) denote the largest integer kk such that, for every jj and nn, the family ⋃i=1k([n]j+i)\bigcup_{i=1}^k\binom{[n]}{j+i} is PP-free. Then π(P)\pi(P) exists and equals e(P)e(P). (ii) For any poset PP, let e∗(P)e^*(P) denote the largest integer kk such that, for every jj and nn, the family ⋃i=1k([n]j+i)\bigcup_{i=1}^k\binom{[n]}{j+i} is induced PP-free. Then π∗(P)\pi^*(P) exists and equals e∗(P)e^*(P). The conjecture proposes that the asymptotic extremal sizes are obtained by taking as many consecutive middle layers as possible without creating a (induced) copy of PP. The limits and equalities are known in many classes of posets, but remain unsettled in general.

References

Primary source

Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Balázs Patkós and Máté Vizer, “Forbidding rank-preserving copies of a poset”, arXiv:1710.09086 (2017).

Additional references

7 papers in this index state this conjecture (2010–2017). The statement above is taken from the most recent of them; the others are arXiv:1706.01212, arXiv:1701.05030, arXiv:1605.00373, arXiv:1301.1870, arXiv:1208.4241, arXiv:1010.5311.

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.