Constructing non-bipartite $k$-common graphs

Graph Theory Seminar
Tuesday, May 4, 2021 - 3:45pm for 1 hour (actually 50 minutes)
Location For password, please email Anton Bernshteyn (bahtoh ~at~
Fan Wei – Princeton University – fanw@princeton.edu
Anton Bernshteyn

A graph $H$ is $k$-common if the number of monochromatic copies of $H$ in a $k$-edge-coloring of $K_n$ 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, Stovicek and Thomason. 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.