Combinatorics
Organizer: jacobfox [at] stanford.edu (Jacob Fox)
Upcoming Events
A 1971 conjecture of Graham (later repeated by Erdős and Graham) asserts that every set A of nonzero residues modulo p has an ordering whose partial sums are all distinct. We prove this conjecture for sets A of up to quasipolynomial size; our result improves the previous bound of log p/loglog p…
Past Events
Define an equivalence relation on the symmetric group S_n by declaring two permutations equivalent if their weak excedances occur in the same positions and share the same values, up to reordering. This talk explores the resulting “excedance equivalence classes” of S_n: their number, the size of…
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…