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

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 $(\pi(P)+o(1))M_n$ for a constant $\pi(P)$, where $M_n=\binom n{\lfloor n/2\rfloor}$, and that the number of $P$-free subfamilies is $2^{(\pi(P)+o(1))M_n}$. For connected $P$ we prove supersaturation above $(\pi(P)+\epsilon)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 $(\pi(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 $\pi_d=\pi(Q_d)$ satisfies $(d+1)\lambda_d\le\pi_d\le d+1-\binom d{\lfloor d/2\rfloor}^{-1}$, where $\lambda_d$ is the vertex Tur\'an density of $d$-dimensional subcubes in the hypercube. Together with a construction of Ellis, Ivan and Leader this gives $d+1-\pi_d=\exp(-\Theta(d))$. For the diamond, known bounds give $2.1479\le\pi_2\le2.15121$.