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 $\mathrm{sat}^*(n,\mathcal{P})$, 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 $\mathrm{sat}^*(n,\Diamond)\geq\sqrt{n}$, improving upon a logarithmic lower bound. For the antichain with $k+1$ elements, we prove $$\mathrm{sat}^*(n,\mathcal{A}_{k+1})\geq \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\geq 3$.
@article{10_37236_8949,
author = {Ryan R. Martin and Heather C. Smith and Shanise Walker},
title = {Improved bounds for induced poset saturation},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {2},
doi = {10.37236/8949},
zbl = {1481.06016},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8949/}
}
TY - JOUR
AU - Ryan R. Martin
AU - Heather C. Smith
AU - Shanise Walker
TI - Improved bounds for induced poset saturation
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/8949/
DO - 10.37236/8949
ID - 10_37236_8949
ER -
%0 Journal Article
%A Ryan R. Martin
%A Heather C. Smith
%A Shanise Walker
%T Improved bounds for induced poset saturation
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8949/
%R 10.37236/8949
%F 10_37236_8949
Ryan R. Martin; Heather C. Smith; Shanise Walker. Improved bounds for induced poset saturation. The electronic journal of combinatorics, Tome 27 (2020) no. 2. doi: 10.37236/8949
