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
- Karlsruhe Institute of Technology (DE)
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