Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
so,the ramsey graph need not to be complete graph?? –  Roronoa Mar 10 '13 at 4:47
    
no, not at all. –  MJD Mar 10 '13 at 4:51

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$.

share|improve this answer
    
I need to check wether a complete graph is ramsey graph or not given r colorings ,n vertices and clique of size 3. so, from the explanation given above if there is no monochromatic triangle then is it a ramsey graph?? –  Roronoa Mar 10 '13 at 4:30
    
@PranayVarma: What I provided was essentially a translation between Ramsey graphs (as you defined them in the OP) and edge-colourings of the complete graph. For Ramsey graphs as technically defined above, there are no edge-colourings. To check that a graph is a Ramsey graph (with respect to integers $s,t$) means just looking for cliques or independent sets of the appropriate sizes. –  Arthur Fischer Mar 10 '13 at 4:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.