On saturated k-Sperner systems

MaRDI QIDQ405311zbMATH OpenFDO

Authors Natasha Morrison, Jonathan A. Noel, Alex Scott

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.5646, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p22

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

minimum saturationset systemsSperner systems

Mathematics Subject Classification ID

Extremal set theory (05D05) Ramsey theory (05D10)

Abstract: Given a set $X$, a collection $mathcalFsubseteqmathcalP(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. conjectured that, if $|X|$ is sufficiently large with respect to $k$, then the minimum size of a saturated $k$-Sperner system $mathcalFsubseteqmathcalP(X)$ is $2^{k-1}$. We disprove this conjecture by showing that there exists $varepsilon>0$ such that for every $k$ and $|X|geq{n}_0(k)$ there exists a saturated $k$-Sperner system $mathcalFsubseteqmathcalP(X)$ with cardinality at most $2^{(1-varepsilon)k}$. A collection $mathcalFsubseteqmathcalP(X)$ is said to be an oversaturated $k$-Sperner system if, for every $SinmathcalP(X)setminusmathcalF$, $mathcalFcupS$ contains more chains of length $k+1$ than $mathcalF$. Gerbner et al. proved that, if $|X|geqk$, then the smallest such collection contains between $2^{k/2-1}$ and $Oleft(fraclogkk{2}^{k}ight)$ elements. We show that if $|X|geq{k}^2+k$, then the lower bound is best possible, up to a polynomial factor.

Recommendations

• Saturating Sperner families
• Minimum saturated families of sets
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Supersaturation in the Boolean lattice
• Sperner systems containing at most \(k\) sets of every cardinality

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• scientific article; zbMATH DE number 3239217 (Why is no real title available?)
• scientific article; zbMATH DE number 3267972 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• scientific article; zbMATH DE number 4185643 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• All minimum \(C_{5}\)-saturated graphs
• Asymptotic evaluation of the sat-function for r-stars
• On a Conjecture of Erdos, Hajnal and Moon
• On a lemma of Littlewood and Offord
• Saturated r-uniform hypergraphs
• Saturated graphs with minimal number of edges
• Saturated subgraphs of the hypercube
• Saturating Sperner families
• The Minimum Size of Saturated Hypergraphs
• The saturation function of complete partite graphs

Cited in

(17)

• The largest projective cube-free subsets of \(\mathbb{Z}_{2^n}\)
• The saturation spectrum for antichains of subsets
• scientific article; zbMATH DE number 3983505 (Why is no real title available?)
• Saturation for small antichains
• Saturation in the hypercube and bootstrap percolation
• The saturation number of induced subposets of the Boolean lattice
• Partite saturation problems
• Induced and non-induced poset saturation problems
• Saturated subgraphs of the hypercube
• Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
• Saturating systems and the rank-metric covering radius
• Saturation for the butterfly poset
• Saturation number of \(tK_{l,l,l}\) in the complete tripartite graph
• Improved bounds for induced poset saturation
• The induced saturation problem for posets
• Supersaturation in the Boolean lattice
• Saturating Sperner families

This page was built for publication: On saturated \(k\)-Sperner systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405311)