Leírás
Abstract:
A graph is Ramsey if the size of its largest clique or independent set is only logarithmic in the number of vertices. In 1947, Erdős used probability to show that almost all graphs are Ramsey. Despite their ubiquitous nature, no explicit construction of Ramsey graphs is known. In this talk, I will discuss progress on locating this "dark matter" of graphs, and connections to fundamental problems in information theory and number theory. Along the way, we study basic problems in additive combinatorics, and discover that group structure is superfluous for these problems. Based on joint work with David Conlon, Huy Tuan Pham, and Liana Yepremyan.
Online access:
Join Zoom Meeting https://us06web.zoom.us/j/86830466823?pwd=cdlaQHFjXWTUrMh56x3g5uRYQORsbf.1
Meeting ID: 868 3046 6823
Passcode: 329735