Disconnected Common Graphs via Supersaturation

arXiv2303.09296MaRDI QIDQ6429795FDOQ6429795

Publication date: 16 March 2023

Abstract: 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 find the first examples of a pair of uncommon graphs whose disjoint union is common and a common graph and an uncommon graph 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}

.

This page was built for publication: Disconnected Common Graphs via Supersaturation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429795)