Loading Events

Additive combinatorics without addition: Ramsey Cayley graphs, information theory, and independence in random graph models

SEMINARS: HARVARD-MIT COMBINATORICS

When: October 11, 2023
4:15 pm - 5:15 pm
Where: MIT, Room 2-139
Speaker: Jacob Fox - Stanford University

A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. We discuss recent progress on locating these “dark matter” of graphs. Along the way, we study some fundamental problems in additive combinatorics, and discover that group structure is superfluous for these problems. This leads to the solution of several longstanding problems in information theory, additive combinatorics, and random graph theory. Joint work with David Conlon, Huy Tuan Pham, and Liana Yepremyan.

For more info, see https://math.mit.edu/combin/