What is a Ramsey Graph? 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)

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