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_n\) 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_1,H_2)\) of such graphs, there exists \(p∈ (0,1)\) such that an appropriate linear combination of red copies of \(H_1\) and blue copies of \(H_2\) is minimized by a quasirandom coloring in which \(p{n}{2}\) edges are red; such a pair \((H_1,H_2)\) 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_1,H_2)\) such that \(H_2\) is uncommon.KeywordscommongraphhomomorphismSidorenkooff-diagonalRamseyMSC codes05C5505C35