Induced saturation for complete bipartite posets

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 K s , 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 .

Institutions

Publication Details

Journal
Discrete Mathematics
Published
2025-03-05
DOI
https://doi.org/10.1016/j.disc.2025.114462
Citations
2
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
10.66
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Induced saturation for complete bipartite posets

2 citations
Discrete Mathematics
Limits and Structures in Graph Theory
10.66
article

Induced saturation for complete bipartite posets

article en
2 citations

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 K s , 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 .

Discrete MathematicsVol. 348(7)
Karlsruhe Institute of Technology (DE)
Openalex Percentile: Top 1%
Limits and Structures in Graph Theory
10.66
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Induced saturation for complete bipartite posets · Discrete Mathematics (2025) | TGRS Research Map | TGRS