Spring 2017

Forcing Quasirandomness with Triangles

Tuesday, March 7th, 2017 11:00 am12:00 pm

Add to Calendar


Calvin Lab Auditorium

We study \emph{forcing pairs} for \emph{quasirandom graphs}. Chung, Graham, and Wilson initiated the study of families~$\cF$ of graphs with the property that if a large graph~$G$ has approximately homomorphism density $p^{e(F)}$ for some fixed $p\in(0,1]$ for every $F\in \cF$, then $G$ is quasirandom with density~$p$. Such families $\cF$ are said to be \emph{forcing}. Several forcing families were found over the last three decades and characterising all bipartite graphs $F$ such that $(K_2,F)$ is a forcing pair is a well known open problem in the area of quasirandom graphs, which is closely related to Sidorenko's conjecture. In fact, most of 
the known forcing families involve bipartite graphs only.
We consider forcing pairs containing the triangle~$K_3$. In particular, we show that if~$(K_2,F)$ is a forcing pair, then so ist $(K_3,F^\Delta)$, where $F^\Delta$ is obtained from~$F$ by replacing every edge of $F$ by a triangle (each of which introducing a new vertex). For the proof we first show that $(K_3,C_4^\triag)$ is a forcing pair, which strengthens related results of Simonovits and S\'os and of Conlon et al.