The Saturation Number of Induced Subposets of the Boolean Lattice

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

Published 2017-01-11Version 1

Given a poset P, a family F of points in the Boolean lattice is said to be P-saturated if (1) F contains no copy of P as a subposet and (2) every strict superset of F contains a copy of P as a subposet. The maximum size of a P-saturated subposet is denoted by La(n,P), which has been studied for a number of choices of P. Here, we are interested in sat(n,P), the size of the smallest family in B_n which is P-saturated. This notion was introduced by Gerbner et al. (2013), and parallels the deep literature on the saturation function for graphs. In particular, 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.