Faculty Recruiting Support CICS

Ramsey Properties in Dense and Sparse Graph Classes

01 Apr
Wednesday, 04/01/2020 12:15pm to 1:15pm
Theory Seminar
Speaker: Rik Sengupta

To view this live seminar via Zoom, visit: 

Abstract: For graphs F and H, we say F is *Ramsey* for H if any two-coloring of the edges of F is forced to contain a monochromatic copy of H. F is *Ramsey H-minimal* (or simply H-minimal) if F is Ramsey for H, but no proper subgraph of F is. The collection of all H-minimal graphs F is denoted M(H), an object of significant combinatorial interest. For instance, Ramsey's Theorem is the statement that M(H) is nonempty for all H, essentially proving that complete structural disorder is impossible. This result is a stepping stone to the vast and beautiful area of extremal graph theory known as Ramsey Theory, an area of immense importance in mathematics, with applications ranging from toy puzzles to the Szemeredi Regularity Lemma. We are interested in characterizing the minimum degree over all graphs in M(H), a problem that turns out to be quite hard even for specific graph classes. In this talk, I will fully characterize this minimum degree for a certain class of dense graphs. If time permits, I'll extend these techniques to sparse graphs as well, obtaining a complete characterization for almost all regular graphs. I will assume no prior background in Ramsey Theory. This is joint work with Andrey Grinshpun and Raj Raina.