Improved bounds for induced poset saturation

DOI10.37236/8949MaRDI QIDQ2185221zbMATH OpenOpenAlexFDO

Authors Ryan R. Martin, Heather Smith, Shanise Walker

Publication date 4 June 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05)

Abstract: Given a finite poset $mathcalP$, a family $mathcalF$ of elements in the Boolean lattice is induced-$mathcalP$-saturated if $mathcalF$ contains no copy of $mathcalP$ as an induced subposet but every proper superset of $mathcalF$ contains a copy of $mathcalP$ as an induced subposet. The minimum size of an induced-$mathcalP$-saturated family in the $n$-dimensional Boolean lattice, denoted $operatorname{sat}^{\ast }(n,mathcalP)$, was first studied by Ferrara et al. (2017). Our work focuses on strengthening lower bounds. For the 4-point poset known as the diamond, we prove $operatorname{sat}^{\ast }(n,mathcal{D}_2)geqsqrtn$, improving upon a logarithmic lower bound. For the antichain with $k+1$ elements, we prove $operatorname{sat}^{\ast }(n,mathcal{A}_{k+1})geq(1-o_k(1))fracknlo{g}_{2}k$, improving upon a lower bound of $3n-1$ for $kgeq3$.

Recommendations

• The saturation number of induced subposets of the Boolean lattice
• Induced and non-induced poset saturation problems
• Saturation for the butterfly poset
• Induced and non-induced forbidden subposet problems
• Supersaturation in posets and applications involving the container method

Cites work

• A Problem in Graph Theory
• A decomposition theorem for partially ordered sets
• A survey of minimum saturated graphs
• On saturated \(k\)-Sperner systems
• Progress on poset-free families of subsets
• Saturating Sperner families
• The saturation number of induced subposets of the Boolean lattice

Cited in

(7)

• Saturation for the butterfly poset
• Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
• The induced saturation problem for posets
• Saturation for small antichains
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Induced and non-induced poset saturation problems
• The saturation number of induced subposets of the Boolean lattice

This page was built for publication: Improved bounds for induced poset saturation

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