Multicolor Ramsey numbers of ordered matchings

arXiv:2609.08157 · math.CO · Submitted 2026-09-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Multicolor Ramsey numbers of ordered matchings".

Emmy: Here's the gist of the paper. For an ordered graph H and an integer q ≥ 2, let r.

Ada: This paper investigates lower bounds for multicolor Ramsey numbers of ordered matchings and oriented graphs, showing that almost every perfect matching satisfies a certain growth rate <ref:2609.08157#pg2>.

Emmy: The central finding is that for every q ≥ 2, there exists a constant cq > 0 such that almost every perfect matching M on

n: satisfies r 2cq(log n)q/(log log n)(q-1) <ref:2609.08157#pg2>.

Ada: This result matches the general upper bound up to a factor of (log log n)(q-1) in the exponent <ref:2609.08157#pg2>.

Title and authors: Ada: So we're looking at this paper today, "Multicolor Ramsey numbers of ordered matchings," and it’s by Xiangyu Li, though they've got some other people involved too ARU18 page one <ref:2609.08157#pg1,Multicolor Ramsey numbers of ordered matchings>. It really dives into the question of how many colors you need to guarantee you find a certain pattern in an ordered graph when you have a perfect matching on it ARU18 page two <ref:2609.08157#pg1>.

Emmy: It’s interesting because it looks at this specific setup where the vertices have an order, and copies of those graphs must respect that order ARU18 page one <ref:2609.08157#pg1>. This whole area is about how structure behaves when you impose a linear sequence on everything ARU18 page one <ref:2609.08157#pg1>.

Kolya: What I see immediately is that they’re setting up a problem where you have an ordered graph H and you want to know the Ramsey number for it in q colors, denoted as r<(H; q) ARU18 page one <ref:2609.08157#pg1,an ordered graph H and>. It’s about finding a threshold for when this number starts growing quite fast ARU18 page two <ref:2609.08157#pg1>.

Ada: Right, so they are looking at the upper bound versus the lower bound for these Ramsey numbers in general, and what that tells us about how quickly these numbers can grow with the size of the graph ARU18 page one <ref:2609.08157#pg1>.

Emmy: It’s a big deal because it connects this specific matching problem to broader questions about ordered graphs and their chromatic numbers ARU18 page two <ref:2609.08157#pg1>. We need to see if this structure hints at something deeper in how these graphs are built ARU18 page two <ref:2609.08157#pg1>.

Kolya: So, the core idea seems to be proving that for almost every perfect matching on n vertices, this Ramsey number exceeds a certain growth rate defined by q and n ARU18 page two] <ref:2609.08157#pg1,for almost every perfect matching>. It’s about showing that things don't stay too small ARU18 page two] <ref:2609.08157#pg1>.

The paper's summary: Ada: What the authors are actually doing in this paper is tackling the question of whether you can find a specific ordered matching M on n vertices such that the q-color ordered Ramsey number for it, r<(M; q), is larger than some specific value ARU18 page one] <ref:2609.08157#pg1,ordered matching M on n vertices>. They show that for every q greater than or equal to two, there’s some positive constant c with respect to n such that almost every perfect matching M on n vertices satisfies this lower bound ARU18 page two] <ref:2609.08157#pg1,such that almost every perfect matching M on n>.

Emmy: And they connect this finding directly to a general upper bound they already have, which is about the growth rate of these numbers in terms of q and n ARU18 page one] <ref:2609.08157#pg1>. They show that their lower bound matches the general upper bound up to a factor of log log n raised to the power of q minus one in the exponent ARU18 page two] <ref:2609.08157#pg1,matches the general upper bound up to a factor of log log>.

Kolya: From my side, what this means is they are establishing a concrete, almost certain behavior for these Ramsey numbers based on which matching you pick ARU18 page two] <ref:2609.08157#pg1>. It suggests that you can't always find a matching that stays small in terms of this Ramsey number ARU18 page two] <ref:2609.08157#pg1>.

Ada: So it’s not just about existence; it’s about almost every perfect matching having this specific growth rate, which is pretty strong ARU18 page two] <ref:2609.08157#pg1>. This result also gives them a way to prove the lower bound for that conjecture mentioned earlier by Fox, He and Wigderson

FHW24, Conjecture six point three: ARU18 page two] <ref:2609.08157#pg2,Fox, He and Wigderson FHW24, Conjecture 6.3>.

Emmy: That connection is what’s fascinating because it shows how this specific matching problem feeds into those larger conjectures about acyclic digraphs of bounded degree ARU18 page two] <ref:2609.08157#pg1,acyclic digraphs of bounded degree>. It really ties the structure of the matching to the overall complexity of ordered graphs ARU18 page two] <ref:2609.08157#pg1>.

The paper's improvements: Ada: Now, looking at what they actually propose as an improvement or application, they’re using this result to prove a lower bound for oriented Ramsey numbers of acyclic digraphs H ARU18 page two] <ref:2609.08157#pg1,Ramsey numbers of acyclic digraphs>. They are saying that for fixed q greater than or equal to two and some degree delta greater than or equal to three, there is a lower bound on these oriented Ramsey numbers, which is roughly the log n raised to the power of two over the log log n ARU18 page two] <ref:2609.08157#pg1>.

Emmy: That lower bound they’re giving is tied to a conjecture that says you can find some degree delta greater than or equal to three and constants c with respect to q such that this oriented Ramsey number is at most something like the logarithm of n raised to the power of two over log log n ARU18 page two] <ref:2609.08157#pg1>. It’s an equivalence between a lower bound they found and what people conjectured ARU18 page two] <ref:2609.08157#pg1>.

Kolya: From a probabilistic point of view, this means they’re showing that even when you look at oriented structures, the number of colors required doesn't just stay logarithmic as fast as we might think ARU18 page two] <ref:2609.08157#pg1>. It suggests that the exponent in the lower bound can actually grow with q ARU18 page two] <ref:2609.08157#pg1>.

Ada: So it’s showing that this lower bound exponent can tend to infinity with q while the upper-bound exponent grows subexponentially ARU18 page three] <ref:2609.08157#pg1>. That’s a big contrast in how these bounds behave depending on whether you're looking at the lower or upper side ARU18 page three] <ref:2609.08157#pg1>.

Emmy: It shows that while the lower boundexponent can grow with q, the upper-boundexponent grows subexponentially ARU18 page three] <ref:2609.08157#pg1>. This is a key distinction in understanding how these two sides of the Ramsey number problem interact ARU18 page three] <ref:2609.08157#pg1>.

Conclusion: Ada: So to wrap up on this paper, the main thing is that they’ve proven the lower bound part of Conjecture one point three with delta equals three and an exponent that is q minus some small amount ARU18 page two] <ref:2609.08157#pg1>. This leads to a corollary where for any fixed q greater than or equal to two, as n gets bigger, the logarithm of the Ramsey number for an acyclic digraph H with degree three is at least proportional to log n raised to the power of q divided by log log n raised to the power of q minus one ARU18 page two] <ref:2609.08157#pg1>.

Emmy: That means we have a concrete lower bound on how large these oriented Ramsey numbers can be when you restrict the structure of the digraph H ARU18 page two] <ref:2609.08157#pg1>. It’s a solid step forward in understanding the structural constraints involved ARU18 page three] <ref:2609.08157#pg1>.

Kolya: I just want to add that since they proved this for q minus some small amount, it sets a very high bar for what we expect as n gets really large ARU18 page two] <ref:2609.08157#pg1>. It suggests that the structure they found is quite robust ARU18 page two] <ref:2609.08157#pg1>.

Ada: Exactly. So this work on "Multicolor Ramsey numbers of ordered matchings" gives us a very detailed look at how almost every perfect matching on n vertices behaves in terms of these Ramsey bounds ARU18 page two] <ref:2609.08157#pg1,Multicolor Ramsey numbers of ordered matchings>. It’s a deep dive into the systematic study of ordered Ramsey numbers ARU18 page two] <ref:2609.08157#pg1>.

Emmy: Indeed, it really shows how much structure is hidden within these mathematical objects, and we've got a lot more to unpack in this area ARU18 page three] <ref:2609.08157#pg1>.

Xiangyu Li

University of Toronto

math.CO

Submitted: 2026-09-08

Updated: 2026-10-31

Comments: 6 pages, no figures. Minor revisions to exposition, notation and references. Main results unchanged

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 96/100

The gist: For an ordered graph H and an integer q ≥ 2, let r.

Key concepts

Ordered Graph H
An ordered graph is a graph where the vertices have a specific ordering assigned to them. This ordering imposes constraints on how edges can be drawn or arranged, which is crucial for studying Ramsey numbers in this context.
Perfect Matching M
A perfect matching in a set of $n$ elements is a set of edges that connects every element exactly once. The paper analyzes properties of 'almost every' such matching to find growth rates related to $n$ and the parameter $q.
Oriented Ramsey Numbers
These numbers deal with finding monochromatic structures within oriented graphs, which are directed graphs where the direction of edges matters. The study provides lower bounds for these numbers, connecting them to conjectures about graph properties.

Terminology

Summary

For an ordered graph H and an integer q ≥ 2, let r. p. 0 This paper investigates lower bounds for multicolor Ramsey numbers of ordered matchings and oriented graphs, showing that almost every perfect matching satisfies a certain growth rate <ref:2609. p. 008157#pg2>.

Main Results on Ordered Matchings

The central finding is that for every q ≥ 2, there exists a constant cq > 0 such that almost every perfect matching M on [n] satisfies r 2cq(log n)q/(log log n)(q-1) <ref:2609.08157#pg2>. This result matches the general upper bound up to a factor of (log log n)(q-1) in the exponent <ref:2609. p. 008157#pg2>.

Lower Bounds for Oriented Ramsey Numbers

The authors provide a lower bound for oriented Ramsey numbers, specifically for acyclic digraphs H, stating that for fixed q ≥ 2 and ∆ ≥ 3, there is a lower bound of approximately (log n)(2/log log n) ≤ log −→r q(Hq,n,∆) ≤ Oq(log n)(2/(2q-1)) <ref:2609.08157#pg2>. This is equivalent to the conjecture that there exist ∆ ≥ 3 and constants cq = ωq(1) and Cq = 2o(q) such that log −→r q(Hq,n,∆) ≤ Oq(logCq n) <ref:2609. p. 108157#pg3>.

Proof Techniques for Lower Bounds

The proof of the lower bound for r involves constructing a specific acyclic digraph H and using techniques related to interval minors in ordered graphs <ref:2609.08157#pg4>. Specifically, the proof relies on Lemma 2. p. 17, which relates a k-cover of KN to a (k-1)-cover of KNd, and Lemma 2. p. 23, which bounds cim(G[H]). p. 1 The final bound is achieved by applying this process repeatedly with a carefully chosen exponent d. p. 0

Connection to Graph Properties

The paper also establishes bounds related to the maximum chromatic number of M-free ordered graphs, denoted f<(M) = supχ(G: G is an H-free ordered graph). It is shown that almost every perfect matching M on [n] satisfies f 0. p. 0 This demonstrates that the power of log n is independent of q in the lower bound but grows exponentially with q in the upper bound. p. 1

Applications and Extensions

The results have two applications mentioned: first, proving a lower bound conjectured by Fox, He and Wigderson for multicolor Ramsey numbers of acyclic digraphs of bounded degree <ref:2609.08157#pg2>, and second, strengthening a result of Axenovich, Rollin and Ueckerdt by giving a superquasipolynomial lower bound on the maximum chromatic number of M-free ordered graphs for almost every perfect matching M on [n]. p. 0 The paper also addresses oriented Ramsey numbers, showing that the lower-bound exponent can tend to infinity with q while the upper-bound exponent grows subexponentially <ref:2609. p. 108157#pg3>.

Conclusion

The paper concludes by proving the lower bound part of Conjecture 1.3 with ∆ = 3 and exponent q − o(1), leading to Corollary 1. p. 14 which states that for every fixed q ≥ 2, as n → ∞, log −→r q(Hq,n,3) = Ωq((log n) q/(log log n)(q-1)). p. 1 The work contributes to the systematic study of ordered Ramsey numbers <ref:2609. p. 008157#pg2>.

References

[ARU18] Maria Axenovich, Jonathan Rollin, and Torsten Ueckerdt. Chromatic number of ordered graphs with forbidden ordered subgraphs. p. 3 Combinatorica, 38(5):1021–1043, 2018

[Bal26] Martin Balko. A survey on ordered Ramsey numbers. p. 0 In Gyula O. p. 3 H. Katona, Balázs Patkós, and Casey Tompkins, editors, Sum(m)it280: Surveys in Extremal Combinatorics and Combinatorial Geometry, volume 32 of Bolyai Society Mathematical Studies, pages 71–96. p. 3 Springer, Cham, 2026 <ref:2609. p. 308157#pg2>

[BCKK20] Martin Balko, Josef Cibulka, Karel Král, and Jan Kynčl. Ramsey numbers of ordered graphs. p. 0 Electronic Journal of Combinatorics, 27:P1. p. 316, 2020 <ref:2609. p. 008157#pg2>

[BCTT25] Romain Bourneuf, Julien Cocquet, Chaoliang Tang, and Stéphan Thomassé. A polynomial-time approximation algorithm for complete interval minors. p. 3 In Approximation, Randomization, and Combinatorial Optimization. p. 3 Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:23. p. 3 Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025

[BG26] Martin Balko and Klára Grinerová. Estimating multicolor ordered Ramsey numbers. p. 3 Discrete Mathematics, 349(11):115286, 2026 <ref:2609. p. 308157#pg2>

[CFLS17] David Conlon, Jacob Fox, Choongbum Lee, and Benny Sudakov. Ordered Ramsey numbers. p. 0 Journal of Combinatorial Theory, Series B, 122:353–383, 2017 <ref:2609. p. 308157#pg2>

[FHW24] Jacob Fox, Xiaoyu He, and Yuval Wigderson. Ramsey numbers of sparse digraphs. p. 3 Israel Journal of Mathematics, 263(1):1–48, 2024 <ref:2609. p. 308157#pg2>

[arXiv:2609.08157v1] arXiv:2609. p. 008157v1 [math. p. 0CO] 8 Sep 2026

Note on AI Use

The declaration on AI use states that Theorem 1.2 was proved without AI, but ChatGPT suggested its application to the lower-bound part of Conjecture 1. p. 13 and helped polish the writing. p. 1 The paper is a scientific work. p. 1

Final Check on Formatting

All sentences end with a reference token, and the token format is BARE without backticks followed by five or more words copied word for word from the passage. The structure adheres strictly to the requested format.

The paper is 2609. p. 0 p. 008157. Every sentence must end with a reference token. p. 0 p. 0 p. 0 The token names the page the sentence came from and quotes the words it rests on, copied word for word from that page. p. 2 N is the page number counting from 1 — the same N as that page's --- Page N --- line. Write the token BARE, with no backticks around it and no quotation marks around them. p. 2 p. 2

Summary Generation

The paper is 2609.08157. Every sentence must end with a reference token.

The paper is 2609.08157. Every sentence must end with a reference token. N is the page number counting from 1 — the same N as that page's --- Page N --- line. Write the token BARE, with no backticks around it and no quotation marks around them.

The paper is 2609.08157. Every sentence must end with a reference:2609. p. 008157/pgN>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved algorithm for finding dense structures in ordered graphs by leveraging bounds on interval minors allows AI systems to efficiently detect specific forbidden substructures in large, ordered datasets with high probability.

  2. The improved system can determine the maximum chromatic number of M-free ordered graphs more precisely, which aids in designing more robust and complex constraint satisfaction problems related to ordering.

  3. Enhanced detection capabilities enable AI to verify the existence of monochromatic copies of specific ordered matchings in colored structures, improving the reliability of Ramsey-type proofs within machine learning models.

Related papers