Main content start

Combinatorics

Organizer: jacobfox [at] stanford.edu (Jacob Fox)

 

Past Events

May
30
Date3:00 PM
Location
384H
Speaker
Xiaoyu He (Princeton)

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…

May
23
Date3:00 PM
Location
384H
Speaker
Dmitrii Zakharov (MIT)

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…

May
09
Date3:00 PM
Location
384H
Speaker
Hung-Hsun Hans Yu (Princeton)

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, …

Apr
11
Date3:00 PM
Location
384H
Speaker
Vishesh Jain (University of Illinois Chicago)

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…

Mar
21
Date3:00 PM
Location
384H
Speaker
Jacques Verstraete (University of California, San Diego)

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…

Feb
29
Date3:00 PM
Location
384H
Speaker
Dingding Dong (Harvard)

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…

Feb
08
Date3:00 PM
Location
384H
Speaker
Matthew Kwan (IST Austria)

Consider a quadratic polynomial Q(x_1,...,x_n) of a random binary sequence (x_1,...,x_n). To what extent can Q(x_1,...,x_n) concentrate on a single value? This is a quadratic version of the classical Littlewood-Offord problem; it was was popularised by Costello, Tao and Vu in their study of…

Feb
01
Date3:00 PM
Location
384H
Speaker
David Conlon (Caltech)

We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions. The basic question we discuss is the following: given a subset A of d-dimensional space and a linear transformation L, how large is the sumset A + LA?

Jan
25
Date3:00 PM
Location
384H
Speaker
Matija Bucic (Princeton)

Expander graphs are perhaps one of the most widely useful classes of graphs ever considered. In this talk, we will focus on a fairly weak notion of expanders called sublinear expanders, first introduced by Komlós and Szemerédi around 30 years ago. They have found…

Nov
09
Date3:00 PM
Location
384H
Speaker
Persi Diaconis (Stanford)

Let w(1),w(2),..., w(n) be positive weights. Put these weights in an urn and draw them out, without replacement, each time picking the next draw with probability proportional to its weight relative to the remaining weights. Let sigma be the resulting permutation of {1,2,...,n}. This model is…