Randomized version of Turán's theorem II

Question

$\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, where the inequality is ascribed to Alon and Spenser: The Probabilistic Method, who in turn ascribe this inequality to Caro and Wei.

Turán's 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)$)?

Answer 1

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.