Non-Bipartite K-Common Graphs
| Authors | |
|---|---|
| Year of publication | 2022 |
| Type | Article in Periodical |
| Magazine / Source | COMBINATORICA |
| MU Faculty or unit | |
| 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: |