Forbidden graded posets in middle levels: supersaturation, enumeration and randomness

Source abstract

Let $P$ be a fixed finite poset whose maximal chains all have $h$ elements, and let $\mathcal W_{n,h}$ be the union of $h$ consecutive middle levels of $2^{[n]}$. We prove that the maximum size of a $P$-free subfamily of $\mathcal W_{n,h}$ is $(π(P)+o(1))M_n$ for a constant $π(P)$, where $M_n=\binom n{\lfloor n/2\rfloor}$, and that the number of $P$-free subfamilies is $2^{(π(P)+o(1))M_n}$. For connected $P$ we prove supersaturation above $(π(P)+ε)M_n$ and determine, in terms of the coordinate patterns of the copies of $P$ in the window, a range of $p$ in which the largest $P$-free subfamily of the random family $\mathcal W_{n,h}(p)$ has size $(π(P)+o(1))pM_n$ and a range in which it has size $(h+o(1))pM_n$; the two ranges meet whenever all copies have the same pattern. For the Boolean poset $Q_d$, which has height $d+1$, the threshold order in the corresponding window $\mathcal W_{n,d+1}$ is $n^{-d/(2^d-1)}$, and $π_d=π(Q_d)$ satisfies $(d+1)λ_d\leπ_d\le d+1-\binom d{\lfloor d/2\rfloor}^{-1}$, where $λ_d$ is the vertex Turán density of $d$-dimensional subcubes in the hypercube. Together with a construction of Ellis, Ivan and Leader this gives $d+1-π_d=\exp(-Θ(d))$. For the diamond, known bounds give $2.1479\leπ_2\le2.15121$.