On saturated k-Sperner systems

zbMATH Open1300.05310arXiv1402.5646MaRDI QIDQ405311FDOQ405311

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)

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.

Full work available at URL: https://arxiv.org/abs/1402.5646

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

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

zbMATH Keywords

minimum saturationset systemsSperner systems

Mathematics Subject Classification ID

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

Cites Work

• Saturated \(r\)-uniform hypergraphs
• Saturated graphs with minimal number of edges
• A survey of minimum saturated graphs
• Title not available (Why is that?)
• A Problem in Graph Theory
• Title not available (Why is that?)
• On a lemma of Littlewood and Offord
• All minimum \(C_{5}\)-saturated graphs
• Saturating Sperner families
• The Minimum Size of Saturated Hypergraphs
• The saturation function of complete partite graphs
• Title not available (Why is that?)
• On a Conjecture of Erdos, Hajnal and Moon
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic evaluation of the sat-function for \(r\)-stars
• Saturated subgraphs of the hypercube
• Title not available (Why is that?)

Cited In (16)

• The largest projective cube-free subsets of \(\mathbb{Z}_{2^n}\)
• Title not available (Why is that?)
• 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
• The saturation spectrum for antichains of subsets

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)