Chromatic Ramsey Theory

AbstractLet G be a countable graph which has infinite chromatic number. Ifγis a coloring of [G]2with two colors, is there then a subsetH⊆Gsuch thatγis constant on [H]2andG|H,the graph induced by G onH,has infinite chromatic number? As edges and non-edges can be colored with different colors this will be the case iff G contains an infinite clique. It turns out that if the clique size of G is unbounded but G does not contain an infinite clique then for every coloring of [G]2withτcolors, there are some two of theτcolors such that there is an infinite chromatic subgraph of G the vertex set of which forms only pairs colored in those two colors; and this is best possible, because one can always distinguish between edges and non-edges. In the case in which the graphs do not contain the complete graph onnvertices the situation is much more complicated. We will show that for every 3≤n ∈οthere is a graph G, which does not embed the complete graph onnvertices, with the property that for every positive numberτthere exists a coloring of [G]2withτcolors such that the vertex set of every infinite chromatic subgraph of G forms pairs in each of theτcolors. On the other hand there is a graph G, which does not embed the complete graph onnvertices, and which has the property that for every positive numberτand every coloring of [G]2withτcolors there is an infinite chromatic subgraph of G the pairs of which use at most 3 colors. We will generalize to the case of colorings ofk-element subsets