Multicolor Ramsey numbers of ordered matchings

summary

The gist

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

In short

The research investigates lower bounds for multicolor Ramsey numbers concerning ordered matchings and oriented graphs. It proves that almost every perfect matching has a specific growth rate, while simultaneously establishing lower bounds for oriented Ramsey numbers related to acyclic digraphs. These findings advance conjectures regarding the complexity of finding monochromatic structures in ordered graphs.

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 used across episodes

This episode discusses

The paper

Multicolor Ramsey numbers of ordered matchings · Read on arXiv

Xiangyu Li

University of Toronto

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>.

More episodes

← Home