MIT PhD Thesis Defense: Ashwin Sah

Building 2, Room 449

Presenter: Aswin SahTitle: Random and exact structures in combinatoricsAbstract:We aim to show various developments related to notions of randomness and structure in combinatorics and probability. One central notion, that of the pseudorandomness-structure dichotomy, has played a key role in additive combinatorics and extremal graph theory. In a broader view, randomness (and the pseudorandomness notions which resemble it along various axes) can be viewed as a type of structure in and of itself which has certain typical and global properties that may be exploited to exhibit or constrain combinatorial and probabilistic behavior.These broader ideas often come in concert to allow the construction or extraction of exact behavior. We look at three particular directions: the singularity of discrete random matrices, thresholds for Steiner triple systems, and improved bounds for Szemerédi's theorem. These concern central questions of the areas of random matrices, combinatorial designs, and additive combinatorics.