Randomness in Ramsey theory and coding theory

Job Candidate Talk
Tuesday, January 17, 2023 - 11:00am for 1 hour (actually 50 minutes)
Skiles 006
Xiaoyu He – Princeton University – xiaoyuh@princeton.eduhttps://alkjash.github.io/
Xingxing Yu

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.