The Library
On saturated k-Sperner systems
Tools
Tools
Tools
Morrison, Natasha, Noel, Jonathan A. and Scott, Alex (2014) On saturated k-Sperner systems. Electronic Journal of Combinatorics, 21 (3). P3.22. ISSN 1077-8926.
|
PDF
WRAP-on-saturated-Sperner-systems-Noel-2014.pdf - Published Version - Requires a PDF viewer. Download (754Kb) | Preview |
Official URL: http://www.combinatorics.org/ojs/index.php/eljc/ar...
Abstract
Given a set X , a collection F ⊆ P (X) is said to be k-Sperner if it does not contain a chain of length k + 1 under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. [11] conjectured that, if |X| is sufficiently large with respect to k, then the minimum size of a saturated k-Sperner system F ⊆ P (X) is 2k-1 . We disprove this conjecture by showing that there exists ε > 0 such that for every k and |X| > n0 (k) there exists a saturated k-Sperner system F ⊆P (X) with cardinality at most 2 (1- ε)k. A collection F ⊆ P (X) is said to be an oversaturated k-Sperner system if, for every S∈P (X) \ F, F∪{ S } contains more chains of length k +1 than F. Gerbner et al. [11] proved that, if |X| > k, then the smallest such collection contains between 2k/2-1 and O (log k k 2 k) elements. We show that if |X| > k2 + k, then the lower bound is best possible, up to a polynomial factor.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Sperner theory, Combinatorial analysis | ||||||
| Journal or Publication Title: | Electronic Journal of Combinatorics | ||||||
| Publisher: | Electronic Journal of Combinatorics | ||||||
| ISSN: | 1077-8926 | ||||||
| Official Date: | 2014 | ||||||
| Dates: |
|
||||||
| Volume: | 21 | ||||||
| Number: | 3 | ||||||
| Article Number: | P3.22 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||
| Date of first compliant deposit: | 10 July 2018 | ||||||
| Date of first compliant Open Access: | 10 July 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
