5
$\begingroup$

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<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?

$\endgroup$
1
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is very nice! $\endgroup$ – Iosif Pinelis Mar 5 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.