<p>We prove a new lower bound on the Ramsey number <InlineEquation ID="IEq1"> <EquationSource Format="MATHML"><math> <mi>r</mi> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi>C</mi> <mi>ℓ</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$r(\ell , C\ell )$</EquationSource> </InlineEquation> for any constant <InlineEquation ID="IEq2"> <EquationSource Format="MATHML"><math> <mi>C</mi> <mo>></mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$C > 1$</EquationSource> </InlineEquation> and sufficiently large <InlineEquation ID="IEq3"> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> <EquationSource Format="TEX">$\ell $</EquationSource> </InlineEquation>, showing that there exists <InlineEquation ID="IEq4"> <EquationSource Format="MATHML"><math> <mi>ε</mi> <mo>=</mo> <mi>ε</mi> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> <mo>></mo> <mn>0</mn> </math></EquationSource> <EquationSource Format="TEX">$\varepsilon =\varepsilon (C)> 0$</EquationSource> </InlineEquation> such that <Equation ID="Equa"> <EquationSource Format="MATHML"><math> <mi>r</mi> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi>C</mi> <mi>ℓ</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <msup> <mrow> <mo>(</mo> <msubsup> <mi>p</mi> <mi>C</mi> <mrow> <mo>−</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msubsup> <mo>+</mo> <mi>ε</mi> <mo>)</mo> </mrow> <mi>ℓ</mi> </msup> <mo>,</mo> </math></EquationSource> <EquationSource Format="TEX">$ r(\ell , C\ell ) \geq \left (p_{C}^{-1/2} + \varepsilon \right )^{ \ell }, $</EquationSource> </Equation> where <InlineEquation ID="IEq5"> <EquationSource Format="MATHML"><math> <msub> <mi>p</mi> <mi>C</mi> </msub> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$p_{C} \in (0, 1/2)$</EquationSource> </InlineEquation> is the unique solution to <InlineEquation ID="IEq6"> <EquationSource Format="MATHML"><math> <mi>C</mi> <mo>=</mo> <mfrac> <mrow> <mo>log</mo> <msub> <mi>p</mi> <mi>C</mi> </msub> </mrow> <mrow> <mo>log</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <msub> <mi>p</mi> <mi>C</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mfrac> </math></EquationSource> <EquationSource Format="TEX">$C = \frac{\log p_{C}}{\log (1 - p_{C})}$</EquationSource> </InlineEquation>. This provides the first exponential improvement over the classical lower bound obtained by Erdős in 1947.</p>

An exponential improvement for Ramsey lower bounds

期刊论文
发表日期：

2026年5月4日

查看全文

Jie Ma,
Wujie Shen,
Shengjie Xie

摘要

We prove a new lower bound on the Ramsey number $r (ℓ, C ℓ)$ $r(\ell , C\ell )$ for any constant $C > 1$ $C > 1$ and sufficiently large $ℓ$ $\ell $ , showing that there exists $ε = ε (C) > 0$ $\varepsilon =\varepsilon (C)> 0$ such that $r (ℓ, C ℓ) \geq {(p_{C}^{- 1 / 2} + ε)}^{ℓ},$ $ r(\ell , C\ell ) \geq \left (p_{C}^{-1/2} + \varepsilon \right )^{ \ell }, $ where $p_{C} \in (0, 1 / 2)$ $p_{C} \in (0, 1/2)$ is the unique solution to $C = \frac{log p_{C}}{log (1 - p_{C})}$ $C = \frac{\log p_{C}}{\log (1 - p_{C})}$ . This provides the first exponential improvement over the classical lower bound obtained by Erdős in 1947.