Given two vertex-ordered graphs <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$H_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>H</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$H_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>H</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>, the ordered Ramsey number <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$R_<(H_1,H_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mo><</mo> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>H</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the smallest N such that whenever the edges of a vertex-ordered complete graph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$K_N$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>N</mi> </msub> </math></EquationSource> </InlineEquation> are red/blue-coloured, then there is a red (ordered) copy of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$H_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>H</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> or a blue (ordered) copy of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$H_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>H</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$P_n^t$</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>P</mi> <mi>n</mi> <mi>t</mi> </msubsup> </math></EquationSource> </InlineEquation> denote the t-th power of a monotone path on n vertices. The ordered Ramsey numbers of powers of paths have been extensively studied. We prove that there exists an absolute constant C such that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$R_<(K_s,P_n^t)\le R(K_s,K_t)^{C} \cdot n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mo><</mo> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mi>s</mi> </msub> <mo>,</mo> <msubsup> <mi>P</mi> <mi>n</mi> <mi>t</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>R</mi> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mi>s</mi> </msub> <mo>,</mo> <msub> <mi>K</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mi>C</mi> </msup> <mo>·</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> holds for all s, t, n, which is tight up to the value of C. As a corollary, we obtain that there is an absolute constant C such that <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$R_<(K_n,P_n^t)\le n^{Ct}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mo><</mo> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mi>n</mi> </msub> <mo>,</mo> <msubsup> <mi>P</mi> <mi>n</mi> <mi>t</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msup> <mi>n</mi> <mrow> <mi mathvariant="italic">Ct</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. These results resolve a problem and a conjecture of Gishboliner, Jin and Sudakov. Furthermore, we show that <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$R_<(P_n^t,P_n^t)\le n^{4+o(1)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mo><</mo> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi>P</mi> <mi>n</mi> <mi>t</mi> </msubsup> <mo>,</mo> <msubsup> <mi>P</mi> <mi>n</mi> <mi>t</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msup> <mi>n</mi> <mrow> <mn>4</mn> <mo>+</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> for any fixed t. This answers questions of Balko, Cibulka, Král and Kynčl, and of Gishboliner, Jin and Sudakov.

Ordered Ramsey Numbers of Powers of Paths

期刊论文
出版模式：

开放获取
发表日期：

2026年7月29日

查看全文

António Girão,
Barnabás Janzer,
Oliver Janzer

摘要

Given two vertex-ordered graphs $H_1$ $H_{1}$ and $H_2$ $H_{2}$ , the ordered Ramsey number $R_<(H_1,H_2)$ $R_{<} (H_{1}, H_{2})$ is the smallest N such that whenever the edges of a vertex-ordered complete graph $K_N$ $K_{N}$ are red/blue-coloured, then there is a red (ordered) copy of $H_1$ $H_{1}$ or a blue (ordered) copy of $H_2$ $H_{2}$ . Let $P_n^t$ $P_{n}^{t}$ denote the t-th power of a monotone path on n vertices. The ordered Ramsey numbers of powers of paths have been extensively studied. We prove that there exists an absolute constant C such that $R_<(K_s,P_n^t)\le R(K_s,K_t)^{C} \cdot n$ $R_{<} (K_{s}, P_{n}^{t}) \leq R {(K_{s}, K_{t})}^{C} \cdot n$ holds for all s, t, n, which is tight up to the value of C. As a corollary, we obtain that there is an absolute constant C such that $R_<(K_n,P_n^t)\le n^{Ct}$ $R_{<} (K_{n}, P_{n}^{t}) \leq n^{Ct}$ . These results resolve a problem and a conjecture of Gishboliner, Jin and Sudakov. Furthermore, we show that $R_<(P_n^t,P_n^t)\le n^{4+o(1)}$ $R_{<} (P_{n}^{t}, P_{n}^{t}) \leq n^{4 + o (1)}$ for any fixed t. This answers questions of Balko, Cibulka, Král and Kynčl, and of Gishboliner, Jin and Sudakov.