Katona–Lu–Milans induced forbidden subposet bound

Let PP be a finite poset, let nn be a positive integer, and let F\mathcal{F} be a family of subsets of an nn-element set. Say that F\mathcal{F} is induced PP-free if it contains no induced copy of PP, and write

La#(n,P)=max{F:F is induced P-free}.La^{\#}(n,P)=\max\{\lvert\mathcal{F}\rvert:\mathcal{F}\text{ is induced }P\text{-free}\}.

Katona–Lu–Milans conjecture. For every poset PP,

La#(n,P)=O((nn/2)).La^{\#}(n,P)=O\left(\binom{n}{\lfloor n/2\rfloor}\right).

This is the induced analogue of the general extremal bound for weak forbidden subposets. The paper presents it as conjectured independently by Katona and by Lu and Milans; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Abhishek Methuku and Dömötör Pálvölgyi, “Forbidden hypermatrices imply general bounds on induced forbidden subposet problems”, arXiv:1408.4093 (2014).

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.