The Ramsey Multiplicity Problem

Title : The Ramsey Multiplicity Problem
Abstract : A graph $H$ is said to be common if the number of monochromatic copies of $H$ is asymptotically minimized by a random colouring. It is well known that the disjoint union of two common graphs may be uncommon; e.g., $K_2$ and $K_3$ are common, but their disjoint union is not. We investigate the commonality of disjoint unions of multiple copies of $K_3$ and $K_2$. 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 $K_3$ and $K_2$. 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. 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^{66}$ 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 earlier and use a powerful technique known as the flag algebra method, assisted by semi-definite programming.