Supersaturation, Counting, and Randomness in Forbidden Subposet Problems

Abstract

In the area of forbidden subposet problems we look for the largest possible size $La(n,P)$ of a family $\mathcal{F}\subseteq 2^{[n]}$ that does not contain a forbidden inclusion pattern described by $P$. The main conjecture of the area states that for any finite poset $P$ there exists an integer $e(P)$ such that $La(n,P)=(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor}$.

In this paper, we formulate three strengthenings of this conjecture and prove them for some specific classes of posets. (The parameters $x(P)$ and $d(P)$ are defined in the paper.)

• For any finite connected poset $P$ and $\varepsilon>0$, there exists  $\delta>0$ and an integer $x(P)$ such that for any $n$ large enough, and $\mathcal{F}\subseteq 2^{[n]}$ of size $(e(P)+\varepsilon)\binom{n}{\lfloor n/2\rfloor}$, $\mathcal{F}$ contains at least $\delta n^{x(P)}\binom{n}{\lfloor n/2\rfloor}$ copies of $P$.
• The number of $P$-free families in $2^{[n]}$ is $2^{(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor}}$.
• Let $\mathcal{P}(n,p)$ be the random subfamily of $2^{[n]}$ such that every $F\in 2^{[n]}$ belongs to $\mathcal{P}(n,p)$ with probability $p$ independently of all other subsets $F'\in 2^{[n]}$. For any finite poset $P$, there exists a positive rational $d(P)$ such that if $p=\omega(n^{-d(P)})$, then the size of the largest $P$-free family in $\mathcal{P}(n,p)$ is $(e(P)+o(1))p\binom{n}{\lfloor n/2\rfloor}$ with high probability.