Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-16T16:16:39.432Z Has data issue: false hasContentIssue false
  • English
  • Français

Constrained Ramsey Numbers

Published online by Cambridge University Press:  01 March 2009

PO-SHEN LOH  and
BENNY SUDAKOV
PO-SHEN LOH
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA (e-mail: [email protected])
BENNY SUDAKOV
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge colouring of the complete graph on n vertices (with any number of colours) 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 colours. It is an immediate consequence of the Erdő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) ≤ O(st2) 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 paper, we study this case and show that f(S, Pt) = 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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 1-2: Papers from The 2006 Oberwolfach Meeting on Combinatorics, Probability and Computing , March 2009 , pp. 247 - 258
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N., Jiang, T., Miller, Z. and Pritikin, D. (2003) Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints. Random Struct. Alg. 23 409–433.CrossRefGoogle Scholar
[2]Balister, P., Gyárfás, A.Lehel, J. and Schelp, R. (2006) Mono-multi bipartite Ramsey numbers, designs, and matrices, J. Combin. Theory Ser. A 113 101–112.CrossRefGoogle Scholar
[3]Bialostocki, A. and Voxman, W. (2003) On monochromatic-rainbow generalizations of two Ramsey type theorems. Ars Combinatoria 68 131–142.Google Scholar
[4]Chen, G., Schelp, R. and Wei, B. (2001) Monochromatic-rainbow Ramsey numbers. Unpublished work in 14th Cumberland Conference Abstracts.Google Scholar
[5]Dean, N. and Latka, B. (1995) Squaring the tournament: An open problem. Congr. Numer. 109 73–80.Google Scholar
[6]Erdős, P. and Rado, R. (1950) A combinatorial theorem. J. London Math. Soc. 25 249–255.CrossRefGoogle Scholar
[7]Eroh, L. (2004) Constrained Ramsey numbers of matchings. J. Combin. Math. Combin. Comput. 51 175–190.Google Scholar
[8]Eroh, L. (2004) Rainbow Ramsey numbers of stars and matchings. Bull. Inst. Combin. Appl. 40 91–99.Google Scholar
[9]Gyárfás, A., Lehel, J., Nešetřil, J., Rödl, V., Schelp, R. and Tuza, Z. (1987) Local k-colorings of graphs and hypergraphs. J. Combin. Theory Ser. B 43 127–139.CrossRefGoogle Scholar
[10]Gyárfás, A., Lehel, J. and Schelp, R. (2007) Finding a monochromatic subgraph or a rainbow path. J. Graph Theory 54 1–12.CrossRefGoogle Scholar
[11]Gyárfás, A., Lehel, J., Schelp, R. and Tuza, Z. (1987) Ramsey numbers for local colorings. Graphs Combin. 3 267–277.CrossRefGoogle Scholar
[12]Havet, F. and Thomassé, S. (2000) Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture. J. Graph Theory 35 244–256.3.0.CO;2-H>CrossRefGoogle Scholar
[13]Jamison, R., Jiang, T. and Ling, A. C. H. (2003) Constrained Ramsey numbers of graphs. J. Graph Theory 42 1–16.CrossRefGoogle Scholar
[14]Jamison, R. and West, D. (2004) On pattern Ramsey numbers of graphs. Graphs Combin. 20 333–339.CrossRefGoogle Scholar
[15]Schelp, R. (1997) Local and mean k-Ramsey numbers for complete graphs. J. Graph Theory 24 201–203.3.0.CO;2-T>CrossRefGoogle Scholar
[16]Thomason, A. and Wagner, P. (2007) Complete graphs with no rainbow path, J. Graph Theory 54 261–266.CrossRefGoogle Scholar
[17]Truszczyński, M. and Tuza, Z. (1987) Linear upper bounds for local Ramsey numbers. Graphs Combin. 3 67–73.CrossRefGoogle Scholar
[18]Wagner, P. (2006) An upper bound for constrained Ramsey numbers. Combin. Probab. Comput. 15 619–626.CrossRefGoogle Scholar
[19]Wormald, N. (1983) Subtrees of large tournaments. In Combinatorial Mathematics X, Vol. 1036 of Lecture Notes in Mathematics, Springer, pp. 417–419.CrossRefGoogle Scholar