Skip navigation
Please use this identifier to cite or link to this item:
Title: Challenges and Results in Extremal Combinatorics
Authors: Alweiss, Ryan
Advisors: Alon, Noga M
Contributors: Mathematics Department
Keywords: combinatorics
set system
Subjects: Mathematics
Issue Date: 2023
Publisher: Princeton, NJ : Princeton University
Abstract: In this thesis, we address several questions in extremal, probabilisitic, and additive combinatorics, with applications to theoretical computer science. We start by addressing the sunflower lemma of Erd ̋os and Rado, and some related problems about set systems. A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all of them. Erd ̋os and Rado provedthe sunflower lemma: for any fixed r, any family of sets of size w with at least about ww sets must contain a sunflower with r petals. The sunflower conjecture states that the bound on the number of sets can be improved to cw for some constant c. In work with Lovett, Wu, and Zhang, we improve the bound to approximately (log w)w. Next, we address a couple of problems about querying in graphs. We answer a question of Alon, Mossel, and Pemantle about the corruption detection model on graphs in the noisy setting. In work with He, Ben Hamida, and Moreira, we make progress on the subgraph query problem introduced by Ferber, Krivelevich, Sudakov, and Vieira. We then discuss a question related to information theory, nailing down the “product dimension” Q(s, r) of the vertex disjoint union of r cliques, each of size s. Then, in joint work with Liu and Sawhney, we study discrepancy minimization for vectors in Rn. Our main result is the analysis of a new simple random process in multiple dimensions, which we call a “self-balancing walk”, through a coupling argument. As a corollary, we obtain linear time algorithms for logarithmic bounds for the Koml ̋os conjecture. The final part of the thesis concerns a few questions in additive combinatorics. First, we solve a conjecture of Gowers from 2009 on clique di↵erences in chains, ruling out any Sperner-type proof of the polynomial density Hales-Jewett Theorem for alphabets of size 2. In particular, this rules out Gowers’ proof strategy for polynomial density Hales-Jewett. Finally, we show primitive recursive bounds for the partition regularity of {x, x + y, xy}.
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Mathematics

Files in This Item:
File Description SizeFormat 
Alweiss_princeton_0181D_14505.pdf648.86 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.