Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can anyone explain me what is a Ramsey Graph with a simple example? What are its properties?

share|improve this question

closed as off-topic by Ricardo Andrade, David White, Daniel Moskovich, Chris Godsil, Jack Huizenga Dec 1 '13 at 4:58

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Chris Godsil, Jack Huizenga
  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ricardo Andrade, David White, Daniel Moskovich
If this question can be reworded to fit the rules in the help center, please edit the question.

    
    
i already referred it but i couldnt understand how is it related to R(r,k,l) Ramsey Theorem –  pranay Mar 9 '13 at 10:04
    
can u pls explain it 2 or 3 simple sentences –  pranay Mar 9 '13 at 10:05
    
Welcome to MO! This question does not really fit in the narrow scope of this site (for details see faq, link at the top); you will likely have a better reception of your question on math.stackexchange.com a similar site yet with a broader scope. That being said, since you got some piece of information here let me try to give the 2 or 3 sentences you asked for (though I am not really well placed to do so). –  quid Mar 9 '13 at 11:41

1 Answer 1

up vote 3 down vote accepted

The form in which you might be familiar with the result is this:

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.

One can then try to determine the smalles such $n$ and this is the respective Ramsey number.

Now, you can rephrase this problem not as coloring problem but like so:

for a pairs of parameters $(r,b)$ there exists an $n$ such that for every graph on $n$ vertices there will exist a complete subgraph on $r$ vertices or for the complement of the graph there will exist a complete subgrpah on $b$ vertices.

The complement of the graph is precisely the graph with those edges not present in the original graph. In other words, if you color, consider the graph just formed by the red edges, the complement will be the grpah with the blue edges.

Still differently, one says a graph contains a clique of size $r$ if it contains a complete subgraph of that size. Conversely, one says it contains an independent set of size $b$ if there is a set of vertices size $b$ with no edges among these vertices. (In other words in the complement this will be a clique.)

So, one can also state the result above in the form:

For every pair of parameters $(r,b)$ there is an $n$ such that each graph on $n$ vertices will contain a clique of size $r$ or an independent set of size $b$.

Now, this result in particular implies that, given $(r,b)$ there are only a finite number of graphs that do not have a clique of size $r$ or an independent set of size $b$. Such a graph is then called a Ramsey graph for the respective parameters, and sometimes the number of vertices of the graph is given as additional parameter.

So, a Ramsey graph (with certain parameters) is an example of a graph were what is implied by the respective Ramsey theorem (for sufficiently large graphs) does not hold true. (Of course its number of vertices thus is smaller than the relevant Ramsey number.
And, the maximal number of vertices of a Ramsey graph is just one smaller than the respective Ramsey number)

share|improve this answer
    
Given as answer, as somehow I needed more than 2 or 3 sentences. –  quid Mar 9 '13 at 12:10

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