For any positive integer k, let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$r_2(k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denote the smallest integer n such that every 2-edge-colored complete graph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$K_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> contains a monochromatic k-connected subgraph. Matula established the bound <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$4(k-1)+1 \le r_2(k) < (3+\sqrt{11/3})(k-1)+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>4</mn> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> <mo>≤</mo> <msub> <mi>r</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo><</mo> <mrow> <mo stretchy="false">(</mo> <mn>3</mn> <mo>+</mo> <msqrt> <mrow> <mn>11</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msqrt> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. It is known that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$r_2(k)=4(k-1)+1 for k=1,2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>4</mn> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> <mi>f</mi> <mi>o</mi> <mi>r</mi> <mi>k</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> (by Bollobás and Gyárfás) and for <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$k=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> (by Liu, Morris, and Prince). We prove that for <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$k \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$n>(3+\frac{\sqrt{497}-1}{16})(k-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>></mo> <mrow> <mo stretchy="false">(</mo> <mn>3</mn> <mo>+</mo> <mfrac> <mrow> <msqrt> <mn>497</mn> </msqrt> <mo>-</mo> <mn>1</mn> </mrow> <mn>16</mn> </mfrac> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, every 2-edge-colored <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$K_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> contains a monochromatic k-connected subgraph with at least <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$2(k-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> vertices. This result improves the upper bound of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$r_2(k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\lceil (3+\frac{\sqrt{497}-1}{16})(k-1) \rceil $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌈</mo> <mrow> <mo stretchy="false">(</mo> <mn>3</mn> <mo>+</mo> <mfrac> <mrow> <msqrt> <mn>497</mn> </msqrt> <mo>-</mo> <mn>1</mn> </mrow> <mn>16</mn> </mfrac> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>⌉</mo> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$k \ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>.

An upper bound for a ramsey type problem for k-connected subgraphs

期刊论文
发表日期：

2025年11月14日

查看全文

Murong Chen,
Qiqin Xie

摘要

For any positive integer k, let $r_2(k)$ $r_{2} (k)$ denote the smallest integer n such that every 2-edge-colored complete graph $K_n$ $K_{n}$ contains a monochromatic k-connected subgraph. Matula established the bound $4(k-1)+1 \le r_2(k) < (3+\sqrt{11/3})(k-1)+1$ $4 (k - 1) + 1 \leq r_{2} (k) < (3 + \sqrt{11 / 3}) (k - 1) + 1$ . It is known that $r_2(k)=4(k-1)+1 for k=1,2$ $r_{2} (k) = 4 (k - 1) + 1 f o r k = 1, 2$ (by Bollobás and Gyárfás) and for $k=3$ $k = 3$ (by Liu, Morris, and Prince). We prove that for $k \ge 2$ $k \geq 2$ and $n>(3+\frac{\sqrt{497}-1}{16})(k-1)$ $n > (3 + \frac{\sqrt{497} - 1}{16}) (k - 1)$ , every 2-edge-colored $K_n$ $K_{n}$ contains a monochromatic k-connected subgraph with at least $2(k-1)$ $2 (k - 1)$ vertices. This result improves the upper bound of $r_2(k)$ $r_{2} (k)$ to $\lceil (3+\frac{\sqrt{497}-1}{16})(k-1) \rceil $ $⌈ (3 + \frac{\sqrt{497} - 1}{16}) (k - 1) ⌉$ for all $k \ge 4$ $k \geq 4$ .