On Families of Subsets With a Forbidden Subposet

Jerrold R. Griggs, Linyuan Lü

Combinatorics Probability Computing · 2009 · 70 citations · 8 references

DOIFull text

Open access

Concepts

Abstract

Let ⊂ 2 [ n ] be a family of subsets of {1, 2,. . ., n }. For any poset H , we say is H -free if does not contain any subposet isomorphic to H . Katona and others have investigated the behaviour of La( n , H ), which denotes the maximum size of H -free families ⊂ 2 [ n ] . Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets H , for which La( n , H ) can be determined asymptotically as n → ∞ for various posets H , including two-end-forks, up-down trees, and cycles C 4 k on two levels.

References

8