<p>For graphs <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(G_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>, the Ramsey number <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(R(G_1, G_2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>G</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is the smallest integer <i>n</i> such that every graph of order <i>n</i> either contains <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> as a subgraph or its complement contains <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(G_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> as a subgraph. A wheel <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(W_m\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> is formed by connecting a vertex to every vertex of a cycle <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(C_m\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation>, while a fan <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(F_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> consists of <i>n</i> triangles sharing a common vertex. Hao and You (2023) established that <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(R(W_4, F_n) = 4n+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msub> <mi>W</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>F</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mn>4</mn> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for sufficiently large <i>n</i>, where the required lower bound on <i>n</i> is of exponential tower type, a consequence of their reliance on the Erdős-Simonovits stability theorem. We significantly improve this result by proving that the same formula holds for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(n \ge 111\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>111</mn> </mrow> </math></EquationSource> </InlineEquation>. Moreover, by applying the stability theorem, we further generalize this result by replacing <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(W_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(W_{2m}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mrow> <mn>2</mn> <mi>m</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, proving that for <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(m \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and large <i>n</i>, <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(R(W_{2m}, F_n)=4n+m-\mu \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msub> <mi>W</mi> <mrow> <mn>2</mn> <mi>m</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>F</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mn>4</mn> <mi>n</mi> <mo>+</mo> <mi>m</mi> <mo>-</mo> <mi>μ</mi> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\mu =1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> if <i>m</i> is even, and <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\mu =0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> if <i>m</i> is odd. As a final extension, we consider the class <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\mathcal {W}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">W</mi> </math></EquationSource> </InlineEquation> of all wheels and show that <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(R(\mathcal {W}, F_n)=4n+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">W</mi> <mo>,</mo> <msub> <mi>F</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mn>4</mn> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(n\ge 16.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>16</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

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

Ramsey Numbers of Small Wheels Versus Fans

  • Haiyu Zeng,
  • Yanbo Zhang,
  • Feng Zhao

摘要

For graphs \(G_1\) G 1 and \(G_2\) G 2 , the Ramsey number \(R(G_1, G_2)\) R ( G 1 , G 2 ) is the smallest integer n such that every graph of order n either contains \(G_1\) G 1 as a subgraph or its complement contains \(G_2\) G 2 as a subgraph. A wheel \(W_m\) W m is formed by connecting a vertex to every vertex of a cycle \(C_m\) C m , while a fan \(F_n\) F n consists of n triangles sharing a common vertex. Hao and You (2023) established that \(R(W_4, F_n) = 4n+1\) R ( W 4 , F n ) = 4 n + 1 for sufficiently large n, where the required lower bound on n is of exponential tower type, a consequence of their reliance on the Erdős-Simonovits stability theorem. We significantly improve this result by proving that the same formula holds for \(n \ge 111\) n 111 . Moreover, by applying the stability theorem, we further generalize this result by replacing \(W_4\) W 4 with \(W_{2m}\) W 2 m , proving that for \(m \ge 2\) m 2 and large n, \(R(W_{2m}, F_n)=4n+m-\mu \) R ( W 2 m , F n ) = 4 n + m - μ , where \(\mu =1\) μ = 1 if m is even, and \(\mu =0\) μ = 0 if m is odd. As a final extension, we consider the class \(\mathcal {W}\) W of all wheels and show that \(R(\mathcal {W}, F_n)=4n+1\) R ( W , F n ) = 4 n + 1 for all \(n\ge 16.\) n 16 .