Off-Diagonal Commonality of Graphs via Entropy

Abstract: A graph

H

is common if the limit as

n o i n f t y

of the minimum density of monochromatic labelled copies of

H

in an edge colouring of

K_{n}

with red and blue is attained by a sequence of quasirandom colourings. 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 i n (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 colouring in which

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.

This page was built for publication: Off-Diagonal Commonality of Graphs via Entropy

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