More non-bipartite forcing pairs

Abstract

We study pairs of graphs $(H_1,H_2)$ such that every graph with the densities of $H_1$ and $H_2$ close to the densities of $H_1$ and $H_2$ in a random graph is quasirandom; such pairs $(H_1,H_2)$ are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, H\`an, Person and Schacht~[{\em Weak quasi-randomness for uniform hypergraphs}, Random Structures Algorithms \textbf{40} (2012), no.~1, 1--38]: they showed that $(K_t, F)$ is forcing where $F$ is the graph that arises from $K_t$ by iteratively doubling its vertices and edges in a prescribed way $t$ times. Reiher and Schacht~[{\em Forcing quasirandomness with triangles}, Forum of Mathematics, Sigma. Vol. 7, 2019] strengthened this result for $t=3$ by proving that two doublings suffice and asked for the minimum number of doublings needed for $t>3$. We show that $\lceil(t+1)/2\rceil$ doublings always suffice.