On \(K^ 4\)-free subgraphs of random graphs (Q1385983): Difference between revisions

For \(0<\gamma\leq 1\) and graphs \(G\) and \(H\), write \(G\rightarrow_\gamma H\) if a \(\gamma\)-proportion of the edges of \(G\) spans at least one copy of \(H\) in \(G\). Let \(K^r\) be the complete graph on \(r\) vertices, and \(G_{n,p}\) be the (binomial) random graph on \(n\) vertices. The main result of this paper says that for every fixed real \(0<\eta\leq 1/3\), there is a constant \(C(\eta )\) for which the following holds. If \(0\leq p=p(n)\leq 1\) is such that \(p\geq Cn^{-2/5}\) for all large enough \(n\), then almost every \(G_{n,p}\) is such that \(G_{n,p}\rightarrow_{2/3+\eta} K_4\). This result is obtained by a sequence of lemmata which are interesting on their own. For instance, nice results on the distribution of triangles in random and pesudo-random graphs are obtained. The proof combines probabilistic arguments with a Turán type result and a version of Szemerédi's regularity lemma for sparse graphs. The paper contains a challenging conjecture, too.