Graphs with N Nodes: Proving Cliques and Anti-Cliques

[mathmari]

Hey!

Let $G$ be a graph. A clique in $G$ is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1}{2} \log_2 n$ nodes.

Could you give me some hints how we could show this?? (Wondering)

 

[magneto1]

Apply Ramsey's theory. Let $R(m,n)$ be the least integer $s$ where a graph $G$ with $s$ vertices contain either a $m$-clique or an $n$-independent set.

Then, use the properties of $R(\cdot, \cdot)$ to show that $R(n,n) \leq 2^{2n}$.

 

[mathmari]

Apply Ramsey's theory. Let $R(m,n)$ be the least integer $s$ where a graph $G$ with $s$ vertices contain either a $m$-clique or an $n$-independent set.

Then, use the properties of $R(\cdot, \cdot)$ to show that $R(n,n) \leq 2^{2n}$.

Could you explain to me further what I have to do?? (Wondering) I got stuck right now...

 

[mathmari]

When we have graphs with $3$ nodes:

View attachment 4021

doesn't the graphs have cliques or anti-cliques with at least $2$ nodes??

But $\frac{1}{2} \log_2 3=0.7924 \dots $. So have I done something wrong?? (Wondering)

 

[magneto1]

You want to use (or proof) the result:

\[
R(r,s) \leq \binom{r+s-2}{r-1}.
\]

In your example, $R(2,2) = 2$, in other words, any graph that has $2$ or more vertices, you are going to find a $2$-clique or $2$-independent set. But that's not what the actual statement you want to prove. In the case $\nu = 3$,
the statement in fact promises a $0$-clique or a $0$-independent set, which is vacuously true.

 

[mathmari]

You want to use (or proof) the result:

\[
R(r,s) \leq \binom{r+s-2}{r-1}.
\]

In your example, $R(2,2) = 2$, in other words, any graph that has $2$ or more vertices, you are going to find a $2$-clique or $2$-independent set. But that's not what the actual statement you want to prove. In the case $\nu = 3$,
the statement in fact promises a $0$-clique or a $0$-independent set, which is vacuously true.

I got stuck right now... To show that every graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1}{2} \log_2 n$ nodes why do we have to show that $R(n, n) \leq 2^{2n}$ ??

$$R(n, n) \leq \binom{n+n-2}{n-1}=\binom{2n-2}{n-1}=\frac{(2(n-1))!}{(n-1)!(n-1)!}$$ How could we continue?? (Wondering)

 

[magneto1]

The equation follows from the definition of $R$ and the problem statement.

The inequality follows from the fact that, for $m \geq n$

\[
\binom mn < \sum_k \binom mk = 2^m.
\]