Computer Science/Discrete Mathematics Seminar I | |

Topic: | Ramsey numbers of degenerate graphs |

Speaker: | Choongbum Lee |

Affiliation: | Massachusetts Institute of Technology |

Date: | Monday, September 28 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2015/0928-ChoongbumLee |

The Ramsey number of a graph $G$ is the minimum integer $n$ for which every edge-coloring of the complete graph on $n$ vertices with two colors contains a monochromatic copy of $G$. A graph is $d$-degenerate if all its subgraphs have a vertex of degree at most $d$. In this talk, we prove that for all $d$, there exists a constant $c$ such that every $d$-degenerate graph $G$ has Ramsey number at most $c|V(G)|$. This solves a conjecture of Burr and ErdÅ‘s from 1973.