2023/03/16 by Lee, Jae-baek, Noel, Jonathan A.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2303.09296
A graph H is said to be common if the number of monochromatic labelled copies of H in a 2-colouring of the edges of a large complete graph is asymptotically minimized by a random colouring. It is well known that the disjoint union of two common graphs may be uncommon; e.g., K2 and K3 are common, but their disjoint union is not. We investigate the commonality of disjoint unions of multiple copies of K3 and K2. As a consequence of our results, we obtain an 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 bounds on the Ramsey multiplicity constant of a triangle with a pendant edge and the disjoint union of K3 and K2.