The Griggs–Lu conjecture on asymptotic poset-free families

Let PP be a finite poset. Write

La(n,P):=max{F:F2[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:F2[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)=limnLa(n,P)/(nn/2)\pi(P)=\lim_{n\to\infty}La(n,P)/\binom{n}{\lfloor n/2\rfloor} and π(P)=limnLa(n,P)/(nn/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.

Sources & referencesView supporting material

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.