Originators: G.O.H. Katona and T.G. Tarján (presented by J. Cooper - REGS 2009)
Definitions: Given a specified poset P, let La(n,P) denote the maximum size of a family F of subsets of [n] such that the inclusion poset form by F does not contain any extension of P as a subposet.
Background: The study of La(n,P) generalizes Sperner's Theorem [S], which states that La(n,2) is the middle binomial coefficient, where k denotes a chain of size k. Forbidding 2 forces F to be an antichain, and largest antichains consist of the subsets of [n] with size n/2. Erdős [E] generalized the result to P=k, showing that La(n,k) is the sum of the k-1 largest binomial coefficients.
The problem of determining La(n,P) can be viewed as an analogue of the Turán problem ex(n,H) for graphs, with chains corresponding to complete graphs. When the poset P is not a chain, all extensions of P are also forbidden. For example, let Vr be the poset consisting of one minimal element and an antichain of r maximal elements above it. Forbidding Vr also forbids r+1 and all the other posets whose relations contain the relations in Vr. Letting C(n) denote the middle binomial coefficient, Thanh [T] and independently de Bonis and Katona [dBK] proved that La(n,Vr+1) is between C(n)(1+r/n) and C(n)(1+2r/n) (asymptotically); the case r=1 had been done by Katona and Tarján [KT]. Griggs and Katona [GK] obtained the same asymptotic bounds for La(n,N) as for La(n,V2), where N is the poset on {a,b,c,d} whose relations are a<b, c<b, and c<d. Further results of this sort have been obtained by Griggs and Lu [GL].
Conjecture: (Griggs-Lu) Letting D denote the poset of subsets of {1,2} ordered by inclusion, La(n,D) is asymptotic to 2C(n).
Comments: The family consisting of two middle levels provides the lower bound. Since the chain 4 contains D, we have La(n,D)<3C(n). Griggs and Lu have proved 2.3C(n) as an upper bound.
Analogous problems where P is forbidden as a subposet rather than a set of relations have also been studied; see [CK,K], etc.
References:
[CK] Carroll, Teena; Katona, Gyula O. H.;
Bounds on maximal families of sets not containing three sets with
A∩B⊂C, A≠B.
Order 25 (2008), no. 3, 229--236.
[dBK] De Bonis, A., Katona, G.O.H.: Largest families without an r-fork.
Order 24, 181--191 (2007)
[E] Erdős, P.; On a lemma of Littlewood and Offord. Bull. Am. Math. Soc.
51, 898--902 (1945)
[GK] Griggs, J.R., Katona, G.O.H.: No four subsets forming an N. J. Comb. Theory
A 115, 677--685 (2008)
[GL] Griggs, J.R., Lu, L.; manuscript.
[KT] Katona, G.O.H., Tarján, T.G.: Extremal problems with excluded
subgraphs in the n-cube. In: Borowiecki, M., Kennedy, J.W., Sys.o M.M.
(eds.) Graph Theory, Łagów, 1981. Lecture Notes in Math., vol.
1018, pp. 84--93. Springer (1983)
[K] Kleitman, D. J. Collections of sets without unions and intersections.
Combinatorial Mathematics: Proceedings of the Third International Conference
(New York, 1985), 272--282, Ann. New York Acad. Sci., 555, New York Acad. Sci.,
New York, 1989.
[S] Sperner, E.: Ein Satz über Untermegen einer endlichen Menge. Math. Z.
27, 544--548 (1928)
[T] Thanh, H.T.: An extremal problem with excluded subposets in the Boolean
lattice. Order 15, 51--57 (1998)