Name
Abstract | ||
|---|---|---|
A celebrated result of Chv\'atal, R\"odl, Szemer\'edi and Trotter states (in slightly weakened form) that, for every natural number $\Delta$, there is a constant $r_\Delta$ such that, for any connected $n$-vertex graph $G$ with maximum degree $\Delta$, the Ramsey number $R(G,G)$ is at most $r_\Delta n$, provided $n$ is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take $r_\Delta = \Delta$. However, Graham, R\"odl and Ruci\'nski showed, by taking $G$ to be a suitable expander graph, that necessarily $r_\Delta > 2^{c\Delta}$ 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 $\beta (n) = o(n)$, then $R(G,G) \le (2\chi(G)+4)n\leq (2\Delta+6)n$, i.e., $r_\Delta = 2\Delta +6$ suffices. On the other hand, we show that Burr's conjecture itself fails even for $P_n^k$, the $k$th power of a path $P_n$. Brandt showed that for any $c$, if $\Delta$ is sufficiently large, there are connected $n$-vertex graphs $G$ with $\Delta(G)\leq\Delta$ but $R(G,K_3)>cn$. We show that, given $\Delta$ and $H$, there are $\beta>0$ and $n_0$ such that, if $G$ is a connected graph on $n\ge n_0$ vertices with maximum degree at most $\Delta$ and bandwidth at most $\beta n$, then we have $R(G,H)=(\chi(H)-1)(n-1)+\sigma(H)$, where $\sigma(H)$ is the smallest size of any part in any $\chi(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 $\epsilon(H) \log n/\log\log n$. |
Year | Venue | Keywords |
|---|---|---|
2013 | Combinatorica | connected graph,ramsey number,maximum degree,expander graph |
Field | DocType | Volume |
Graph,Discrete mathematics,Natural number,Combinatorics,Expander graph,Vertex (geometry),Ramsey's theorem,Degree (graph theory),Connectivity,Conjecture,Mathematics | Journal | 33 |
Issue | Citations | PageRank |
2 | 9 | 0.84 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Allen | 1 | 9 | 1.18 |
| Graham R. Brightwell | 2 | 192 | 25.09 |
| Jozef Skokan | 3 | 251 | 26.55 |