The saturation number of induced subposets of the Boolean lattice

DOI10.1016/J.DISC.2017.06.010zbMATH Open1423.06006arXiv1701.03010OpenAlexW2576813251MaRDI QIDQ2012537FDOQ2012537

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)

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.

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

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

zbMATH Keywords

saturationposetsinduced saturation

Mathematics Subject Classification ID

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

Cites Work

• Berge trigraphs
• A survey of minimum saturated graphs
• Induced saturation number
• A Problem in Graph Theory
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Saturating Sperner families
• Title not available (Why is that?)
• Bipartite dimensions and bipartite degrees of graphs
• On saturated \(k\)-Sperner systems
• Progress on poset-free families of subsets

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)