Combinatorics

We will begin by briefly introducing the use of higher-order Fourier analysis in additive combinatorics for a general audience. In particular, we will discuss the arithmetic regularity lemma and how it identifies a certain class of arithmetically-structured functions -- nilsequences -- as…

Semialgebraic graphs are a convenient way to encode many problems in discrete geometry. These include the Erdős unit distance problem and many of its variants, the point-line incidence problems studied by Szemerédi–Trotter and by Guth–Katz, more general problems about incidences of…

Given two vertex-ordered graphs G and H, the ordered Ramsey number R_<(G,H) is the smallest N such that whenever the edges of a vertex-ordered complete graph K_N are red/blue-colored, then there is a red (ordered) copy of G or a blue (ordered) copy of H. Let P_n^t denote the t-th power of a…

Look at a typical partition of N (uniform distribution). What does it 'look like'? How many singletons, parts of size k, how big is the largest part? AND how can we generate such a random partition, say when N = 10^6, to check theory against 'reality'    Of course, there are many…

Let S be a subset of the Boolean hypercube {0,1}^n that is both an antichain and a distance-r code. How large can S be? I will discuss the solution to this problem and its connections with combinatorial proofs of results in Littlewood-Offord theory. 

Based on joint work with…

Consider the incidence graph between the points of the unit square and the set of δ x 1 tubes for some δ > 0. What is the size n = n(δ) of the largest induced matching in this graph? We use ideas from projection theory to study this problem and show a non-trivial upper bound on n(δ). As a…

The joints problem asks to determine the maximum number of joints N lines can form, where a joint in a d-dimensional space is a point on d lines in linearly independent directions. Recently, Ting-Wei Chao and I determined the maximum exactly for k choose d-1 lines in d-dimensional space, …

Given a set system S_1,...,S_n over the ground set [n], the minimum discrepancy problem seeks to find a 2-coloring of the elements of the ground set so that the discrepancy i.e. the maximum (over S_1,..., S_n) imbalance of colors in a set is minimized. In a breakthrough work, Bansal provided a…

The Ramsey number r(s,t) denotes the minimum N such that in any red-blue coloring of the edges of the complete graph on N vertices, there exists a red complete graph on s vertices or a blue complete graph on t vertices. While the study of these quantities goes back almost one hundred…

A system of linear equations is Sidorenko over F_p if any subset of F_p^n contains at least as many solutions to it as a random set of the same density, asymptotically as n->infty. A system of linear equations is common over F_p if any 2-coloring of F_p^n gives at least as many monochromatic…