On the number of containments in $P$-free families

Abstract

A subfamily $\{F_1,F_2,\dots ,F_{|P|}\}\subseteq \mathcal{F}$ is a copy of the poset $P$ if there exists a bijection $i:P\to \{F_1,F_2,\dots ,F_{|P|}\}$ such that $p{\le }_{P}q$ implies $i(p)\subseteq i(q)$. A family $\mathcal{F}$ is $P$-free, if it does not contain a copy of $P$. In this paper we establish basic results on the maximum possible number of $k$-chains in a $P$-free family $\mathcal{F}\subseteq 2^{[n]}$. We prove that if the height of $P$, $h(P)>k$, then this number is of the order $\Theta ({\prod }_{i=1}^{k+1}(\genfrac{}{}{0ex}{}{l_{i-1}}{l_i}))$, where $l_0=n$ and $l_1\ge l_2\ge \cdots \ge l_{k+1}$ are such that $n-l_1,l_1-l_2,\dots ,l_k-l_{k+1},l_{k+1}$ differ by at most one. On the other hand if $h(P)\le k$, then we show that this number is of smaller order of magnitude. Let ${\vee }_r$ denote the poset on $r+1$ elements $a,b_1,b_2,\dots ,b_r$, where $a<b_i$ for all $1\le i\le r$ and let ${\wedge }_r$ denote its dual. For any values of $k$ and $l$, we construct a $\{{\wedge }_k,{\vee }_l\}$-free family and we conjecture that it contains asymptotically the maximum number of pairs in containment. We prove that this conjecture holds under the additional assumption that a chain of length 4 is forbidden. Moreover, we prove the conjecture for some small values of $k$ and $l$. We also derive the asymptotics of the maximum number of copies of certain tree posets $T$ of height 2 in $\{{\wedge }_k,{\vee }_l\}$-free families $\mathcal{F}\subseteq 2^{[n]}$.