Combinatorics
Organizer: jacobfox [at] stanford.edu (Jacob Fox)
Past Events
In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as the connection between vertex and spectral…
A graph is said to be a (1-dimensional) expander if the second eigenvalue of its adjacency matrix is bounded away from 1, or almost-equivalently, if it has no sparse vertex cuts. There are several natural ways to generalize the notion of expansion to hypergraphs/simplicial complexes…
In this talk, we strengthen a result by Ben Green on an analogue of Sárközy’s theorem in the setting of polynomial rings F_q[…
In a basic online selection problem, we observe a sequence of numbers one-by-one, and we have to make an irrevocable decision to select one of the numbers. Two classical problems of this type are the secretary problem and the prophet problem. They differ along a few dimensions: the order…
The Erdös-Ginzburg-Ziv Problem is a classical extremal problem in discrete geometry. Given positive integers m and n, the problem asks about the smallest number s such…
In joint work with Kannan Soundararajan, we consider the behavior of random multiplicative functions when summed over subsets of the integers in [1, N], and give several examples of sets where such sums satisfy a central limit theorem. In contrast, as we know from…
I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi’s theorem and describe a proof of such bounds for sets lacking nontrivial configurations of the form (x,y), (x,y+z), (x,y+2z…
The Sylow theorems appear at the very start of group theory. If you look (and we will) you'll see that the proofs are 'just simple combinatorics'. This connection continues. In this talk I'll focus on the Sylow subgroups of the Symmetric group S_n. These have a simple description as 'chandelier…
Let A be drawn uniformly at random from the set of all n x n symmetric matrices with entries in {-1,1}. What is the probability that A is singular? This is a classical problem at the intersection of probability and combinatorics. I will give an…