MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Graph Nodes
AI Thread Summary
Every graph with n nodes contains either a clique or an anti-clique of at least \(\frac{1}{2} \log_2 n\) nodes, as established through Ramsey's theory. The discussion emphasizes the application of Ramsey's number \(R(m,n)\) to demonstrate that \(R(n,n) \leq 2^{2n}\). Participants clarify that for graphs with three nodes, the existence of cliques or anti-cliques of size two is guaranteed, aligning with the theoretical framework. The conversation also highlights the relationship between Ramsey's numbers and combinatorial properties, specifically using binomial coefficients to support the proof. Ultimately, the proof relies on understanding these combinatorial principles to validate the initial claim.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
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}$.
 
magneto said:
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...
 
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)
 

Attachments

  • (Anti-)Clique.png
    (Anti-)Clique.png
    11.1 KB · Views: 132
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.
 
magneto said:
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)
 
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.
\]
 
Back
Top