# Ramsey theorem with forbidden induced subgraph

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.

• By "and a set $R$" do you mean "for every set $R$" or do you mean "there exists a set $R$"? The only restriction on $\alpha(n)$ is that $\alpha(n)\le1$? No lower bound? Not even $\alpha(n)\gt0$? – bof Apr 21 '17 at 10:07
• $\alpha(n)>0$. The set $R$ is given, it cannot hold for every set $R$ (it's size is larger than the clique size for sufficient large $|V|$, so there is such set that contains the clique). – Horvey Apr 21 '17 at 12:46
• Do you mean $|R| \leq \alpha(n) \binom{|V|}{2}$? – Perry Elliott-Iverson Apr 21 '17 at 14:35
• yes. My mistake. Will edit – Horvey Apr 21 '17 at 14:44

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}$.
• Turan's theorem states that if I had $|V|^2/2 (1-1/(f(n)-1))$ edges, then I have clique of size $f(n)$. How is it helping to take the $n$'th Ramsey number? Not sure I understand your "punchline" – Horvey Apr 22 '17 at 18:02
• There are at least $\frac{|V|^2}{2}\left(1-\frac{1}{f(n)-1}\right)$ members of $V \times V$ that are not in $R$, so Turan's theorem says that the graph $G'$ with vertex set $V$ and edge set $(V \times V) \backslash R$ must have a $K_{f(n)}$. Let $S \subseteq V$ be the set of vertices of this $K_{f(n)}$. Then no members of $R$ have both ends in $S$, and $G[S]$ is a graph with $f(n)$ vertices, which must have $K_n$ or $\overline{K_n}$ by Ramsey's Theorem. – Perry Elliott-Iverson Apr 22 '17 at 19:56
• But $G$ does not necessarily contain all the edges in $V \times V$. What if $G$ has much less edges? – Horvey Apr 23 '17 at 4:47
• The number of edges in $G$ is irrelevant. We found a large enough (order $f(n)$, which guarantees $K_n$ or $\overline{K_n}$) subset of the vertices of $G$ with no members of $R$ having both ends in that subset. – Perry Elliott-Iverson Apr 24 '17 at 19:51