Premium
The size‐Ramsey number of trees
Author(s) -
Dellamonica Domingos
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20363
Subject(s) - ramsey's theorem , combinatorics , mathematics , conjecture , monochromatic color , discrete mathematics , embedding , graph , invariant (physics) , random graph , ramsey theory , computer science , physics , artificial intelligence , optics , mathematical physics
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom