Abstract
IfG andH are graphs, let us writeG→(H)2 ifG contains a monochromatic copy ofH in any 2-colouring of the edges ofG. Thesize-Ramsey number r e(H) of a graphH is the smallest possible number of edges a graphG may have ifG→(H)2. SupposeT is a tree of order |T|≥2, and lett 0,t 1 be the cardinalities of the vertex classes ofT as a bipartite graph, and let Δ(T) be the maximal degree ofT. Moreover, let Δ0, Δ1 be the maxima of the degrees of the vertices in the respective vertex classes, and letβ(T)=T 0Δ0+t 1Δ1. Beck [7] proved thatβ(T)/4≤r e(T)=O{β(T)(log|T|)12}, improving on a previous result of his [6] stating thatr e(T)≤Δ(T)|T|(log|T|)12. In [6], Beck conjectures thatr e(T)=O{Δ(T)|T|}, and in [7] he puts forward the stronger conjecture thatr e(T)=O{β(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing thatr e(T)=O{β(T)logΔ(T)}.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon,Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica6 (1986), 207–219.
N. Alon,Personal communication, August 1993.
N. Alon and F. R. K. Chung,Explicit construction of linear sized tolerant networks, Discrete Mathematics72 (1988), 15–19.
N. Alon, O. Goldreich, J. Håstad and R. Peralta,Simple constructions of almost k-wise independent random variables, Random Structures and Algorithms3 (1992), 289–304.
N. Alon and Y. Roichman,Random Cayley graphs and expanders, to appear.
J. Beck,On size Ramsey number of paths, trees, and circuits I, Journal of Graph Theory7 (1983), 115–129.
J. Beck,On size Ramsey number of paths, trees, and circuits II, inMathematics of Ramsey Theory (J. Nešetřil and V. Rödl, eds.), Algorithms and Combinatorics 5, Springer-Verlag, Berlin, 1990, pp. 34–45.
B. Bollobás,Random Graphs, Academic Press, London, xvi + 447pp, 1985.
E. Bombieri,On the large sieve, Mathematika12 (1965), 201–225.
H. Davenport,Multiplicative Number Theory, Second edition, Graduate Texts in Mathematics 74, Springer-Verlag, New York, xiv + 177pp, 1980.
J. Friedman and N. Pippenger,Expanding graphs contain all small trees, Combinatorica7 (1987), 71–76.
P. E. Haxell and Y. Kohayakawa,On an anti-Ramsey property of Ramanujan graphs, to appear.
W. Hoeffding,Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association58 (1963), 13–30.
X. Ke,The size Ramsey number of trees with bounded degree, Random Structures and Algorithms4 (1993), 85–97.
L. Lovász,Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979.
A. Lubotzky, R. Phillips and P. Sarnak,Ramanujan graphs, Combinatorica8 (1988), 261–277.
C. J. H. McDiarmid,On the method of bounded differences, inSurveys in Combinatorics 1989 (J. Siemons, ed.), London Mathematical Society Lecture Notes Series 141, Cambridge University Press, Cambridge, 1989, pp. 148–188.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Haxell, P.E., Kohayakawa, Y. The size-Ramsey number of trees. Israel J. Math. 89, 261–274 (1995). https://doi.org/10.1007/BF02808204
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02808204