Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 16, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Graham Brightwell (LSE)
Given two graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest $N$ such that, however the edges of the complete graph $K_N$ are coloured with red and blue, there exists either a red copy of $G$ or a blue copy of $H$. Burr gave a simple general lower bound on the Ramsey number $R(G,H)$, valid for all connected graphs $G$: defining $\sigma(H)$ to be the smallest size of any colour class in any colouring of $H$ with $\chi(H)$ colours, we have
$R(G,H) \ge (\chi(H)-1)(|G|-1) + \sigma(H).$
For a given graph $H$, it is natural to ask which connected graphs $G$ attain this bound. A class of graphs is called Ramsey-good if, for each fixed $H$, Burr's bound is attained for all sufficiently large graphs in the class.
In this talk we will give an overview of some known results about Ramsey-goodness, and offer some new results. In particular, we shall explore connections between Ramsey-goodness and the bandwidth.
Joint work with Peter Allen and Jozef Skokan.
Automatic MiSe System Software Version 1.4803M | admin login