Saturation for Small Antichains

Abstract: For a given positive integer

k

we say that a family of subsets of

[n]

is

k

-antichain saturated if it does not contain

k

pairwise incomparable sets, but whenever we add to it a new set, we do find

k

such sets. The size of the smallest such family is denoted by

e x t {s a t}^{*} (n, m a t h c a l A_{k})

. Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan conjectured that

e x t {s a t}^{*} (n, m a t h c a l A_{k}) = (k - 1) n (1 + o (1))

, and proved this for

k l e q 4

. In this paper we prove this conjecture for

k = 5

and

k = 6

. Moreover, we give the exact value for

e x t {s a t}^{*} (n, m a t h c a l A_{5})

and

e x t {s a t}^{*} (n, m a t h c a l A_{6})

. We also give some open problems inspired by our analysis.

This page was built for publication: Saturation for Small Antichains