Jae-baek Lee

Topic

The Ramsey Multiplicity Problem

Department of Mathematics and Statistics

Date & location

• Thursday, August 21, 2025
• 9:00 A.M.
• Clearihue Building, Room B019

Examining Committee

Supervisory Committee

• Dr. Jonathan Noel, Department of Mathematics and Statistics, University of Victoria (Co-Supervisor)
• Dr. Gary MacGillivray, Department of Mathematics and Statistics, UVic (Co-Supervisor)
• Dr. Sajin Koroth, Department of Computer Science, UVic (Outside Member)

External Examiner

• Dr. Rachel Kirsch, Department of Mathematical Sciences, George Mason University

Chair of Oral Examination

• Prof. Martin Segger, Department of Art History and Visual Studies, UVic

Abstract

“Complete chaos is impossible” is a core concept of Ramsey theory. Ramsey’s Theorem formalizes this idea by showing that any sufficiently large graph, no matter how disordered, must inevitably contain a certain type of pattern. The Ramsey multiplicity problem extends this concept quantitatively: instead of asking whether a fixed pattern exists, it asks how many copies of a fixed pattern are guaranteed as the size of the graph increases. Combinatorial limit theory, one of the most significant developments in modern combinatorics, helps to understand these large discrete structures. It also provides a framework for viewing discrete structures as approximations of rich continuous objects, like measurable functions or measures, which facilitates the use of analytic tools to tackle the problems in extremal combinatorics including the Ramsey multiplicity problem. By solving such a problem, we want to deepen our understanding of large and seemingly chaotic graphs.

A graph 𝐻 is said to be common if the number of monochromatic copies of 𝐻 is asymptotically minimized by a random colouring. It is well known that the disjoint union of two common graphs may be uncommon; e.g., 𝐾₂ and 𝐾₃ are common, but their disjoint union is not.

In Chapter 3, we investigate the commonality of disjoint unions of multiple copies of 𝐾₃ and 𝐾₂. As a consequence of our results, we obtain the first example of a pair of uncommon graphs whose disjoint union is common. Our approach is to reduce the problem of showing that certain disconnected graphs are common to a constrained optimization problem in which the constraints are derived from supersaturation bounds related to Razborov’s Triangle Density Theorem. We also improve the bounds on the Ramsey multiplicity constant of a triangle with a pendant edge and the disjoint union of 𝐾₃ and 𝐾₂.

Fox and Wigderson recently identified a large family of graphs whose Ramsey multiplicity constants are attained by sequences of “Turán colourings;” i.e. colourings in which one of the colour classes forms the edge set of a balanced complete multipartite graph. Each graph in their family comes from taking a connected non-3-colourable graph with a critical edge and adding many pendant edges. In Chapter 4, We extend their result to an off-diagonal variant of the Ramsey multiplicity constant which involves minimizing a weighted sum of red copies of one graph and blue copies of another.

In Chapter 5, we focus on finding smaller graphs whose Ramsey multiplicity constants are achieved by Turán colourings. While Fox and Wigderson provide many examples, their smallest constructions involve graphs with at least 10⁶⁶ vertices. In contrast, we identify a graph on only 10 vertices whose Ramsey multiplicity constant is achieved by Turán colourings. To prove this, we apply the method developed in Chapter 3 and used a powerful technique known as the flag algebra method, assisted by semi-definite programming.