Non-Bipartite K-Common Graphs
| Autoři | |
|---|---|
| Rok publikování | 2022 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | COMBINATORICA |
| Fakulta / Pracoviště MU | |
| 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: |