Since September 2014, I'm a doctoral student in mathematics at ETH Zurich under the guidance of Benny Sudakov. Before coming to ETH, my undergraduate studies were at UNSW (Sydney), where my adviser was Catherine Greenhill.
An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. All known constructions of Ramsey graphs involve randomness in an essential way, and there is a line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. In this paper we prove an old conjecture of Erdős, Faudree and Sós that in any n-vertex C-Ramsey graph, there are Ω(n5/2) induced subgraphs, no pair of which have the same numbers of edges and vertices. This improves on earlier results due to Alon, Balogh, Kostochka and Samotij.
We show that for any n divisible by 3, almost all order-n Steiner triple systems have a perfect matching (also known as a parallel class). In fact, we prove a general upper bound on the number of perfect matchings in a Steiner triple system and show that almost all Steiner triple systems essentially attain this maximum. We accomplish this via a general theorem comparing a uniformly random Steiner triple system to the outcome of the triangle removal process, which we hope will be useful for other problems. We believe our methods can be adapted to other types of designs, for example to show that almost all Latin squares have transversals.
Fix a sequence of nonzero real numbers a = (a1,...,an), consider a random ±1 sequence ξ = (ξ1,...,ξn), and let X = a1ξ1+...+anξn. The Erdős-Littlewood-Offord theorem shows that, regardless of a, for any x the event X = x is unlikely (that is, X is anti-concentrated). In this paper, motivated by some questions about random matrices, we study the “resilience” of this anti-concentration. For a given x, how many coordinates of ξ is an adversary typically allowed to change without making X = x? The answer is quite surprising, and its proof involves an interesting connection to combinatorial number theory.