$\newcommand{\om}{\omega}$Let $\om(G)$ denote the number of vertices in a largest clique of an (undirected) graph $G$ with the set $[n]:=\{1,\dots,n\}$ of vertices. Then
\begin{equation}
 \om(G)\ge\sum\_{i\in[n]}\frac1{n-d\_i},\tag{1}
\end{equation}
where $d\_i$ is the degree of vertex $i$ in $G$. Inequality (1) is the main ingredient in the fourth proof of Turán's theorem in [Proofs from THE BOOK, Fifth Edition, p. 271](https://www.springer.com/gp/book/9783662495926), where the inequality is ascribed to [Alon and Spenser: The Probabilistic Method](https://www.wiley.com/en-us/The+Probabilistic+Method%2C+4th+Edition-p-9781119061953), who in turn ascribe this inequality to Caro and Wei.


[Turán's theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem) actually says the following.



> 
> Take any natural $n$ and $r$. Suppose that
> \begin{equation\*}
> |G|>\Big(1-\frac1r\Big)\frac{n^2}2, \tag{\*}
> \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 (\*) 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.


Suppose now that $G$ is a random graph with the set $[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
$d\_i=\sum\_{j\in[n]}G\_{\{i,j\}}$. Suppose also that



> 
> 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$.
> 
> 
> 


Then $Ed\_i=(n-1)(1-p)$ and hence, by (1) and Jensen's inequality,
\begin{equation}
 E\om(G)\ge\sum\_{i\in[n]}E\frac1{n-d\_i}\ge\sum\_{i\in[n]}\frac1{n-Ed\_i} \\ 
 =\frac n{n-(n-1)(1-p)}=\frac n{1+(n-1)p}\sim\frac1p \\ 
 \text{if}\quad np\to\infty.\tag{2}
\end{equation}


So, with nonzero probability
\begin{equation}
 \om(G)\ge\frac{1+o(1)}p\quad\text{if}\quad np\to\infty.\tag{2}
\end{equation}


Inequality (1), even with its probabilistic proof, appears to be just enough to prove Turán's theorem, which deals with the worst possible cases for $G$ in regard to a largest clique 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]$ of vertices, satisfying condition 0 above as well as the following conditions:



> 
> 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]$.
> 
> 
> 


The above derivation of (2) does not use conditions 1--3 on the random graph $G$. This derivation
is based on inequality (1) -- which, even with its probabilistic proof, appears to be just enough to prove Turán's theorem, which deals with the worst possible cases for $G$ in regard to a largest clique in $G$, 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, the lower bound on $\om(G)$ in (2) appears to be too weak.



> 
> Can we improve (2) as follows:
> \begin{equation}
>  P\Big(\om(G)\ge\frac cp\,\ln\frac1p\Big)>0
> \end{equation}
> for some universal real constant $c>0$ and all large enough $n$ (depending on $p\in(0,1)$)?
> 
> 
> 



Randomized version of Turán's theorem II
For completeness, I'll repeat here the construction as the other thread. Let $M$ be an integer say $M=\frac{1}{p}$. Then for each $v \in [n]$, let $m(v)$ be an integer chosen uniformly from $\{0,1,\ldots, M-1\}$, and then $u$ and $v$ form an edge iff $m(u)\not = m(v)$.


Then all of 0.--3. as above are satisfied, and $u$ and $v$ form an edge with probability $\frac{M-1}{M} = 1-p$, and $\omega(G) \le M = \frac{1}{p}$. So no, Inequality (2) cannot be significantly improved and is actually quite tight.


