# Randomized version of Turán's theorem

Turán's theorem says the following.

Take any natural $$n$$ and $$r$$. Suppose that $$\begin{equation*} |G|>\Big(1-\frac1r\Big)\frac{n^2}2, \tag{0} \end{equation*}$$ where $$|G|$$ is the number of edges of an (undirected) graph $$G$$ with $$n$$ vertices. Then $$G$$ contains an $$(r+1)$$-vertex clique.

The bound on $$|G|$$ in (0) is the best possible one. The extreme graphs not containing an $$(r+1)$$-vertex clique, called Turán's graphs, are complete $$r$$-partite graphs with maximally balanced numbers of vertices in the $$r$$ parts.

Taking here, e.g., $$r=2$$, we see that Turán's theorem requires that more than half of all $$\binom n2$$ possible edges between the $$n$$ vertices be included into $$G$$ in order to guarantee, even in a worst possible case, the existence of a triangle in $$G$$.

Suppose, though, that we are interested, not in a worst possible case, but in a case typical to a however degree.

To be more specific, suppose $$G$$ is a random graph with the set $$[n]:=\{1,\dots,n\}$$ of vertices. For any $$i$$ and $$j$$ in $$[n]$$, let $$G_{\{i,j\}}$$ denote the indicator of the inclusion of the edge $$\{i,j\}$$ into $$G$$, with $$G_{\{i,i\}}=0$$ for all $$i\in[n]$$, so that $$|G|=\sum_{\{i,j\}\subseteq[n]}G_{\{i,j\}}$$.

Further, assume the following conditions:

1. For each pair of distinct $$i$$ and $$j$$ in $$[n]$$, the r.v. $$G_{\{i,j\}}$$ has the same Bernoulli distribution with parameter $$1-p$$.

2. For each $$J\subseteq[n]$$, the families $$(G_{\{i,j\}}\colon\{i,j\}\subseteq J)$$ and $$(G_{\{k,l\}}\colon\{k,l\}\subseteq[n]\setminus J)$$ are independent of each other.

3. For each $$i\in[n]$$, the random variables (r.v.'s) $$G_{\{i,1\}},\dots,G_{\{i,i-1\}},G_{\{i,i+1\}},\dots,G_{\{i,n\}}$$ are independent.

4. The distribution of $$G$$ is invariant with respect to all permutations of $$[n]$$.

(No conditions other than 0--3 are assumed here. In particular, it is not necessary that all the indicators $$G_{\{i,j\}}$$ be jointly independent.)

Then, by condition 0,
$$\begin{equation*} E|G|=\binom n2(1-p). \end{equation*}$$ So, with a nonzero probability
$$\begin{equation*} |G|\ge\binom n2(1-p)\ge\Big(1-\frac1{cn}\Big)\frac{n^2}2 \end{equation*}$$ if $$0 and $$\begin{equation*} p\le\Big(\frac1c-1\Big)\frac1{n-1} \tag{1} \end{equation*}$$ and hence, by Turán's theorem, there is a clique in $$G$$ of a size $$\ge cn$$.

However, the above derivation of (1) does not use conditions 1--3 on the random graph $$G$$. This derivation is based on Turán's theorem, which deals with the worst possible case, and the "worst possible" Turán graphs seem to be very different from a typical realization of a random graph $$G$$ satisfying conditions 0--3. Therefore, condition (1) appears to be too restrictive, as far as the existence of a clique of a size $$\asymp n$$ in the random graph $$G$$ is concerned.

Can we relax (1), say to $$\begin{equation*} p\le b\frac{\ln n}n \tag{2} \end{equation*}$$ for some small enough real $$b>0$$ (and still have, with a nonzero probability, a clique of a size $$\asymp n$$ in $$G$$)?

To put this more formally:

Is it true that there exist universal real constants $$b>0$$ and $$c\in(0,1)$$ such that -- for each natural $$n$$, each $$p\in[0,b\frac{\ln n}n]$$, and each random graph $$G$$ with the set $$[n]$$ of vertices satisfying conditions 0--3 -- the probability that $$G$$ has a clique of a size $$\ge cn$$ is nonzero?

No. Consider the following distribution: Let $$M$$ be an integer, say $$M= \frac{n}{\log n}$$. Then for each vertex $$v \in [n]$$ assign an integer $$m(v)$$ where $$m(v)$$ is chosen according to the uniform distribution on $$\{0,1,\ldots, M-1\}$$, and where the $$m(v)$$s; $$v \in [n]$$; are mutually independent. Then for each pair $$u$$,$$v \in [n]$$ of vertices, $$uv$$ is an edge if and only if $$m(v)\not = m(u)$$.
Then this distribution satisfies (0)--(3) of your conditions, and furthermore the probability that 2 vertices form an edge is $$\frac{M-1}{M} = 1 -\theta(\frac{\log n}{n})$$, but there is necessarily no clique with more than $$M$$ vertices.