On the Number of Containments in P-free Families.

A subfamily { F 1 , F 2 , ⋯ , F | P | } ⊆ F is a copy of the poset P if there exists a bijection i : P → { F 1 , F 2 , ⋯ , F | P | } , such that p ≤ P q implies i (p) ⊆ i (q) . A family F is P-free, if it does not contain a copy of P. In this paper we establish basic results on the maximum number of k-chains in a P-free family F ⊆ 2 [ n ] . We prove that if the height of P, h (P) > k , then this number is of the order Θ (∏ i = 1 k + 1 l i - 1 l i ) , where l 0 = n and l 1 ≥ l 2 ≥ ⋯ ≥ l k + 1 are such that n - l 1 , l 1 - l 2 , ⋯ , l k - l k + 1 , l k + 1 differ by at most one. On the other hand if h (P) ≤ k , then we show that this number is of smaller order of magnitude. Let ∨ r denote the poset on r + 1 elements a , b 1 , b 2 , ... , b r , where a < b i for all 1 ≤ i ≤ r and let ∧ r denote its dual. For any values of k and l, we construct a { ∧ k , ∨ 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 { ∧ k , ∨ l } -free families F ⊆ 2 [ n ] . [ABSTRACT FROM AUTHOR]