Non-Bipartite K-Common Graphs

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

Rok publikování 2022
Druh Článek v odborném periodiku
Časopis / Zdroj COMBINATORICA
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://doi.org/10.1007/s00493-020-4499-9
Doi http://dx.doi.org/10.1007/s00493-020-4499-9
Klíčová slova common graphs; extremal combinatorics; Sidorenko's conjecture
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.