Departmental Colloquium
Xiaoyu He
Princeton
Randomness in Ramsey theory and coding theory
Abstract: wo 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 give an overview of the 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.
Thursday December 8, 2022 at 3:00 PM in 636 SEO