کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650394 | 1342486 | 2008 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 308, Issue 18, 28 September 2008, Pages 4079–4085