Improved bounds for induced poset saturation

DOI10.37236/8949zbMATH Open1481.06016arXiv1908.01108OpenAlexW3030386554MaRDI QIDQ2185221FDOQ2185221

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)

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$.

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

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)