Ramsey theorem with forbidden induced subgraph

Question

Given $n \in \mathbb{N}$, I want to prove that there exist $f(n) \in \mathbb{N}, 0<\alpha(n) \leq 1$ such that for every graph $G=(V,E)$ with $|V| > f(n)$ vertices, and a set $R \subseteq V \times V$ where $|R| \leq \alpha(n) {|V| \choose 2}$, there is a clique or anti clique of size $n$ whose edges/anti-edges are not in $R$ (non of the edges are in $R$). Very similar to Ramsey thorem but with the constraint of $R$.
I tried to prove in the following manner:
Take $f(n)$ to be the $n'$th Ramsey number. When choosing a pair of vertices $\{u,v\} \in V \times V$ randomly with uniform distribution , the probability that this pair is in $R$ is: $\frac{|R|}{|V \times V|} = \alpha(n)$. Since there is at least one clique/anti-clique, there are at least $n \choose 2$ edges/anti-edges that are part of clique/anti-clique. Hence the probability that random pair is a part of a clique/anti-clique is $\frac{{n \choose 2}}{{|V| \choose 2}} = \frac{n(n-1)}{|V|(|V|-1)}$. Thus, the probability that a random pair is NOT in $R$ AND in a clique/anti-clique is $\frac{n(n-1)}{|V|(|V|-1)}(1 - \alpha(n))$. There are $|V| \choose 2$ such pairs. I want the expectation of the number of pairs to be larger than $n \choose 2$ , so: $$ \frac{n(n-1)}{|V|(|V|-1)} (1-\alpha(n))\frac{|V|(|V|-1)}{2} \geq \frac{n(n-1)}{2}$$ Which leads to $\alpha(n) = 0$ - clearly incorrect.
My question is: how can I improve this method in order to achieve $\alpha(n) > 0$? I thought about taking $f(n)$ to be such that every graph with $|V| > f(n)$ vertices will have at least $n$ cliques, but I did all the math and it's also incorrect.

Answer 1

Let $f(n)$ be the $n$th Ramsey number, and let $\alpha(n) = \left(\frac{1}{f(n)-1}\right)^2$. Then $|R|\leq \alpha(n) \binom{|V|}{2}$ and we have:

$$\begin{align} |(V \times V) \backslash R| &\geq \binom{|V|}{2} - \alpha(n)\binom{|V|}{2} \\ &= \binom{|V|}{2}\left(1-\left(\frac{1}{f(n)-1}\right)^2\right) \\ &= \frac{|V|(|V|-1)}{2}\left(1+\frac{1}{f(n)-1}\right)\left(1-\frac{1}{f(n)-1}\right) \\ &> \frac{|V|(|V|-1)}{2}\left(1+\frac{1}{|V|-1}\right)\left(1-\frac{1}{f(n)-1}\right) \\ &= \frac{|V|(|V|-1)}{2}\left(\frac{|V|}{|V|-1}\right)\left(1-\frac{1}{f(n)-1}\right) \\ &= \frac{|V|^2}{2}\left(1-\frac{1}{f(n)-1}\right) \end{align}$$

Thus by Turán's Theorem, there is a subset $S$ of $V$ with $|S|=f(n)$ so that $G[S]$ does not contain any edges of $R$, and $G[S]$ has either $K_n$ or $\overline{K_n}$.