Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Po-Shen Loh

Princeton University

Constrained Ramsey Numbers

Abstract:

For two graphs $S$ and $T$, the constrained Ramsey number $f(S, T)$ is the minimum $n$ such that every edge coloring of the complete graph on $n$ vertices (with any number of colors) has a monochromatic subgraph isomorphic to $S$ or a rainbow subgraph isomorphic to $T$. Here, a subgraph is said to be rainbow if all of its edges have different colors. It is an immediate consequence of the Erd\H{o}s-Rado Canonical Ramsey Theorem that $f(S, T)$ exists if and only if $S$ is a star or $T$ is acyclic. Much work has been done to determine the rate of growth of $f(S, T)$ for various types of parameters. When $S$ and $T$ are both trees having $s$ and $t$ edges respectively, Jamison, Jiang, and Ling showed that $f(S, T) \leq O(st^2)$ and conjectured that it is always at most $O(st)$. They also mentioned that one of the most interesting open special cases is when $T$ is a path. We study this case and show that $f(S, P_t) = O(st\log t)$, which differs only by a logarithmic factor from the conjecture. This substantially improves the previous bounds for most values of $s$ and $t$.

Host: Fan Chung Graham

May 15, 2007

4:00 PM

AP&M 7321

****************************