The level-count conjecture for forbidden subposets

About 18 years old · traced to

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 L⊂Mon⁡(Z)L\subset\operatorname{Mon}(\mathbb{Z}) on which ∑nf(n)−g(n)=0\sum_n f(n)-g(n)=0 for every f,g∈Lf,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)(n⌊n/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.

References

Primary source

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

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.