[Turán's theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_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:


0. 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$.
1. 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.
2. 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.
3. 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<c<1$ 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?
> 
> 
> 



Randomized version of Turán's theorem
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.


