<p>The Kneser cube <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(Kn_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>K</mi> <msub> <mi>n</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> has vertex set <InlineEquation ID="IEq2"> <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> and two vertices <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(F,F'\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>,</mo> <msup> <mi>F</mi> <mo>′</mo> </msup> </mrow> </math></EquationSource> </InlineEquation> are joined by an edge if and only if <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(F\cap F'=\emptyset \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>∩</mo> <msup> <mi>F</mi> <mo>′</mo> </msup> <mo>=</mo> <mi mathvariant="normal">∅</mi> </mrow> </math></EquationSource> </InlineEquation>. For a fixed graph <i>G</i>, we are interested in the most number <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\textrm{vex}(n,G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>vex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of vertices of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(Kn_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>K</mi> <msub> <mi>n</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> that span a <i>G</i>-free subgraph in <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(Kn_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>K</mi> <msub> <mi>n</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. We show that the asymptotics of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\textrm{vex}(n,G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>vex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\((1+o(1))2^{n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> for bipartite <i>G</i> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\((1-o(1))2^n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> for graphs with chromatic number at least 3. We also obtain results on the order of magnitude of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(2^{n-1}-\!\textrm{vex}(n,G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mo>-</mo> <mspace width="-0.166667em" /> <mtext>vex</mtext> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(2^n-\!\textrm{vex}(n,G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>-</mo> <mspace width="-0.166667em" /> <mtext>vex</mtext> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in these two cases. In the case of bipartite <i>G</i>, we relate this problem to instances of the forbidden subposet problem.</p>

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

A note on vertex Turán problems in the Kneser cube

  • Dániel Gerbner,
  • Balázs Patkós

摘要

The Kneser cube \(Kn_n\) K n n has vertex set \(2^{[n]}\) 2 [ n ] and two vertices \(F,F'\) F , F are joined by an edge if and only if \(F\cap F'=\emptyset \) F F = . For a fixed graph G, we are interested in the most number \(\textrm{vex}(n,G)\) vex ( n , G ) of vertices of \(Kn_n\) K n n that span a G-free subgraph in \(Kn_n\) K n n . We show that the asymptotics of \(\textrm{vex}(n,G)\) vex ( n , G ) is \((1+o(1))2^{n-1}\) ( 1 + o ( 1 ) ) 2 n - 1 for bipartite G and \((1-o(1))2^n\) ( 1 - o ( 1 ) ) 2 n for graphs with chromatic number at least 3. We also obtain results on the order of magnitude of \(2^{n-1}-\!\textrm{vex}(n,G)\) 2 n - 1 - vex ( n , G ) and \(2^n-\!\textrm{vex}(n,G)\) 2 n - vex ( n , G ) in these two cases. In the case of bipartite G, we relate this problem to instances of the forbidden subposet problem.