×

zbMATH — the first resource for mathematics

The saturation number of induced subposets of the Boolean lattice. (English) Zbl 1423.06006
Summary: Given a poset \(\mathcal{P}\), a family \(\mathcal{F}\) of elements in the Boolean lattice is said to be \(\mathcal{P}\)-saturated if (1) \(\mathcal{F}\) contains no copy of \(\mathcal{P}\) as a subposet and (2) every proper superset of \(\mathcal{F}\) contains a copy of \(\mathcal{P}\) as a subposet. The maximum size of a \(\mathcal{P}\)-saturated family is denoted by \(\mathrm{La}(n, \mathcal{P})\), which has been studied for a number of choices of \(\mathcal{P}\). The minimum size of a \(\mathcal{P}\)-saturated family, \(\mathrm{sat}(n, \mathcal{P})\), was introduced by D. Gerbner et al. [Graphs Comb. 29, No. 5, 1355–1364 (2013; Zbl 1272.05212)], 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.

MSC:
06A07 Combinatorics of partially ordered sets
05D05 Extremal set theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Chudnovsky, M., Berge trigraphs, J. Graph Theory, 53, 1, 1-55, (2006) · Zbl 1101.05036
[2] Dilworth, R. P., A decomposition theorem for partially ordered sets, Ann. of Math. (2), 51, 161-166, (1950) · Zbl 0038.02003
[3] Erdős, P.; Hajnal, A.; Moon, J. W., A problem in graph theory, Amer. Math. Monthly, 71, 10, 1107-1110, (1964) · Zbl 0126.39401
[4] Faudree, J.; Faudree, R.; Schmitt, J., A survey of minimum saturated graphs, Electron. J. Combin., DS19, (2011) · Zbl 1222.05113
[5] Fishburn, P. C.; Hammer, P. L., Bipartite dimensions and bipartite degrees of graphs, Discrete Math., 160, 1-3, 127-148, (1996) · Zbl 0861.05035
[6] Gerbner, D.; Keszegh, B.; Lemons, N.; Palmer, C.; Pálvölgyi, D.; Patkós, B., Saturating sperner families, Graphs Combin., 29, 5, 1355-1364, (2013) · Zbl 1272.05212
[7] Griggs, J. R.; Li, W.-T., Progress on poset-free families of subsets, (Recent Trends in Combinatorics, (2016), Springer), 317-338 · Zbl 1354.05138
[8] Martin, R. R.; Smith, J. J., Induced saturation number, Discrete Math., 312, 21, 3096-3106, (2012) · Zbl 1251.05082
[9] Monson, S. D.; Pullman, N. J.; Rees, R., A survey of clique and biclique coverings and factorizations of \((0, 1)\)-matrices, Bull. Inst. Combin. Appl., 14, 17-86, (1995) · Zbl 0832.05088
[10] Morrison, N.; Noel, J. A.; Scott, A., On saturated \(k\)-sperner systems, Electron. J. Combin., 21, (2014) · Zbl 1300.05310
[11] Rényi, A., On random generating elements of a finite Boolean algebra, Acta Sci. Math. (Szeged), 22, 75-81, (1961) · Zbl 0099.12204
[12] Sperner, E., Ein satz uber utermegen einer endlichen menge, Math. Z., 2, 544-548, (1928) · JFM 54.0090.06
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.