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:Prightarrow {F_1,F_2,dots,F_{|P|}}$ such that $ple_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 Fsubseteq 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}binom{l_{i-1}}{l_i})$, where $l_0=n$ and $l_1ge l_2ge dots 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, ldots, 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]}$.
تحميل البحث