On families of subsets with a forbidden subposet

Details On families of subsets with a forbidden subposet On families of subsets with a forbidden subposet

2008-07-23

arxiv.org/abs/0807.3702v1

Mathematics

Combinatorics

19 pages, submitted to CPC

Scientific paper

Let $\F\subset 2^{[n]}$ be a family of subsets of $\{1,2,..., n\}$. For any poset $H$, we say $\F$ is $H$-free if $\F$ does not contain any subposet isomorphic to $H$. Katona and others have investigated the behavior of $\La(n,H)$, which denotes the maximum size of $H$-free families $\F\subset 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\to\infty$ for various posets $H$, including two-end-forks, up-down trees, and cycles $C_{4k}$ on two levels.

Affiliated with

Also associated with

No associations

Rating

On families of subsets with a forbidden subposet does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On families of subsets with a forbidden subposet, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On families of subsets with a forbidden subposet will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-1234