比利时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
****************************