What is a Ramsey Graph?

Question

What is a ramsey graph and What is its relation to RamseyTheorem?

In Ramsey Theorem: for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n vertices with colors r(ed) and b(lue) there will exist a complete subgraph on r vertices colored red or a complete subgraph on b vertices colored blue.

Ramsey Graph : A Ramsey graph is a graph with n vertices, no clique of size s, and no independent set of size t.

I couldnt understand how the above two are related.

Can any one explain what is a Ramsey Graph as simple as possible? (in terms of coloring)

Answer 1

Instead of considering a complete graph $K_n$ whose edges are red and blue, just consider some graph $G$ with $n$ vertices. Let $\bar G$ be the complement of $G$. $\bar G$ contains a clique of size $s$ if and only if $G$ contains an independent set of size $s$.

Now consider $G$ as a subgraph of $K_n$. Color the edges of $G$ in $K_n$ red, and color the other edges of the $K_n$, that is the edges of $\bar G$, blue.

Now $K_n$ contains a red $K_r$ if and only if $G$ contains a clique of size $r$, and $K_n$ contains a blue $K_b$ if $\bar G$ contains a clique of size $b$, which is true if and only if $G$ contains an independent set of size $b$.

The Ramsey theorem says that for given $r$ and $b$ there is an $n$ such that (what you said about $K_n$). A Ramsey graph of size $q$ is a counterexample to the Ramsey theorem, and when it exists, it shows that $n$, which must exist, must be larger than $q$.

Here is an example. Let's take $r=b=3$. The Ramsey theorem says that there is some $n$ such that if we color edges of $K_n$ in red and blue, there is either a red triangle or a blue triangle.

There are many Ramsey graphs. For example, consider $K_2$. It has neither a clique of size $r=3$ nor an independent set of size $b=3$ and therefore it is a ramsey graph for $r=3, b=3$ and shows that the $n$ of the previous paragraph must be bigger than 2.

Now consider $C_5$, the cycle on five vertices. It has neither a clique of size $r=3$ nor an independent set of size $b=3$ and therefore it is a ramsey graph for $r=3, b=3$ and shows that the $n$ given by the Ramsey theorem must be bigger than 5.

The Ramsey theorem claims that when $n$ is large enough, there is no Ramsey graph with $n$ or more vertices.

Answer 2

Given natural numbers $r,b$ Ramsey's Theorem states that there is a natural number $n$ such that if you colour the edges of $K_n$, the complete graph on $n$ vertices, you get either a copy of $K_r$ all edges of which are coloured red, or a copy of $K_b$ all edges of which are coloured blue. Let us denote by $R(r,b)$ the least such number $n$, this is called the Ramsey number of $r$ and $b$.

A Ramsey graph (with respect to integers $s$ and $t$) is just some some graph containing neither a copy of $K_s$ nor a copy of the "trivial graph" on $t$ vertices (a graph where there are no edges). Note that if $( G , E )$ is a Ramsey graph with respect to $s,t$ on $n$ vertices, we can create a colouring of $K_n$ as follows:

• Enumerate $G = \{ v_1 , \ldots , v_n \}$.
• If there is an edge between $v_i$ and $v_j$ in $G$, colour the edge $\{ i , j \}$ in $K_n$ red; otherwise colour that edge blue.

It should be easy to see that in $K_n$ there is no copy of $K_s$ all edges of which are coloured red: if there was we could translate this to a clique of size $s$ in the original graph $(G,E)$. And neither is there a copy of $K_t$ all edges of which are coloured blue. Therefore this colouring serves as proof that $R ( s,t ) > n$. Or, equivalently, the existence of a Ramsey graph for $s,t$ on $n$ vertices serves as proof that $R(s,t) > n$.