KIT | KIT-Bibliothek | Impressum | Datenschutz

Induced saturation for complete bipartite posets

Liu, Dingyuan 1
1 Fakultät für Mathematik (MATH), Karlsruher Institut für Technologie (KIT)

Abstract:

Given s, t ∈ N, a complete bipartite poset K$_{s,t}$ is a poset whose Hasse diagram consists of s pairwise incomparable vertices in the upper layer and t pairwise incomparable vertices in the lower layer, such that every vertex in the upper layer is larger than all vertices in the lower layer. A family F ⊆ 2[n] is called induced Ks,t -saturated if (F, ⊆) contains no induced copy of K$_{s,t}$ , whereas adding any set from 2[n] \F to F creates an induced K$_{s,t}$ . Let sat∗(n, K$_{s,t}$) denote the smallest size of an induced K$_{s,t}$ -saturated family F ⊆ 2[n]. It was conjectured that sat∗(n, K$_{s,t}$) is superlinear in n for certain values of s and t. In this paper, we show that sat∗(n, K$_{s,t}$) = O (n) for all fixed s, t ∈ N. Moreover, we prove a linear lower bound on sat∗(n, P) for a large class of posets P, particularly for K$_{s,2}$ with s ∈ N.


Verlagsausgabe §
DOI: 10.5445/IR/1000180155
Veröffentlicht am 18.03.2025
Originalveröffentlichung
DOI: 10.1016/j.disc.2025.114462
Scopus
Zitationen: 1
Web of Science
Zitationen: 1
Dimensions
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT KIT-Bibliothek (BIB)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 07.2025
Sprache Englisch
Identifikator ISSN: 0012-365X
KITopen-ID: 1000180155
Erschienen in Discrete Mathematics
Verlag Elsevier
Band 348
Heft 7
Seiten 114462
Nachgewiesen in Scopus
OpenAlex
Dimensions
Web of Science
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page