Generalized Forbidden Subposet Problems

A subfamily {F1,F2, horizontal ellipsis ,F|P|}subset of F of sets is a copy of a poset P in F if there exists a bijection phi:P ->{F1,F2, horizontal ellipsis ,F|P|} holds, then so does phi(x)subset of phi(x ') of sets, let c(P,F) denote the number of copies of P in F, and we say that F is P-free if c(P,F)=0 holds. For any two posets P, Q let us denote by La(n, P, Q) the maximum number of copies of Q over all P-free families F subset of 2[n], i.e. max{c(Q,F):F subset of 2[n],c(P,F)=0}. This generalizes the well-studied parameter La(n, P) = La(n, P, P-1) where P-1 is the one element poset, i.e. La(n, P) is the largest possible size of a P-free family. The quantity La(n, P) has been determined (precisely or asymptotically) for many posets P, and in all known cases an asymptotically best construction can be obtained by taking as many middle levels as possible without creating a copy of P. In this paper we consider the first instances of the problem of determining La(n, P, Q). We find its value when P and Q are small posets, like chains, forks, the N poset and diamonds. Already these special cases show that the extremal families are completely different from those in the original P-free cases: sometimes not middle or consecutive levels maximize La(n, P, Q) and sometimes the extremal family is not the union of levels. Finally, we determine (up to a polynomial factor) the maximum number of copies of complete multi-level posets in k-Sperner families. The main tools for this are the profile polytope method and two extremal set system problems that are of independent interest: we maximize the number of r-tuples A1,A2, horizontal ellipsis ,Ar is an element of A over all antichains A subset of 2[n] such that (i) boolean AND i=1rAi= null , (ii) boolean AND i=1rAi= null and ?i=1rAi=[n].