Repository logo
 

Saturation for Small Antichains

Published version
Peer-reviewed

Type

Article

Change log

Authors

Ðanković, Irina 
Ivan, Maria-Romina 

Abstract

jats:pFor 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 sat∗(n,Ak). Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan conjectured that sat∗(n,Ak)=(k−1)n(1+o(1)), and proved this for k≤4. In this paper we prove this conjecture for k=5 and k=6. Moreover, we give the exact value for sat∗(n,A5) and sat∗(n,A6). We also give some open problems inspired by our analysis.</jats:p>

Description

Keywords

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

The Electronic Journal of Combinatorics

Conference Name

Journal ISSN

1097-1440
1077-8926

Volume Title

30

Publisher

The Electronic Journal of Combinatorics

Rights

Publisher's own licence
Sponsorship
Engineering and Physical Sciences Research Council (2261049)