Diamond-free Families

Details Diamond-free Families Diamond-free Families

2010-10-26

arxiv.org/abs/1010.5311v3

Mathematics

Combinatorics

16 pages

Scientific paper

Given a finite poset P, we consider the largest size La(n,P) of a family of subsets of $[n]:=\{1,...,n\}$ that contains no subposet P. This problem has been studied intensively in recent years, and it is conjectured that $\pi(P):= \lim_{n\rightarrow\infty} La(n,P)/{n choose n/2}$ exists for general posets P, and, moreover, it is an integer. For $k\ge2$ let $\D_k$ denote the $k$-diamond poset $\{A< B_1,...,B_k < C\}$. We study the average number of times a random full chain meets a $P$-free family, called the Lubell function, and use it for $P=\D_k$ to determine $\pi(\D_k)$ for infinitely many values $k$. A stubborn open problem is to show that $\pi(\D_2)=2$; here we make progress by proving $\pi(\D_2)\le 2 3/11$ (if it exists).

Affiliated with

Also associated with

No associations

Rating

Diamond-free Families 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 Diamond-free Families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diamond-free Families will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159097