<p>DeBiasio and Krueger showed the following result: For all 0 ≤ <i>δ</i> ≤ 1 and <i>ϵ</i> &gt; 0, there exists <i>n</i><sub>0</sub> such that if <i>G</i> is a balanced bipartite graph on 2<i>n</i> ≥ 2<i>n</i><sub>0</sub> vertices with <i>δ</i>(<i>G</i>) = <i>δn</i>, then in every 2-coloring of G, there exists a monochromatic cycle of order at least (<i>f</i>(<i>δ</i>) − <i>ϵ</i>)<i>n</i>, where <Equation ID="Equa"> <EquationSource Format="TEX">\(f(\delta)=\begin{cases}{\delta}, &amp; {0 \leq \delta \leq {2 \over 3}},\\{4{\delta}-2}, &amp; {{2 \over 3} &lt; \delta \leq {3 \over 4}},\\1, &amp; {3 \over 4} &lt; \delta \leq 1.\end{cases}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>δ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow> <mo>{</mo> <mtable columnalign="left" columnspacing="1em" displaystyle="false" rowspacing=".2em"> <mtr> <mtd> <mrow> <mi>δ</mi> </mrow> <mo>,</mo> </mtd> <mtd> <mrow> <mn>0</mn> <mo>≤</mo> <mi>δ</mi> <mo>≤</mo> <mrow> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </mrow> </mrow> <mo>,</mo> </mtd> </mtr> <mtr> <mtd> <mrow> <mn>4</mn> <mrow> <mi>δ</mi> </mrow> <mo>−</mo> <mn>2</mn> </mrow> <mo>,</mo> </mtd> <mtd> <mrow> <mrow> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </mrow> <mo>&lt;</mo> <mi>δ</mi> <mo>≤</mo> <mrow> <mfrac> <mn>3</mn> <mn>4</mn> </mfrac> </mrow> </mrow> <mo>,</mo> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> <mo>,</mo> </mtd> <mtd> <mrow> <mfrac> <mn>3</mn> <mn>4</mn> </mfrac> </mrow> <mo>&lt;</mo> <mi>δ</mi> <mo>≤</mo> <mn>1.</mn> </mtd> </mtr> </mtable> <mo fence="true" stretchy="true" /> </mrow> </math></EquationSource> </Equation> Zhang and Peng (2023) extended the above result to off-diagonal cases when <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({\delta} &gt; {3 \over 4}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi>δ</mi> </mrow> <mo>&gt;</mo> <mrow> <mfrac> <mn>3</mn> <mn>4</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we relax the condition <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\delta} &gt; {3 \over 4}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi>δ</mi> </mrow> <mo>&gt;</mo> <mrow> <mfrac> <mn>3</mn> <mn>4</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({\delta} &gt; {2 \over 3}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi>δ</mi> </mrow> <mo>&gt;</mo> <mrow> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>. We show the following result: For every <i>η</i> &gt; 0, there exists a positive integer <i>N</i><sub>0</sub> such that for every integer <i>N</i> &gt; <i>N</i><sub>0</sub> the following holds. Let <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\({2 \over 3} &lt; {\delta} \leq {3 \over 4}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </mrow> <mo>&lt;</mo> <mrow> <mi>δ</mi> </mrow> <mo>≤</mo> <mrow> <mfrac> <mn>3</mn> <mn>4</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, and let <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\({\alpha_1} \geq {{\delta\alpha}_{2} \over {3\delta - 2}} &gt; 0\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <msub> <mi>α</mi> <mn>1</mn> </msub> </mrow> <mo>≥</mo> <mrow> <mfrac> <msub> <mrow> <mi>δ</mi> <mi>α</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msub> <mrow> <mn>3</mn> <mi>δ</mi> <mo>−</mo> <mn>2</mn> </mrow> </mfrac> </mrow> <mo>&gt;</mo> <mn>0</mn> </math></EquationSource> </InlineEquation> such that <i>α</i><sub>1</sub> + <i>α</i><sub>2</sub> = 1. Let <i>G</i>[<i>X, Y</i>] be a balanced bipartite graph on 2<i>N</i> vertices with <i>δ</i>(<i>G</i>) = (<i>δ</i> + 3<i>η</i>)<i>N</i>. Then for each red-blue-edge-coloring of <i>G</i>, either there exist red even cycles of each length in {4, 6, 8, …, 2(2<i>δ</i> − 1)(2 − 3<i>η</i><sup>2</sup>)<i>α</i><sub>1</sub><i>N</i>}, or there exist blue even cycles of each length in {4, 6, 8, …, 2(2<i>δ</i> − 1)(2 − 3<i>δ</i><sup>2</sup>)<i>α</i><sub>2</sub><i>N</i>}. There are constructions of colorings showing that the length of a longest monochromatic cycle is asymptotically tight and the condition <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\({\alpha_1} \geq {{\delta\alpha}_{2} \over {3\delta - 2}}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <msub> <mi>α</mi> <mn>1</mn> </msub> </mrow> <mo>≥</mo> <mrow> <mfrac> <msub> <mrow> <mi>δ</mi> <mi>α</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msub> <mrow> <mn>3</mn> <mi>δ</mi> <mo>−</mo> <mn>2</mn> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation> cannot be removed.</p>

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

Monochromatic Cycles in 2-edge-colored Bipartite Graphs

  • Yiran Zhang,
  • Yuejian Peng

摘要

DeBiasio and Krueger showed the following result: For all 0 ≤ δ ≤ 1 and ϵ > 0, there exists n0 such that if G is a balanced bipartite graph on 2n ≥ 2n0 vertices with δ(G) = δn, then in every 2-coloring of G, there exists a monochromatic cycle of order at least (f(δ) − ϵ)n, where \(f(\delta)=\begin{cases}{\delta}, & {0 \leq \delta \leq {2 \over 3}},\\{4{\delta}-2}, & {{2 \over 3} < \delta \leq {3 \over 4}},\\1, & {3 \over 4} < \delta \leq 1.\end{cases}\) f ( δ ) = { δ , 0 δ 2 3 , 4 δ 2 , 2 3 < δ 3 4 , 1 , 3 4 < δ 1. Zhang and Peng (2023) extended the above result to off-diagonal cases when \({\delta} > {3 \over 4}\) δ > 3 4 . In this paper, we relax the condition \({\delta} > {3 \over 4}\) δ > 3 4 to \({\delta} > {2 \over 3}\) δ > 2 3 . We show the following result: For every η > 0, there exists a positive integer N0 such that for every integer N > N0 the following holds. Let \({2 \over 3} < {\delta} \leq {3 \over 4}\) 2 3 < δ 3 4 , and let \({\alpha_1} \geq {{\delta\alpha}_{2} \over {3\delta - 2}} > 0\) α 1 δ α 2 3 δ 2 > 0 such that α1 + α2 = 1. Let G[X, Y] be a balanced bipartite graph on 2N vertices with δ(G) = (δ + 3η)N. Then for each red-blue-edge-coloring of G, either there exist red even cycles of each length in {4, 6, 8, …, 2(2δ − 1)(2 − 3η2)α1N}, or there exist blue even cycles of each length in {4, 6, 8, …, 2(2δ − 1)(2 − 3δ2)α2N}. There are constructions of colorings showing that the length of a longest monochromatic cycle is asymptotically tight and the condition \({\alpha_1} \geq {{\delta\alpha}_{2} \over {3\delta - 2}}\) α 1 δ α 2 3 δ 2 cannot be removed.