A Canonical Ramsey Theorem |
| |
Authors: | Nancy Eaton Vojtch Rdl |
| |
Institution: | Nancy Eaton,Vojtěch Rödl |
| |
Abstract: | Say a graph H selects a graph G if given any coloring of H, there will be a monochromatic induced copy of G in H or a completely multicolored copy of G in H. Denote by s(G) the minimum order of a graph that selects G and set s(n) = max {s(G): |G| = n}. Upper and lower bounds are given for this function. Also, consider the Folkman function fr(n) = max{min{|V(H)|: H → (G)1r}: |V(G)| = n}, where H → (G)1r indicates that H is vertex Ramsey to G, that is, any vertex coloring of H with r colors admits a monochromatic induced copy of G. The method used provides a better upper bound for this function than was previously known. As a tool, we establish a theorem for projective planes. |
| |
Keywords: | |
|
|