The level-count conjecture for forbidden subposets

From papers

Let PPsubseteq be a finite poset. Let Mon(Z)\operatorname{Mon}(\mathbb{Z}) be the set of functions f ⁣:Z{0,1}f\colon\mathbb{Z}\to\{0,1\} such that f(n)=1f(n)=1 and f(n)=0f(-n)=0 for all sufficiently large nn, ordered pointwise. A level is a maximal family LMon(Z)L\subset\operatorname{Mon}(\mathbb{Z}) on which nf(n)g(n)=0\sum_n f(n)-g(n)=0 for every f,gLf,g\in L. Define l(P)l(P) to be the maximum number of levels whose union does not contain PP as a subposet. Level-count conjecture. For every finite poset PP,

ex(P,n)=l(P)(nn/2)(1+O(1/n)).\operatorname{ex}(P,n)=l(P)\binom{n}{\lfloor n/2\rfloor}\bigl(1+O(1/n)\bigr).

This conjecture proposes a common asymptotic explanation for several known forbidden-subposet results, including those for chains, brooms, butterflies, and loops on adjacent levels of the Boolean lattice. Its general validity is not established by the surrounding discussion.

Progress summary

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

Sources & referencesView supporting material

Primary source

Boris Bukh, “Set families with a forbidden subposet”, arXiv:0803.3840 (2009).

Solutions 0

No solutions have been posted yet.