Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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)

Ramsey-goodness

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login