Constrained Ramsey Numbers

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-331129

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.