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

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

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

Review text

Summary: Given a finite poset \(\mathcal{P} \), a family \(\mathcal{F}\) of elements in the Boolean lattice is induced-\( \mathcal{P} \)-saturated if \(\mathcal{F}\) contains no copy of \(\mathcal{P}\) as an induced subposet but every proper superset of \(\mathcal{F}\) contains a copy of \(\mathcal{P}\) as an induced subposet. The minimum size of an induced-\( \mathcal{P} \)-saturated family in the \(n\)-dimensional Boolean lattice, denoted \(\text{sat}^*(n,\mathcal{P})\), was first studied by \textit{M. Ferrara} et al. [Discrete Math. 340, No. 10, 2479--2487 (2017; Zbl 1423.06006)]. Our work focuses on strengthening lower bounds. For the 4-point poset known as the diamond, we prove \(\text{sat}^*(n,\mathcal{D}_2)\geqslant\sqrt{n} \), improving upon a logarithmic lower bound. For the antichain with \(k+1\) elements, we prove \[\text{sat}^*(n,\mathcal{A}_{k+1})\geqslant \left(1-\frac{1}{\log_2k}\right)\frac{kn}{\log_2 k}\] for \(n\) sufficiently large, improving upon a lower bound of \(3n-1\) for \(k\geqslant 3\).

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 decomposition theorem for partially ordered sets
• A Problem in Graph Theory
• 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

(15)

• The saturation number of induced subposets of the Boolean lattice
• Induced and non-induced poset saturation problems
• Saturation for small antichains
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Saturation for the butterfly poset
• The induced saturation problem for posets
• Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
• Induced saturation of the poset 2C₂
• Poset saturation of unions of chains
• A polynomial upper bound for poset saturation
• Projective and external saturation problem for posets
• Saturation of k-chains in the Boolean lattice
• A general bound for the induced poset saturation problem (extended abstract)
• Induced saturation for complete bipartite posets
• Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron (extended abstract)

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)