The saturation number of induced subposets of the Boolean lattice

DOI10.1016/J.DISC.2017.06.010MaRDI QIDQ2012537zbMATH OpenOpenAlexFDO

Authors Michael Ferrara, Bill Kay, Lucas Kramer, Ryan R. Martin, Benjamin Reiniger, Heather Smith, Eric C. Sullivan

Publication date 1 August 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

saturationposetsinduced saturation

Mathematics Subject Classification ID

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

Abstract: Given a poset $P$, a family $F$ of elements in the Boolean lattice is said to be $P$-saturated if (1) $F$ contains no copy of $P$ as a subposet and (2) every proper superset of $F$ contains a copy of $P$ as a subposet. The maximum size of a $P$-saturated family is denoted by $La(n,P)$, which has been studied for a number of choices of $P$. The minimum size of a $P$-saturated family, $sat(n,P)$, was introduced by Gerbner et al. (2013), and parallels the deep literature on the saturation function for graphs. We introduce and study the concept of saturation for induced subposets. As opposed to induced saturation in graphs, the above definition of saturation for posets extends naturally to the induced setting. We give several exact results and a number of bounds on the induced saturation number for several small posets. We also use a transformation to the biclique cover problem to prove a logarithmic lower bound for a rich infinite family of target posets.

Recommendations

• Improved bounds for induced poset saturation
• 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

• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• scientific article; zbMATH DE number 790476 (Why is no real title available?)
• A Problem in Graph Theory
• A decomposition theorem for partially ordered sets
• A survey of minimum saturated graphs
• Berge trigraphs
• Bipartite dimensions and bipartite degrees of graphs
• Induced saturation number
• On saturated k-Sperner systems
• Progress on poset-free families of subsets
• Saturating Sperner families

Cited in

(13)

• Almost all permutation matrices have bounded saturation functions
• Saturation for small antichains
• Saturation of Ordered Graphs
• Saturation problems in the Ramsey theory of graphs, posets and point sets
• 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
• Improved bounds for induced poset saturation
• The induced saturation problem for posets
• Sequence saturation
• Supersaturation in posets and applications involving the container method
• Saturation problems about forbidden 0-1 submatrices
• Forbidden subposet problems in the grid

This page was built for publication: The saturation number of induced subposets of the Boolean lattice

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