On tripartite common graphs

Abstract: A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_N$ is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdős, conjectured that every graph is common, which was disproved by Thomason and by Sidorenko in late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture.

Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle trees, which generalises two theorems by Sidorenko and hence answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle tree such that the graph obtained by adding $T$ as a pendant tree is still common. Furthermore, we show that some complete tripartite graphs, e.g., the octahedron graph $K_{2,2,2}$, are common and conjecture that every complete tripartite graph is common.

Joint work with Andrzej Grzesik, Bernard Lidický, and Jan Volec.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).