Calculating Ramsey Numbers by Partitioning Colored Graphs |
| |
| Authors: | Alexey Pokrovskiy |
| |
| Affiliation: | DEPARTMENT OF MATHEMATICS, ETH ZüRICH, ZüRICH, SWITZERLAND |
| |
| Abstract: | In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for  , in every edge coloring of  with the colors red and blue, it is possible to cover all the vertices with k disjoint red paths and a disjoint blue balanced complete  ‐partite graph. When the coloring of  is connected in red, we prove a stronger result—that it is possible to cover all the vertices with k red paths and a blue balanced complete  ‐partite graph. Using these results we determine the Ramsey number of an n‐vertex path,  , versus a balanced complete t‐partite graph on  vertices,  , whenever  . We show that in this case  , generalizing a result of Erd?s who proved the  case of this result. We also determine the Ramsey number of a path  versus the power of a path  . We show that  , solving a conjecture of Allen, Brightwell, and Skokan. |
| |
| Keywords: | Ramsey theory monochromatic subgraphs partitioning graphs |
|
|
