Mathematics – Combinatorics
Scientific paper
2007-06-14
Mathematics
Combinatorics
12 pages; minor revisions
Scientific paper
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 (all edges differently colored) subgraph isomorphic to T. The Erdos-Rado Canonical Ramsey Theorem implies that f(S, T) exists if and only if S is a star or T is acyclic, and 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) <= 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. In this work, 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.
Loh Po-Shen
Sudakov Benny
No associations
LandOfFree
Constrained Ramsey Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constrained Ramsey Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constrained Ramsey Numbers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-331129