<p>Given a set <i>X</i>, the power set <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\mathcal {P}(X)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">P</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and a finite poset <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\((P,\le _P)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>P</mi> <mo>,</mo> <msub> <mo>≤</mo> <mi>P</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, a family <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mathcal {F}\subseteq \mathcal {P}(X)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo>⊆</mo> <mi mathvariant="script">P</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is said to be induced-<i>P</i>-free if there is no injection <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\varphi : P\rightarrow \mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>φ</mi> <mo>:</mo> <mi>P</mi> <mo stretchy="false">→</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\varphi (p)\subseteq \varphi (q)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> <mo>⊆</mo> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if and only if <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(p\le _{P} q\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <msub> <mo>≤</mo> <mi>P</mi> </msub> <mi>q</mi> </mrow> </math></EquationSource> </InlineEquation> for every <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(p,q \in P\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo>∈</mo> <mi>P</mi> </mrow> </math></EquationSource> </InlineEquation>. The family <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is <i>induced-P-saturated</i> if it is maximal with respect to being induced-<i>P</i>-free. If <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(n=|X|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mo stretchy="false">|</mo> <mi>X</mi> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>, then the size of the smallest induced-<i>P</i>-saturated family in <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\mathcal {P}(X)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">P</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is denoted <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\textrm{sat}^*(n,P)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mtext>sat</mtext> <mo>∗</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. The poset <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(2C_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msub> <mi>C</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> is two incomparable 2-chains (the Hasse diagram is two vertex-disjoint edges) and Keszegh, Lemons, Martin, Pálvölgyi, and Patkós proved that <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(n+2\le \textrm{sat}^*(n,2C_2)\le 2n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo>≤</mo> <msup> <mtext>sat</mtext> <mo>∗</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>2</mn> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>2</mn> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> and gave one isomorphism class of an induced-<InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(2C_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msub> <mi>C</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>-saturated family that achieves the upper bound. We show that the lower bound can be improved to <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(3n/2 + 1/2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo>+</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> by examining the necessary structure of a saturated family. In addition, we provide many examples of induced-<InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(2C_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msub> <mi>C</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>-saturated families of size 2<i>n</i> in <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(\mathcal {P}(X)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">P</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(|X|=n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>X</mi> <mo stretchy="false">|</mo> <mo>=</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Induced Saturation of the Poset \(2C_2\)

  • Ryan R. Martin,
  • Nick Veldt

摘要

Given a set X, the power set \(\mathcal {P}(X)\) P ( X ) , and a finite poset \((P,\le _P)\) ( P , P ) , a family \(\mathcal {F}\subseteq \mathcal {P}(X)\) F P ( X ) is said to be induced-P-free if there is no injection \(\varphi : P\rightarrow \mathcal {F}\) φ : P F such that \(\varphi (p)\subseteq \varphi (q)\) φ ( p ) φ ( q ) if and only if \(p\le _{P} q\) p P q for every \(p,q \in P\) p , q P . The family \(\mathcal {F}\) F is induced-P-saturated if it is maximal with respect to being induced-P-free. If \(n=|X|\) n = | X | , then the size of the smallest induced-P-saturated family in \(\mathcal {P}(X)\) P ( X ) is denoted \(\textrm{sat}^*(n,P)\) sat ( n , P ) . The poset \(2C_2\) 2 C 2 is two incomparable 2-chains (the Hasse diagram is two vertex-disjoint edges) and Keszegh, Lemons, Martin, Pálvölgyi, and Patkós proved that \(n+2\le \textrm{sat}^*(n,2C_2)\le 2n\) n + 2 sat ( n , 2 C 2 ) 2 n and gave one isomorphism class of an induced- \(2C_2\) 2 C 2 -saturated family that achieves the upper bound. We show that the lower bound can be improved to \(3n/2 + 1/2\) 3 n / 2 + 1 / 2 by examining the necessary structure of a saturated family. In addition, we provide many examples of induced- \(2C_2\) 2 C 2 -saturated families of size 2n in \(\mathcal {P}(X)\) P ( X ) where \(|X|=n\) | X | = n .