## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, March 22, 2018, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Matthew Kwan

## Induced subgraphs of Ramsey graphs

An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. We discuss two results showing that all Ramsey graphs must obey certain "richness" properties characteristic of random graphs. First, resolving a conjecture of Narayanan, Sahasrabudhe and Tomon, motivated by an old problem of Erd\H{o}s and McKay, we prove that every C-Ramsey graph has $\Omega(n^2)$ induced subgraphs with different numbers of edges. Second, resolving a conjecture of Erd\H{o}s, Faudree and S\'{o}s, we prove that every C-Ramsey graph has $\Omega(n^{5/2})$ induced subgraphs, no two of which have the same numbers of vertices and edges. This is joint work with Benny Sudakov.

Information for students and suggested topics for student talks