MATH Seminar

Title: Randomness in Ramsey Theory and Coding Theory
Job Talk: Combinatorics
Speaker: Xiaoyu He, NSF Postdoctoral Research Fellow of Princeton University
Contact: Liana Yepremyan, liana.yepremyan@emory.edu
Date: 2023-01-19 at 10:00AM
Venue: MSC W201
Download Flyer
Abstract: Two of the most influential theorems in discrete mathematics state, respectively, that diagonal Ramsey numbers grow exponentially and that error-correcting codes for noisy channels exist up to the information limit. The former, proved by Erd?s in 1947 using random graphs, led to the development of the probabilistic method in combinatorics. The latter, proved by Shannon in 1948 using random codes, is one of the founding results of coding theory. Since then, the probabilistic method has been a cornerstone in the development of both Ramsey theory and coding theory. In this talk, we highlight a few important applications of the probabilistic method in these two parallel but interconnected worlds. We then present new results on Ramsey numbers of graphs and hypergraphs and codes correcting deletion errors, all based on probabilistic ideas.