Can anyone explain me what is a Ramsey Graph with a simple example? What are its properties?
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
The form in which you might be familiar with the result is this:
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:
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:
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.