Ramsey-goodness—and otherwise |
| |
Authors: | Peter Allen Graham Brightwell Jozef Skokan |
| |
Institution: | 12778. Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK
|
| |
Abstract: | A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number Δ, there is a constant r Δ such that, for any connected n-vertex graph G with maximum degree Δ, the Ramsey number R(G,G) is at most r Δ n, provided n is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take r Δ = Δ. However, Graham, Rödl and Ruciński showed, by taking G to be a suitable expander graph, that necessarily r Δ > 2 cΔ for some constant c>0. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of G be at most some function β(n)=o(n), then R(G,G)≤(2χ(G)+4)n≤(2Δ+6)n, i.e., r Δ =2Δ+6 suffices. On the other hand, we show that Burr’s conjecture itself fails even for P n k , the kth power of a path P n . Brandt showed that for any c, if Δ is sufficiently large, there are connected n-vertex graphs G with Δ(G)≤Δ but R(G,K 3) > cn. We show that, given Δ and H, there are β>0 and n 0 such that, if G is a connected graph on n≥n 0 vertices with maximum degree at most Δ and bandwidth at most β n , then we have R(G,H)=(χ(H)?1)(n?1)+σ(H), where σ(H) is the smallest size of any part in any χ(H)-partition of H. We also show that the same conclusion holds without any restriction on the maximum degree of G if the bandwidth of G is at most ?(H) log n=log logn. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|