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.
This semester I'm teaching Graph Theory. Here's the course homepage. I don't have fixed office hours, but please feel free to email me to schedule an appointment if you'd like help with the course.
Frieze showed that a random directed graph with m = n log n + ω(n) edges typically has a directed Hamilton cycle (this is best possible). Using Frieze's machinery, permanent estimates, and some elementary facts about random permutations, we give a short proof of the fact that such random digraphs in fact typically have n! (m/n2 (1+o(1)))n Hamilton cycles, improving previous results that held only for denser random digraphs. We also prove a hitting time version of our theorem.
We study the k-matching-free process, where one starts with the empty n-vertex graph and adds edges one-by-one, each chosen uniformly at random subject to the constraint that no k-matching is created (for some k potentially depending on n). This appears to be the first analysis of an H-free process for non-fixed H. In our main theorems, we identify the range of k for which the process results in an extremal k-matching-free graph, as characterised by Erdős and Gallai. One of the proofs involves some interesting coupling arguments for tracking the formation of augmenting paths.
The classical Erdős-Ko-Rado theorem gives the maximum size of a k-uniform intersecting family, and the Hilton-Milner theorem gives the maximum size of such a family that is not trivially intersecting (this means that there is no element x which appears in each set of the family). Frankl introduced and solved a certain natural “multi-part” generalization of the Erdős-Ko-Rado problem; in this paper we study the corresponding question for non-trivially intersecting families. We solve this problem asymptotically, disproving a conjecture of Alon and Katona and obtaining a stability theorem for a problem of Greenwell and Lovász.
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.
An intercalate in a Latin square is a 2×2 Latin subsquare. We show that a random n×n Latin square typically has about n2 intercalates, significantly improving the previous best lower and upper bounds. In addition, we show that in a certain natural sense a random Latin square has relatively low discrepancy, which relates to a question of Linial and Luria. The primary tools in our proofs are the so-called “switching” method and permanent estimates.
We find the asymptotic expected number of spanning trees in a random graph conditioned on a fixed "sparse" degree sequence. In particular this gives the expected number of spanning trees in a random d-regular graph on n vertices, where d can grow modestly with n. An interesting part of the proof is a concentration result proved using a martingale based on the Prüfer code algorithm.
We show that randomly changing linearly many edges in a dense graph is typically enough to ensure the existence of a copy of any given bounded-degree spanning tree. The proof uses the so-called regularity method.
In many situations, “typical” structures have certain properties, but there are worst-case extremal examples which do not. In these situations one can often show that the extremal examples are “fragile” in that after a modest random perturbation our desired property will typically appear. We prove several results of this flavour, concerning perfect matchings and Hamilton cycles in digraphs and hypergraphs. The proof of one of our results involves an interesting use of Szemerédi's regularity lemma to “beat the union bound”, which may be of independent interest.
We study the number of spanning trees τ(G) in a uniformly random d-regular graph G on n vertices (for fixed d and large n). We find the asymptotic expected value of τ(G), and we find the limiting distribution of τ(G) for d = 3. The proof uses the method of small subgraph conditioning: we estimate Y via its expectation conditioned on the short cycle counts. The estimates are rather more difficult than usual, and involve complex-analytic methods.