Challenges and Results in Extremal Combinatorics

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}.