<p>A family <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varvec{{\mathcal {G}}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-script">G</mi> </mrow> </math></EquationSource> </InlineEquation> of sets is a(n induced) copy of a poset <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varvec{P}\varvec{=}\varvec{(}\varvec{P}\varvec{,}\varvec{\leqslant }\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> <mrow> <mo mathvariant="bold">,</mo> </mrow> <mrow> <mo mathvariant="bold">⩽</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> if there exists a bijection <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\varvec{b}\varvec{:}\varvec{P}\varvec{\rightarrow } \varvec{{\mathcal {G}}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> <mrow> <mo mathvariant="bold">:</mo> </mrow> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> <mrow> <mo mathvariant="bold">→</mo> </mrow> <mrow> <mi mathvariant="bold-script">G</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\varvec{p}\varvec{\leqslant } \varvec{q}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">p</mi> </mrow> <mrow> <mo mathvariant="bold">⩽</mo> </mrow> <mrow> <mi mathvariant="bold-italic">q</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> holds if and only if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varvec{b}\varvec{(p)}\varvec{\subset } \varvec{b}\varvec{(q)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">p</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mrow> <mo mathvariant="bold">⊂</mo> </mrow> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">q</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. The induced saturation number <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\varvec{\textrm{sat}^}\varvec{(}\varvec{n}\varvec{,}\varvec{P}\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <msup> <mtext>sat</mtext> <mo mathvariant="bold">∗</mo> </msup> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mo mathvariant="bold">,</mo> </mrow> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the minimum size of a family <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\varvec{{\mathcal {F}}}\varvec{\subseteq } \varvec{2}^{\varvec{[n]}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">F</mi> </mrow> <mrow> <mo mathvariant="bold">⊆</mo> </mrow> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">[</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">]</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> that does not contain any copy of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\varvec{P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> </math></EquationSource> </InlineEquation>, but for any <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\varvec{G}\varvec{\in } \varvec{2}^{\varvec{[n]}}\varvec{\setminus } \varvec{{\mathcal {F}}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">G</mi> </mrow> <mrow> <mo mathvariant="bold">∈</mo> </mrow> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">[</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">]</mo> </mrow> </msup> <mrow> <mo lspace="0.15em" mathvariant="bold" rspace="0.15em" stretchy="false">\</mo> </mrow> <mrow> <mi mathvariant="bold-script">F</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation>, the family <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\varvec{{\mathcal {F}}}\varvec{\cup } \varvec{\{G\}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">F</mi> </mrow> <mrow> <mo mathvariant="bold">∪</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">{</mo> <mi mathvariant="bold-italic">G</mi> <mo mathvariant="bold" stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> contains a copy of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\varvec{P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> </math></EquationSource> </InlineEquation>. We consider <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\varvec{\textrm{sat}^}\varvec{(n,P)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <msup> <mtext>sat</mtext> <mo mathvariant="bold">∗</mo> </msup> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">P</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for posets <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\varvec{P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> </math></EquationSource> </InlineEquation> that are formed by pairwise incomparable chains, i.e. <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\varvec{P}\varvec{=}\varvec{\bigoplus }_{\varvec{j=1}}^{\varvec{m}}\varvec{C}_{\varvec{i}_{\varvec{j}}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <msubsup> <mrow> <mo mathvariant="bold">⨁</mo> </mrow> <mrow> <mrow> <mi mathvariant="bold-italic">j</mi> <mo mathvariant="bold">=</mo> <mn mathvariant="bold">1</mn> </mrow> </mrow> <mrow> <mi mathvariant="bold-italic">m</mi> </mrow> </msubsup> <msub> <mrow> <mi mathvariant="bold-italic">C</mi> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">i</mi> </mrow> <mrow> <mi mathvariant="bold-italic">j</mi> </mrow> </msub> </msub> </mrow> </math></EquationSource> </InlineEquation>. We make the following two conjectures: (i) <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\varvec{\textrm{sat}^}\varvec{(n,P)}\varvec{=}\varvec{O}\varvec{(n)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <msup> <mtext>sat</mtext> <mo mathvariant="bold">∗</mo> </msup> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">P</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mi mathvariant="bold-italic">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for all such posets and (ii) <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$\varvec{\textrm{sat}^}\varvec{(n,P)}\varvec{=}\varvec{O}\varvec{(1)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <msup> <mtext>sat</mtext> <mo mathvariant="bold">∗</mo> </msup> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">P</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mi mathvariant="bold-italic">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> if not all two 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 <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\varvec{2C}_{\varvec{k}}\varvec{+}\varvec{C}_{\varvec{1}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">C</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> <mrow> <mo mathvariant="bold">+</mo> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">C</mi> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>. Finally, we give an infinite number of examples showing that (ii) is not a necessary condition for <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$\varvec{\textrm{sat}^}\varvec{(n,P)}\varvec{=}\varvec{O}\varvec{(1)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <msup> <mtext>sat</mtext> <mo mathvariant="bold">∗</mo> </msup> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">P</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mi mathvariant="bold-italic">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> among posets <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$\varvec{P}\varvec{=}\varvec{\bigoplus }_{\varvec{j=1}}^{\varvec{m}}\varvec{C}_{{\varvec{i}}_{\varvec{j}}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">P</mi> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <msubsup> <mrow> <mo mathvariant="bold">⨁</mo> </mrow> <mrow> <mrow> <mi mathvariant="bold-italic">j</mi> <mo mathvariant="bold">=</mo> <mn mathvariant="bold">1</mn> </mrow> </mrow> <mrow> <mi mathvariant="bold-italic">m</mi> </mrow> </msubsup> <msub> <mrow> <mi mathvariant="bold-italic">C</mi> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">i</mi> </mrow> <mrow> <mi mathvariant="bold-italic">j</mi> </mrow> </msub> </msub> </mrow> </math></EquationSource> </InlineEquation>: we prove <InlineEquation ID="IEq20"> <EquationSource Format="TEX">$\varvec{\textrm{sat}^}\varvec{(}\varvec{n}\varvec{,}\varvec{(}\left( {\begin{array}{c}\varvec{2t}\\ \varvec{t}\end{array}}\right) \varvec{+}\varvec{1}\varvec{)}\varvec{C}_{\varvec{2}}\varvec{)}\varvec{=}\varvec{O}\varvec{(1)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <msup> <mtext>sat</mtext> <mo mathvariant="bold">∗</mo> </msup> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mo mathvariant="bold">,</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">t</mi> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mrow> <mi mathvariant="bold-italic">t</mi> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mrow> <mo mathvariant="bold">+</mo> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">C</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mi mathvariant="bold-italic">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq21"> <EquationSource Format="TEX">$\varvec{t}\varvec{\ge } \varvec{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">t</mi> </mrow> <mrow> <mo mathvariant="bold">≥</mo> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>.</p>

Poset Saturation of Unions of Chains

期刊论文
出版模式：

开放获取
发表日期：

2026年3月7日

查看全文

Shengjin Ji,
Balázs Patkós,
Erfei Yue

摘要

A family $\varvec{{\mathcal {G}}}$ $G$ of sets is a(n induced) copy of a poset $\varvec{P}\varvec{=}\varvec{(}\varvec{P}\varvec{,}\varvec{\leqslant }\varvec{)}$ $P = (P, ⩽)$ if there exists a bijection $\varvec{b}\varvec{:}\varvec{P}\varvec{\rightarrow } \varvec{{\mathcal {G}}}$ $b : P \to G$ such that $\varvec{p}\varvec{\leqslant } \varvec{q}$ $p ⩽ q$ holds if and only if $\varvec{b}\varvec{(p)}\varvec{\subset } \varvec{b}\varvec{(q)}$ $b (p) \subset b (q)$ . The induced saturation number $\varvec{\textrm{sat}^*}\varvec{(}\varvec{n}\varvec{,}\varvec{P}\varvec{)}$ ${sat}^{*} (n, P)$ is the minimum size of a family $\varvec{{\mathcal {F}}}\varvec{\subseteq } \varvec{2}^{\varvec{[n]}}$ $F \subseteq 2^{[n]}$ that does not contain any copy of $\varvec{P}$ $P$ , but for any $\varvec{G}\varvec{\in } \varvec{2}^{\varvec{[n]}}\varvec{\setminus } \varvec{{\mathcal {F}}}$ $G \in 2^{[n]} \ F$ , the family $\varvec{{\mathcal {F}}}\varvec{\cup } \varvec{\{G\}}$ $F \cup {G}$ contains a copy of $\varvec{P}$ $P$ . We consider $\varvec{\textrm{sat}^*}\varvec{(n,P)}$ ${sat}^{*} (n, P)$ for posets $\varvec{P}$ $P$ that are formed by pairwise incomparable chains, i.e. $\varvec{P}\varvec{=}\varvec{\bigoplus }_{\varvec{j=1}}^{\varvec{m}}\varvec{C}_{\varvec{i}_{\varvec{j}}}$ $P = ⨁_{j = 1}^{m} C_{i_{j}}$ . We make the following two conjectures: (i) $\varvec{\textrm{sat}^*}\varvec{(n,P)}\varvec{=}\varvec{O}\varvec{(n)}$ ${sat}^{*} (n, P) = O (n)$ for all such posets and (ii) $\varvec{\textrm{sat}^*}\varvec{(n,P)}\varvec{=}\varvec{O}\varvec{(1)}$ ${sat}^{*} (n, P) = O (1)$ if not all two 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 $\varvec{2C}_{\varvec{k}}\varvec{+}\varvec{C}_{\varvec{1}}$ ${2 C}_{k} + C_{1}$ . Finally, we give an infinite number of examples showing that (ii) is not a necessary condition for $\varvec{\textrm{sat}^*}\varvec{(n,P)}\varvec{=}\varvec{O}\varvec{(1)}$ ${sat}^{*} (n, P) = O (1)$ among posets $\varvec{P}\varvec{=}\varvec{\bigoplus }_{\varvec{j=1}}^{\varvec{m}}\varvec{C}_{{\varvec{i}}_{\varvec{j}}}$ $P = ⨁_{j = 1}^{m} C_{i_{j}}$ : we prove $\varvec{\textrm{sat}^*}\varvec{(}\varvec{n}\varvec{,}\varvec{(}\left( {\begin{array}{c}\varvec{2t}\\ \varvec{t}\end{array}}\right) \varvec{+}\varvec{1}\varvec{)}\varvec{C}_{\varvec{2}}\varvec{)}\varvec{=}\varvec{O}\varvec{(1)}$ ${sat}^{*} (n, ((\begin{matrix} 2 t \\ t \end{matrix}) + 1) C_{2}) = O (1)$ for all $\varvec{t}\varvec{\ge } \varvec{2}$ $t \geq 2$ .