<p>Let <i>n</i> be a positive integer. A collection <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{S}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">S</mi> </math></EquationSource> </InlineEquation> of subsets of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="119" /> </InlineMediaObject> <EquationSource Format="TEX">\([n]=\{1,\ldots ,n\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is called <i>symmetric</i> if <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(X\in \mathcal{S}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>∈</mo> <mi mathvariant="script">S</mi> </mrow> </math></EquationSource> </InlineEquation> implies <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(X^*\in \mathcal{S}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>X</mi> <mo>∗</mo> </msup> <mo>∈</mo> <mi mathvariant="script">S</mi> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="231" /> </InlineMediaObject> <EquationSource Format="TEX">\(X^*:=\{i\in [n]:n-i+1\notin X\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>X</mi> <mo>∗</mo> </msup> <mo>:</mo> <mo>=</mo> <mrow> <mo stretchy="false">{</mo> <mi>i</mi> <mo>∈</mo> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> <mo>:</mo> <mi>n</mi> <mo>-</mo> <mi>i</mi> <mo>+</mo> <mn>1</mn> <mo>∉</mo> <mi>X</mi> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. As the main results of this paper, one shows that in each of the three types of separation relations: <i>strong</i>, <i>weak</i> and <i>chord</i> ones, the following “purity phenomenon” takes place: all inclusion-wise maximal symmetric separated collections in <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq6.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(2^{[n]}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> </msup> </math></EquationSource> </InlineEquation> have the same cardinality. These give “symmetric versions” of well-known results on the purity of usual strongly, weakly and chord separated collections of subsets of [<i>n</i>], and in the case of weak separation, this extends a result due to Karpman on the purity of symmetric weakly separated collections in <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="29_2025_1025_Article_IEq7.gif" Format="GIF" Height="43" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(\left( {\begin{array}{c}[n]\\ n/2\end{array}}\right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> </math></EquationSource> </InlineEquation> for <i>n</i> even.</p>

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

The purity phenomenon for symmetric separated set-systems

  • Vladimir I. Danilov,
  • Alexander V. Karzanov,
  • Gleb A. Koshevoy

摘要

Let n be a positive integer. A collection \(\mathcal{S}\) S of subsets of \([n]=\{1,\ldots ,n\}\) [ n ] = { 1 , , n } is called symmetric if \(X\in \mathcal{S}\) X S implies \(X^*\in \mathcal{S}\) X S , where \(X^*:=\{i\in [n]:n-i+1\notin X\}\) X : = { i [ n ] : n - i + 1 X } . As the main results of this paper, one shows that in each of the three types of separation relations: strong, weak and chord ones, the following “purity phenomenon” takes place: all inclusion-wise maximal symmetric separated collections in \(2^{[n]}\) 2 [ n ] have the same cardinality. These give “symmetric versions” of well-known results on the purity of usual strongly, weakly and chord separated collections of subsets of [n], and in the case of weak separation, this extends a result due to Karpman on the purity of symmetric weakly separated collections in \(\left( {\begin{array}{c}[n]\\ n/2\end{array}}\right) \) [ n ] n / 2 for n even.