Non-Bipartite K-Common Graphs

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KRÁĽ Daniel NOEL Jonathan A NORIN Sergey VOLEC Jan WEI Fan

Year of publication 2022
Type Article in Periodical
Magazine / Source COMBINATORICA
MU Faculty or unit

Faculty of Informatics

Citation
Web http://doi.org/10.1007/s00493-020-4499-9
Doi http://dx.doi.org/10.1007/s00493-020-4499-9
Keywords common graphs; extremal combinatorics; Sidorenko's conjecture
Description A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štovíček and Thomason [20]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.