The saturation number of induced subposets of the Boolean lattice
The saturation number of induced subposets of the Boolean lattice
复制标题
布尔格的诱导子集的饱和数
DOI：
10.1016/j.disc.2017.06.010
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Eric Sullivan
中科院分区：
文献类型：
--
作者：
M. Ferrara;Bill Kay;Lucas Kramer;Ryan R. Martin;B. Reiniger;Heather C. Smith;Eric Sullivan
给定一个偏序集P，如果(1)F不包含作为传票集的P的副本，(2)F的每个固有超集包含作为传票集的P的副本，则布尔格中的元素族F被称为P饱和的。P-饱和族的最大大小用La （n， P）表示，这已经研究了P的许多选择。P-饱和族的最小大小sat （n， P）由Gerbner等人（2013）引入，并与图的饱和函数的深层文献相似。引入并研究了诱导传票集的饱和概念。与图中的诱导饱和相反，上述偏集的饱和定义自然地扩展到诱导设置。我们给出了几个精确的结果和几个小偏集的诱导饱和数的界。我们还利用对双峰覆盖问题的一个变换，证明了一组丰富的无限目标集的对数下界。
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.