Turan $K_4$-free problem of graphs with small independence number.

Question

I’m asked to use the following lemma to prove that, if $G$ is an $n$-vertex $K_4$-free graph with independence number at most $n^{0.99}$, then $G$ has $O\left( \frac{n^2}{\text{log}n} \right)$ edges.

DRC-Lemma. Let $n, m, r, t \in \mathbb{N}_{+}$ and $\alpha>0$. Then every graph $G$ with $v(G)=n$ vertices and average degree $\overline{d}(G) \geq \alpha n$ contains a subset $U \subseteq V(G)$ of size $$ |U| \geq \alpha^{t} n-\left(\begin{array}{l} n \\ r \end{array}\right)\left(\frac{m}{n}\right)^{t} $$ such that every $r$-subset of $U$ has more than $m$ common neighbors in $G$.

Suppose that $G$ is a graph with independence number at most $n^{0.99}$ and $\frac{cn^2}{\text{log}n}$ edges, where $c$ is a constant to be chosen later, then we want to show that $G$ contains a $K_4$.

I think one way to go about this problem, keeping the lemma in mind, is to find a set $U$ such that any $2$ vertices in $U$ have at least $n^{0.99} + 1$ common neighbors. If this holds, and if some two vertices in $U$ are adjacent, then $G$ would contain a $K_4$.

Note that with this line of argument, we’ve already chosen $r = 2$ and $m = n^{0.99} + 1$.

A few difficulties in choosing the appropriate parameters are as follows:

1. I need to make sure there would be an adjacent pair of vertices in $U$. One way is to choose the remaining parameters so that $|U| \geq n^{0.99} + 1$, but this seems rather excessive.

2. The setup above assumes that $m$ depends on $n$. I’m not sure this is ok?

3. What about $c$? Can I let $c$ be a function of $n$, but of order smaller than $\frac{n^2}{\text{log}n}$ (say, $c = k(n^{0.99} + 1)$ for some constant $k$), so that the upper bound on the number of edges is not violated?

If all the above go through, then I’m thinking of the following solution. I refrain from choosing $t$ for now, but since we have $\overline{d}(G) \geq \frac{cn}{\text{log}n}$, for the choice of $\alpha = \left(\frac{c}{\text{log}n}\right)^{1/t}$, we do have $\overline{d}(G) \geq \alpha n$. With the parameters chosen, by the lemma we receive a set of vertices $U$ such that any $2$ vertices in $U$ have at least $n^{0.99} + 1$ common neighbors, and furthermore:

$$|U| \geq \frac{c}{\text{log}n} \cdot n - {n \choose 2}\left( \frac{n^{0.99} + 1}{n} \right)^t \geq c - {n \choose 2}\left( \frac{n^{0.99} + 1}{n} \right)^t$$

Now assume we do need $|U| \geq n^{0.99} + 1$ (so that there would be two adjacent vertices in $U$). If ${n \choose 2}\left( \frac{n^{0.99} + 1}{n} \right)^t$ can be upper bounded by something not depending on $n$, then the choice of $c = k(n^{0.99} + 1)$ would do the trick. There are several ways to go further and I’m still thinking, but I’d like to see some comments on this argument.

Answer 1

1. This is the way to do it. In fact, $t=101$ should suffice.

2. It is okay for any of the parameters to depend on $n$ in the statement of DRC.

3. You are to prove that there are $O(n^2/\log n)$ edges, so $c$ has to be a constant. If $c>\log n$, then the problem is trivial, as a graph has at most $\binom{n}{2}$ edges.

Expanding on this: the $\log n$ is really a stand-in for some sufficiently small polynomial factor. We want $|U|$ to be larger than $n^{0.99}$, so we should make sure that $\alpha^t n$ is (much) larger than $n^{0.99}$ and $\binom{n}{r} (m/n)^t$ is (much) smaller than $n^{0.99}$. Taking $m = n^{0.99}$, $r=2$, we need $t\geq 101$ to realize the latter goal. Since $\alpha = \log n$ is subpolynomial, so is $\alpha^t$, and hence the former goal of $\alpha^t n \geq n^{0.99}$ is easily realized.