The size‐Ramsey number of trees |
| |
Authors: | Domingos Dellamonica Jr |
| |
Institution: | Department of Mathematics, Emory University, 400 Dowman Dr, Atlanta, Georgia 30322 |
| |
Abstract: | Given a graph G, the size‐Ramsey number $\hat r(G)$ is the minimum number m for which there exists a graph F on m edges such that any two‐coloring of the edges of F admits a monochromatic copy of G. In 1983, J. Beck introduced an invariant β(·) for trees and showed that $\hat r(T) = \Omega (\beta (T))$ . Moreover he conjectured that $\hat r(T) = \Theta (\beta (T))$ . We settle this conjecture by providing a family of graphs and an embedding scheme for trees. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 |
| |
Keywords: | size‐Ramsey number trees expander graphs |
|
|