Randomized version of Turán's theorem

Question

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:

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?

Answer 1

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.