Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650394 | Discrete Mathematics | 2008 | 7 Pages |
Let (T1,T2,…,Tc)(T1,T2,…,Tc) be a fixed cc-tuple of sets of graphs (i.e. each TiTi is a set of graphs). Let R(c,n,(T1,T2,…,Tc))R(c,n,(T1,T2,…,Tc)) denote the set of all nn-tuples, (a1,a2,…,an)(a1,a2,…,an), such that every cc-coloring of the edges of the complete multipartite graph, Ka1,a2,…,anKa1,a2,…,an, forces a monochromatic subgraph of color ii from the set TiTi (for at least one ii). If NN denotes the set of non-negative integers, then R(c,n,(T1,T2,…,Tc))⊆NnR(c,n,(T1,T2,…,Tc))⊆Nn. We call such a subset of NnNn a “Ramsey region”. An application of Ramsey's Theorem shows that R(c,n,(T1,T2,…,Tc))R(c,n,(T1,T2,…,Tc)) is non-empty for n⪢0n⪢0. For a given cc-tuple, (T1,T2,…,Tc)(T1,T2,…,Tc), known results in Ramsey theory help identify values of nn for which the associated Ramsey regions are non-empty and help establish specific points that are in such Ramsey regions. In this paper, we develop the basic theory and some of the underlying algebraic structure governing these regions.