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 |
|
|