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.

  • $\begingroup$ 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$? $\endgroup$ – bof Apr 21 '17 at 10:07
  • $\begingroup$ $\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). $\endgroup$ – Horvey Apr 21 '17 at 12:46
  • $\begingroup$ Do you mean $|R| \leq \alpha(n) \binom{|V|}{2}$? $\endgroup$ – Perry Elliott-Iverson Apr 21 '17 at 14:35
  • $\begingroup$ yes. My mistake. Will edit $\endgroup$ – 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}$.

  • $\begingroup$ 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" $\endgroup$ – Horvey Apr 22 '17 at 18:02
  • $\begingroup$ 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. $\endgroup$ – Perry Elliott-Iverson Apr 22 '17 at 19:56
  • $\begingroup$ But $G$ does not necessarily contain all the edges in $V \times V$. What if $G$ has much less edges? $\endgroup$ – Horvey Apr 23 '17 at 4:47
  • $\begingroup$ 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. $\endgroup$ – Perry Elliott-Iverson Apr 24 '17 at 19:51

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.