Diamond-free families

Abstract: 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

p i (P) := l i m_{n i g h t a r r o w i n f t y} L a (n, P) / n c h o o s e n / 2

exists for general posets P, and, moreover, it is an integer. For

k g e 2

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

p i (D_{k})

for infinitely many values

k

. A stubborn open problem is to show that

p i (D_{2}) = 2

; here we make progress by proving

p i (D_{2}) l e 23 / 11

(if it exists).

Recommendations

Cites Work

Cited In (33)

This page was built for publication: Diamond-free families