arxiv: 2605.12318 · v1 · submitted 2026-05-12 · 🧮 math.CO

Recognition: no theorem link

A stepping-up lemma for monotone paths with bounded color complexity

Hyunwoo Lee, Jigang Choi

Pith reviewed 2026-05-13 03:14 UTC · model grok-4.3

classification 🧮 math.CO MSC 05D1005C65

keywords Ramsey numbersmonotone pathsstepping-up lemmaMorse-Hedlund theoremhypergraph coloringsErdős-Szekeres problemtower functionscombinatorics on words

0 comments

The pith

For any fixed p the generalized Ramsey number A_k(n; q, p) grows at least as a tower of height linear in k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves the first nontrivial lower bound on A_k(n; q, p), the largest N such that some q-coloring of the edges of the complete k-uniform hypergraph on N vertices avoids any tight monotone path of length n that uses at most p colors. By building a new stepping-up construction that lifts lower-dimensional colorings while keeping the avoided paths restricted to p colors, the authors show A_k(n; q, p) is at least a tower of height floor(k over C_p) with top exponent n raised to a q-dependent power that tends to infinity. This holds for every fixed p once n, k and q are large enough relative to p. A reader cares because the bound demonstrates that limiting the path to p colors does not destroy the tower-type growth that appears in ordinary monotone-path Ramsey problems.

Core claim

For every fixed positive integer p there is a constant C_p > 0 depending only on p such that A_k(n; q, p) is at least the tower function T of height floor(k / C_p) evaluated at n raised to the power omega_q(1), for all sufficiently large n, k and q. The proof proceeds by a variant of the classical stepping-up lemma that produces q-colorings of higher-uniformity hypergraphs from lower ones while ensuring that every tight monotone path still requires more than p colors; the key supporting fact is a finite analogue of the Morse-Hedlund theorem that controls the combinatorial complexity of the color sequences arising in the construction.

What carries the argument

A novel variant of the stepping-up lemma that lifts edge colorings from (k-1)-uniform to k-uniform hypergraphs while preserving the property that every tight monotone path in the new coloring uses more than p colors, supported by a finite Morse-Hedlund theorem that guarantees the color sequences have high complexity.

If this is right

The quantity A_k(n; q, p) is at least a tower of height proportional to k for every fixed p.
The bounded-color-complexity restriction on the avoided path does not reduce the asymptotic tower height below a linear fraction of k.
Lower bounds for ordinary (p=1) monotone-path Ramsey numbers can be transferred to the p-color setting via the new stepping-up method.
When p is fixed the known upper bounds of tower height k-3 cannot be tight in the height parameter.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The finite Morse-Hedlund result may apply to other sequence-avoidance problems that arise in combinatorial word theory or canonical Ramsey theorems.
The stepping-up technique could be adapted to let p grow slowly with q while still obtaining towers of height linear in k.
Improving the dependence of C_p on p would close more of the gap with existing upper bounds.
Similar constructions might yield lower bounds for other restricted-path variants of the Erdős-Szekeres problem in hypergraphs.

Load-bearing premise

The new stepping-up construction produces colorings in which every tight monotone path still requires more than p colors, and this preservation depends on the finite Morse-Hedlund theorem holding for the sequences that appear.

What would settle it

Exhibit a q-edge-coloring of K_M^{(k)} for M smaller than the claimed tower height that contains no tight monotone path of length n using at most p colors, or produce a finite sequence violating the claimed Morse-Hedlund bound for the parameters used in the construction.

read the original abstract

For positive integers $n, k, q, p$, let $A_k(n; q, p)$ be the largest integer $N$ such that there exists an edge coloring of $K_N^{(k)}$ with $q$ colors that does not contain a tight monotone path of length $n$ that consists of at most $p$ colors. In the case $p = 1$, this coincides with the ordinary Ramsey number of a tight monotone path, and it is known that $A_k(n; q, 1) = T_{k-2}(n^{\Theta(q)})$, proved by Moshkovitz and Shapira. Recently, Mulrenin, Pohoata, and Zakharov showed that whenever $p > \frac{q}{2}$, an improved upper bound $A_k(n; q, p) \leq T_{k-3}(n^{O(q)})$ holds, without any accompanying lower bounds. In this paper, we obtain the first non-trivial lower bound by developing a novel variant of the classical stepping-up lemma applicable to an Erd\H{o}s--Szekeres-type problem in which one seeks a tight monotone path spanning at most $p$ colors. In particular, we show that for any fixed $p \geq 1$, there exists a constant $C_p > 0$ that only depends on $p$ such that $$ A_{k}(n; q, p) \geq T_{\lfloor k/ C_p \rfloor}\left(n^{\omega_q(1)}\right) $$ holds for all sufficiently large $n, k, q$ compared with $p$, that is, a tower function whose height grows linearly in $k$. A key ingredient in our proof is establishing a finite analogue of the celebrated Morse--Hedlund theorem, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper supplies the first lower bound showing A_k(n; q, p) grows as a tower of height linear in k for fixed p, via a new stepping-up lemma and finite Morse-Hedlund theorem.

read the letter

The main point is that the authors close the lower-bound side of the gap left by Mulrenin-Pohoata-Zakharov. For any fixed p they get A_k(n; q, p) at least a tower of height roughly k over C_p, with the exponent on n being some positive function of q that goes to infinity. This matches the tower height in the known upper bounds up to the constant in the denominator, which is new for p greater than 1. The p=1 case was already settled by Moshkovitz-Shapira, but nothing comparable existed before for general p. They achieve it with an explicit combinatorial construction that lifts a lower-dimensional coloring while keeping the avoided monotone path inside p colors. The key new ingredient is a finite Morse-Hedlund theorem proved by a direct counting argument on distinct subwords of an auxiliary sequence; this gives an explicit linear bound in p that prevents the color complexity from growing during the lift. The reduction factor C_p comes from a fixed number of base-case applications plus this complexity control, and the choices stay uniform in q once p is fixed. The argument looks solid on the details supplied. No circularity or hidden growth-rate assumptions appear to break the induction, and the construction is self-contained. Minor soft spots are that the precise form of the omega_q(1) exponent is not optimized and C_p is left as an existence constant rather than computed, but these are standard in stepping-up work and do not affect the main claim. This is for people working on hypergraph Ramsey numbers, multicolored Erdős-Szekeres problems, or stepping-up techniques in general. The Morse-Hedlund analogue may interest readers outside the immediate application. The paper deserves a serious referee because the result is new, the proofs are explicit, and the gap it closes is real. I would send it out for peer review.

Referee Report

0 major / 3 minor

Summary. The paper defines A_k(n; q, p) as the largest N such that the complete k-uniform hypergraph on N vertices admits a q-edge-coloring with no tight monotone path of length n using at most p colors. For p=1 this recovers the known value T_{k-2}(n^{Θ(q)}). The main result is a lower bound: for any fixed p ≥ 1 there exists C_p > 0 (depending only on p) such that A_k(n; q, p) ≥ T_{⌊k/C_p⌋}(n^{ω_q(1)}) for all sufficiently large n, k, q relative to p. The proof proceeds via a new stepping-up construction that reduces dimension while preserving the p-color bound, supported by a finite analogue of the Morse-Hedlund theorem proved by direct subword counting.

Significance. If correct, the result supplies the first non-trivial lower bounds for A_k(n; q, p) when p > 1, establishing that the tower height still grows linearly in k (with a p-dependent slowdown factor). This complements the upper bounds of Mulrenin-Pohoata-Zakharov and introduces an explicit finite Morse-Hedlund analogue whose linear-in-p complexity bound is obtained by elementary counting; both the explicit construction and the self-contained proof of the word-complexity lemma are strengths.

minor comments (3)

[Abstract] The notation n^{ω_q(1)} is used without an explicit definition in the abstract or introduction; a sentence clarifying that the exponent tends to infinity with q (or stating the precise growth) would improve readability.
[Theorem 1.1] In the statement of the main theorem, the phrase 'sufficiently large n, k, q compared with p' is informal; replacing it with an explicit quantifier (e.g., 'for all n, k, q ≥ f(p) for some function f') would make the dependence precise.
[Section 4] The finite Morse-Hedlund lemma is stated with an O(p m) bound on distinct subwords; a short remark on how this bound is applied in the lifting step to keep total color complexity ≤ p would help readers follow the induction without consulting the full proof.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript, including the accurate summary of the definition of A_k(n; q, p) and the main lower bound. The recommendation for minor revision is noted, and we will incorporate improvements to presentation and clarity.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation relies on an explicit combinatorial stepping-up construction that reduces the k-dimensional problem to a lower-dimensional instance plus a new finite Morse-Hedlund theorem proved by direct counting on subword complexity (linear in p). All constants C_p are uniform and arise from a fixed number of applications of the base case; no parameters are fitted to the target quantity, no self-citations are load-bearing, and no ansatz or uniqueness theorem is imported from prior author work. The central lower bound therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The claim rests on a new finite analogue of the Morse-Hedlund theorem (established in the paper) and a variant of the classical stepping-up construction. The only explicit parameter is the existential constant C_p that controls tower height.

free parameters (1)

C_p
Positive constant depending only on p that determines the linear factor in the tower height; its existence is asserted but not computed explicitly.

axioms (1)

ad hoc to paper A finite analogue of the Morse-Hedlund theorem holds for the color sequences arising in the stepping-up construction.
This new result is proved in the paper and used as the central technical ingredient to control color complexity.

pith-pipeline@v0.9.0 · 5646 in / 1419 out tokens · 200431 ms · 2026-05-13T03:14:35.890151+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

Arag˜ ao, M

L. Arag˜ ao, M. Collares, J. P. Marciano, T. Martins, and R. Morris,A lower bound for set-coloring Ramsey numbers, Random Structures Algorithms64(2024), no. 2, 157–169

work page 2024
[2]

Choi and H

J. Choi and H. Lee,Note on improved upper bound for color-avoiding Moshkovitz–Shapira theorem, (2026), Manuscript in preparation

work page 2026
[3]

Conlon, J

D. Conlon, J. Fox, X. He, D. Mubayi, A. Suk, and J. Verstra¨ ete,Set-coloring Ramsey numbers via codes, Studia Sci. Math. Hungar.61(2024), no. 1, 1–15

work page 2024
[4]

Dubroff, A

Q. Dubroff, A. Gir˜ ao, E. Hurley, and C. Yap,Tower gaps in multicolour Ramsey numbers, Forum Math. Sigma11(2023), Paper No. e84, 15

work page 2023
[5]

Eli´ aˇ s and J

M. Eli´ aˇ s and J. Matouˇ sek,Higher-order Erd˝ os-Szekeres theorems, Adv. Math.244(2013), 1–15

work page 2013
[6]

Erd˝ os, A

P. Erd˝ os, A. Hajnal, and R. Rado,Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar.16(1965), 93–196

work page 1965
[7]

Erd˝ os and G

P. Erd˝ os and G. Szekeres,A combinatorial problem in geometry, Compositio Math.2 (1935), 463–470. 16

work page 1935
[8]

Erd˝ os and A

P. Erd˝ os and A. Szemer´ edi,On a Ramsey type theorem, Period. Math. Hungar.2(1972), 295–299

work page 1972
[9]

Falgas-Ravry, E

V. Falgas-Ravry, E. R¨ aty, and I. Tomon,Dedekind’s problem in the hypergrid, Adv. Math. 488(2026), Paper No. 110796, 41

work page 2026
[10]

J. Fox, J. Pach, B. Sudakov, and A. Suk,Erd˝ os-Szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. (3)105(2012), no. 5, 953–982

work page 2012
[11]

J. Fox, B. Sudakov, and Y. Wigderson,Color-avoiding directed paths in tournaments, arXiv:2512.10438, 2025

work page arXiv 2025
[12]

W. T. Gowers and J. Long,The length of ans-increasing sequence ofr-tuples, Combin. Probab. Comput.30(2021), no. 5, 686–721

work page 2021
[13]

R. L. Graham, B. L. Rothschild, and J. H. Spencer,Ramsey theory, paperback ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2013

work page 2013
[14]

Loh,Directed paths: from Ramsey to Ruzsa and Szemer´ edi, (2015),arXiv:1505

P.-S. Loh,Directed paths: from Ramsey to Ruzsa and Szemer´ edi, (2015),arXiv:1505. 07312

work page 2015
[15]

Morse and G

M. Morse and G. A. Hedlund,Symbolic Dynamics, Amer. J. Math.60(1938), no. 4, 815– 866

work page 1938
[16]

Moshkovitz and A

G. Moshkovitz and A. Shapira,Ramsey theory, integer partitions and a new proof of the Erd˝ os-Szekeres theorem, Adv. Math.262(2014), 1107–1129

work page 2014
[17]

Mulrenin, C

E. Mulrenin, C. Pohoata, and D. Zakharov,Color avoidance for monotone paths, Discrete Anal. (2025), Paper No. 23, 14

work page 2025
[18]

J. Park, M. Sarantis, and P. Tetali,Note on the number of antichains in generalizations of the Boolean lattice, Comb. Theory5(2025), no. 1, Paper No. 7, 20

work page 2025
[19]

Pohoata and D

C. Pohoata and D. Zakharov,On the number of high-dimensional partitions, Proc. Lond. Math. Soc. (3)128(2024), no. 2, Paper No. e12586, 12. 17

work page 2024