Off-diagonaL
Ramsey Multiplicity
Jonathan Noel
University of Victoria
Joint work with
Natalie Behague (x2), Joseph Hyde (x2),
Jae-baek Lee (x3), Natasha Morrison (x2)
and Elena Moss
Ramsey Theory
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Strategy 1: Colour “Randomly”
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Strategy 1: Colour “Randomly”
Erdős, 1947, r(t,t) is exponential
Erdős, 1947, r(t,t) is exponential
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Strategy 1: Colour “Randomly”
Erdős, 1947, r(t,t) is exponential
Erdős, 1947, r(t,t) is exponential
Kim, 1995,
Kim, 1995,
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Strategy 1: Colour “Randomly”
Both results have been improved but the strategy is still “random”
Both results have been improved but the strategy is still “random”
Erdős, 1947, r(t,t) is exponential
Erdős, 1947, r(t,t) is exponential
Kim, 1995,
Kim, 1995,
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Strategy 1: Colour “Randomly”
Both results have been improved but the strategy is still “random”
Both results have been improved but the strategy is still “random”
Erdős, 1947, r(t,t) is exponential
Erdős, 1947, r(t,t) is exponential
Kim, 1995,
Kim, 1995,
Strategy 2: “Structured” Colouring
Turán graphs (Ramsey Goodness)
Turán graphs (Ramsey Goodness)
Geometric/algebraic constructions
Geometric/algebraic constructions
Strongly regular graphs
Strongly regular graphs
Ramsey Theory
Q: Let F and H be graphs. What is the minimum N such that every red/blue colouring of the edges of a clique on N vertices with red and blue contains a red copy of F or a blue copy of H? Denoted r(F,H) or r(s,t) for cliques.
Strategy 1: Colour “Randomly”
Both results have been improved but the strategy is still “random”
Both results have been improved but the strategy is still “random”
Erdős, 1947, r(t,t) is exponential
Erdős, 1947, r(t,t) is exponential
Kim, 1995,
Kim, 1995,
Strategy 2: “Structured” Colouring
Turán graphs (Ramsey Goodness)
Turán graphs (Ramsey Goodness)
Geometric/algebraic constructions
Geometric/algebraic constructions
Strongly regular graphs
Strongly regular graphs
Strategy 3: A mixture of both!
Mattheus and Verstraëte, 2023+, r(4,t)
Mattheus and Verstraëte, 2023+, r(4,t)
Ramsey Multiplicity
Ramsey Multiplicity
Q: Suppose n is very large (tending to infinity). What is the minimum number of monochromatic copies of H in a red/blue colouring of the edges of ?
Ramsey Multiplicity
Q: Suppose n is very large (tending to infinity). What is the minimum number of monochromatic copies of H in a red/blue colouring of the edges of ?
Example: H is a triangle
Ramsey Multiplicity
Q: Suppose n is very large (tending to infinity). What is the minimum number of monochromatic copies of H in a red/blue colouring of the edges of ?
Example: H is a triangle
Goodman’s Theorem (1959): Every red/blue colouring contains at least
labelled monochromatic triangles.
Ramsey Multiplicity
Q: Suppose n is very large (tending to infinity). What is the minimum number of monochromatic copies of H in a red/blue colouring of the edges of ?
Example: H is a triangle
Goodman’s Theorem (1959): Every red/blue colouring contains at least
labelled monochromatic triangles.
This is asymptotically tight by colouring randomly!
Turán (complete bipartite) colourings are also tight!
Optimality of Random Colourings
Optimality of Random Colourings
A graph H is said to be common if the number of labelled monochromatic copies of H is asymptotically minimized by a random colouring.
Optimality of Random Colourings
A graph H is said to be common if the number of labelled monochromatic copies of H is asymptotically minimized by a random colouring.
Common graphs are very mysterious...
Optimality of Random Colourings
A graph H is said to be common if the number of labelled monochromatic copies of H is asymptotically minimized by a random colouring.
Common graphs are very mysterious...
common
Goodman ‘59
common
trivial
Sidorenko ‘89
uncommon
common
Lee, N, 2023+
Triangle-trees
A generalization
common
Grzesik, Lee, Lidický Volec, ‘22
Behague, Morrison, N, 2023+
Thomason ‘89
uncommon
common
Hatami, Hladký, Král, Norine, Razborov, ‘12
Exists common graphs of any chromatic number
common
Král, Volec and Wei, 2022+
Any graph containing
uncommon
Jagger, Šťovíček
Thomason ‘96
Non-bipartite graph with many pendants
uncommon
Jagger, Šťovíček
Thomason ‘96
How about Structured Colourings?
How about Structured Colourings?
Fox and Wigderson (2023): If H has chromatic number at least 4 and has a critical edge, then the Ramsey multiplicity of any graph obtained from H by adding MANY pendants is attained by a Turán colouring.
How about Structured Colourings?
Fox and Wigderson (2023): If H has chromatic number at least 4 and has a critical edge, then the Ramsey multiplicity of any graph obtained from H by adding MANY pendants is attained by a Turán colouring.
How about Structured Colourings?
Fox and Wigderson (2023): If H has chromatic number at least 4 and has a critical edge, then the Ramsey multiplicity of any graph obtained from H by adding MANY pendants is attained by a Turán colouring.
How about Structured Colourings?
Fox and Wigderson (2023): If H has chromatic number at least 4 and has a critical edge, then the Ramsey multiplicity of any graph obtained from H by adding MANY pendants is attained by a Turán colouring.
They call graphs minimized by Turán colourings bonbons
How about Structured Colourings?
Fox and Wigderson (2023): If H has chromatic number at least 4 and has a critical edge, then the Ramsey multiplicity of any graph obtained from H by adding MANY pendants is attained by a Turán colouring.
They call graphs minimized by Turán colourings bonbons
There are no examples in which the Ramsey multiplicity has been computed which are not common or bonbons
An Off-Diagonal Generalization?
An Off-Diagonal Generalization?
For a red/blue colouring of the edges of the complete graph, let
red(H) =
blue(H) =
An Off-Diagonal Generalization?
For a red/blue colouring of the edges of the complete graph, let
red(H) =
blue(H) =
Basic question: Given two graphs H, F and reals A, B, what is the minimum of
A• red(F) + B• blue(H)
in a red/blue colouring of the edges of the complete graph as n tends to ∞?
A Nice result for cliques
A Nice result for cliques
Parczyk, Pokutta, Spiegel, Szabó (2022+): For every colouring,
red(K3) + blue(K4) ≥
3
4
A Nice result for cliques
Parczyk, Pokutta, Spiegel, Szabó (2022+): For every colouring,
red(K3) + blue(K4) ≥
3
4
Tight construction: Red edges form a blow-up of the Schläfli graph, which is a srg(27, 16, 10, 8)
Picture credit: Wikipedia
A Nice result for cliques
Parczyk, Pokutta, Spiegel, Szabó (2022+): For every colouring,
red(K3) + blue(K4) ≥
3
4
Tight construction: Red edges form a blow-up of the Schläfli graph, which is a srg(27, 16, 10, 8)
Similar result for
red(K3) + blue(K4)
3
5
but the blue edges are a blowup of the complement
of the Schläfli graph
Picture credit: Wikipedia
What about Random Colourings?
What about Random Colourings?
Defn (Behague, Morrison, N, 23+): A pair (F,H) is (p, 1-p)-common if
red(F) + blue(H)
is minimized by a random colouring in which the density of red edges is p.
What about Random Colourings?
Defn (Behague, Morrison, N, 23+): A pair (F,H) is (p, 1-p)-common if
red(F) + blue(H)
is minimized by a random colouring in which the density of red edges is p.
If (F,H) is (p, 1-p)-common, then both F and H are K -free.
4
What about Random Colourings?
Defn (Behague, Morrison, N, 23+): A pair (F,H) is (p, 1-p)-common if
red(F) + blue(H)
is minimized by a random colouring in which the density of red edges is p.
If (F,H) is (p, 1-p)-common, then both F and H are K -free.
4
If F has odd girth, then H must have the same girth or a shorter even girth.
What about Random Colourings?
Defn (Behague, Morrison, N, 23+): A pair (F,H) is (p, 1-p)-common if
red(F) + blue(H)
is minimized by a random colouring in which the density of red edges is p.
If (F,H) is (p, 1-p)-common, then both F and H are K -free.
4
If F has odd girth, then H must have the same girth or a shorter even girth.
4
5
(C , C ) is (1/2, 1/2)-common and (1/3, 2/3)-common but not for p>0.518
What about Random Colourings?
Defn (Behague, Morrison, N, 23+): A pair (F,H) is (p, 1-p)-common if
red(F) + blue(H)
is minimized by a random colouring in which the density of red edges is p.
If (F,H) is (p, 1-p)-common, then both F and H are K -free.
4
If F has odd girth, then H must have the same girth or a shorter even girth.
4
5
(C , C ) is (1/2, 1/2)-common and (1/3, 2/3)-common but not for p>0.518
There exists a (p, 1-p) common pair (F,H) such that F is uncommon,
What about Random Colourings?
Defn (Behague, Morrison, N, 23+): A pair (F,H) is (p, 1-p)-common if
red(F) + blue(H)
is minimized by a random colouring in which the density of red edges is p.
If (F,H) is (p, 1-p)-common, then both F and H are K -free.
4
If F has odd girth, then H must have the same girth or a shorter even girth.
4
5
(C , C ) is (1/2, 1/2)-common and (1/3, 2/3)-common but not for p>0.518
There exists a (p, 1-p) common pair (F,H) such that F is uncommon,
12 open
problems!
(2 papers)
Turán Colourings?
Turán Colourings?
Hyde, Lee, N., 23+: Extend Fox and Wigderson’s bonbon result to an off-diagonal version.
One graph can have chromatic number 3. There’s a technical condition on the number of pendants added to the two graphs.
Turán Colourings?
Hyde, Lee, N., 23+: Extend Fox and Wigderson’s bonbon result to an off-diagonal version.
One graph can have chromatic number 3. There’s a technical condition on the number of pendants added to the two graphs.
4 open
problems!
Open problem: Does there exist a bonbon of minimum degree at least 2?
Other Structured Colourings
Other Structured Colourings
Moss and N, 23+: The balanced Ramsey multiplicity of (F,H) is the max over all lambda λ of the minimum of
λ•red(F) + (2-λ)•blue(H)
Other Structured Colourings
Moss and N, 23+: The balanced Ramsey multiplicity of (F,H) is the max over all lambda λ of the minimum of
λ•red(F) + (2-λ)•blue(H)
We compute it in a few cases.
Other Structured Colourings
Moss and N, 23+: The balanced Ramsey multiplicity of (F,H) is the max over all lambda λ of the minimum of
λ•red(F) + (2-λ)•blue(H)
We compute it in a few cases.
Several of these results involve “structured” colourings coming from blowups of small graphs and graphs obtained from graph products.
Other Structured Colourings
Moss and N, 23+: The balanced Ramsey multiplicity of (F,H) is the max over all lambda λ of the minimum of
λ•red(F) + (2-λ)•blue(H)
We compute it in a few cases.
Several of these results involve “structured” colourings coming from blowups of small graphs and graphs obtained from graph products.
4 open
problems!
Thanks!
