2025/05/29 by Ji, Shengjin, Patkós, Balázs, Yue, Erfei
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2505.23128
A family G of sets is a(n induced) copy of a poset P=(P,\leqslant) if there exists a bijection b:P→ G such that p\leqslant q holds if and only if b(p)⊆ b(q). The induced saturation number sat^*(n,P) is the minimum size of a family F⊆ 2[n] that does not contain any copy of P, but for any G∈ 2[n]∖ F, the family F∪ \G\ contains a copy of P. We consider sat^*(n,P) for posets P that are formed by pairwise incomparable chains, i.e. P=\bigoplusj=1mCij. We make the following two conjectures: (i) sat^*(n,P)=O(n) for all such posets and (ii) sat^*(n,P)=O(1) if not all chains are of the same size. (The second conjecture is known to hold if there is a unique longest among the chains.) We verify these conjectures in some special cases: we prove (i) if all chains are of the same length, we prove (ii) in the first unknown general case: for posets 2Ck+C1. Finally, we give an infinite number of examples showing that (ii) is not a necessary condition for sat^*(n,P)=O(1) among posets P=\bigoplusj=1mCij: we prove sat^*(n,(\binom2tt+1)C2)=O(1) for all t≥ 1.