Common Pairs of Graphs

arXiv2208.02045MaRDI QIDQ6406853FDOQ6406853

Authors: Natalie C. Behague, Natasha Morrison, Jonathan A. Noel 

Publication date: 3 August 2022

Abstract: A graph $H$ is said to be common if the number of monochromatic labelled copies of $H$ in a red/blue edge colouring of a large complete graph is asymptotically minimized by a random colouring with an equal proportion of each colour. We extend this notion to an asymmetric setting. That is, we define a pair $(H_1,H_2)$ of graphs to be $(p,1-p)$-common if a particular linear combination of the density of $H_1$ in red and $H_2$ in blue is asymptotically minimized by a random colouring in which each edge is coloured red with probability $p$ and blue with probability $1-p$. We extend many of the results on common graphs to this asymmetric setting. In addition, we obtain several novel results for common pairs of graphs with no natural analogue in the symmetric setting. We also obtain new examples of common graphs in the classical sense and propose several open problems.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Ramsey theory (05D10)

This page was built for publication: Common Pairs of Graphs

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