The size-Ramsey number of trees |
| |
Authors: | P E Haxell Y Kohayakawa |
| |
Institution: | 1. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, CB2 1SB, Cambridge, England 3. Instituto de Matemática e Estatística, Universidade de S?o Paulo, Caixa Postal 20570, 01452-990, S?o Paulo, SP, Brazil
|
| |
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)}. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|