Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Odprti dostop
  • Jae-baek, Lee; Noel, Jonathan A

    arXiv.org, 08/2023
    Paper, Journal Article

    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., \(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 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 \(K_3\) and \(K_2\).