Natalie Behague

Common pairs of graphs

Ramsey's theorem tells us that for any fixed graph H, there is a monochromatic copy of H in any red/blue edge colouring of a sufficiently large complete graph. The closely related Ramsey multiplicity problem asks instead what is the minimum number of monochromatic copies of H over all red/blue edge colourings? A beautiful result of Goodman shows that the number of monochromatic copies of the triangle is asymptotically minimised by an unbiased random edge colouring. A graph H is called common if it has this property, that an unbiased random edge colouring gives the asymptotic minimum, and the question of which graphs (other than the triangle) are common has been well studied. I will discuss this history and introduce a natural extension of this notion to an asymmetric setting, where we wish to minimize some linear combination of the number of red copies of H_1 and blue copies of H_2. I will discuss some of our new results in the asymmetric setting and finish with several open questions. This is joint work with Natasha Morrison and Jonathan Noel.