printable pdf
比利时vs摩洛哥足彩 ,
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

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