Off-Diagonal Commonality of Graphs via Entropy

. A graph \ (H\) is common if the limit as \ (n \) of the minimum density of monochromatic labeled copies of \ (H\) in an edge coloring of \ (Kₙ\) with red and blue is attained by a sequence of quasirandom colorings. We apply an information-theoretic approach to show that certain graphs obtained from odd cycles and paths via gluing operations are common. In fact, for every pair \ ( (H₁, H₂) \) of such graphs, there exists \ (p (0, 1) \) such that an appropriate linear combination of red copies of \ (H₁\) and blue copies of \ (H₂\) is minimized by a quasirandom coloring in which \ (pn2\) edges are red; such a pair \ ( (H₁, H₂) \) is said to be \ ( (p, 1-p) \) -common. Our approach exploits a strengthening of the common graph property for odd cycles that was recently proved using Schur convexity. We also exhibit a \ ( (p, 1-p) \) -common pair \ ( (H₁, H₂) \) such that \ (H₂\) is uncommon. KeywordscommongraphhomomorphismSidorenkooff-diagonalRamseyMSC codes05C5505C35