- Extension complexity of low-dimensional polytopes (with Lisa Sauermann and Yufei Zhao). Submitted.
Sometimes, it is possible to represent a complicated polytope as a “shadow” of a much simpler polytope. To quantify this phenomenon, the

*extension complexity*of a polytope*P*is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which*P*can be obtained as a linear projection. It is an important question to understand the extent to which the extension complexity of a polytope is controlled by its dimension, and in this paper we prove three different results along these lines. First, we show that there exists an*n*^{o(1)}-dimensional polytope with at most*n*facets and extension complexity*n*^{1−o(1)}. Second, we obtain optimal bounds for the extension complexity of*random**d*-polytopes, and third, we obtain an optimal upper bound for the extension complexity of*cyclic*polygons (all of whose vertices lie on a common circle). - Dirac-type theorems in random hypergraphs (with Asaf Ferber). Submitted.
For 1 ≤

*d*<*k*and*n*divisible by*k*, let*m*_{d}(*k*,*n*) be the minimum*d*-degree ensuring the existence of a perfect matching in a*k*-uniform hypergraph. In general, our understanding of the values of*m*_{d}(*k*,*n*) is very limited, and it is an active topic of research to determine or approximate these values. In this paper we prove a “transference” theorem for random hypergraphs. Specifically, for any 1 ≤*d*<*k*, any*ε*> 0 and any “not too small”*p*, we prove that a random*k*-uniform hypergraph*G*with*n*vertices and edge probability*p*typically has the property that every spanning subgraph of*G*with minimum degree at least (1+*ε*)*m*_{d}(*k*,*n*)*p*has a perfect matching. One interesting aspect of our proof is a “non-constructive” application of the absorbing method, which allows us to prove a bound in terms of*m*_{d}(*k*,*n*) without actually knowing its value. - Lower bounds for superpatterns and universal sequences (with Zachary Chroman and Mihir Singhal). Submitted.
A permutation is said to be

or a*k*-universalif it contains every permutation of length*k*-superpattern*k*. A simple counting argument shows that every*k*-superpattern has length at least (1/*e*^{2}+*o*(1))*k*^{2}, and Arratia conjectured that this lower bound is best-possible. Disproving Arratia's conjecture, we improve this trivial bound by a small constant factor. We accomplish this by designing an efficient encoding scheme for the patterns that appear in a permutation. This approach is quite flexible and is applicable to other universality-type problems; for example, we also improve a bound by Engen and Vatter on a problem concerning (*k*+1)-ary sequences which contain all*k*-permutations. - Acyclic subgraphs of tournaments with high chromatic number (with Jacob Fox and Benny Sudakov). Submitted.
It is a simple fact that if an oriented graph

*G*has chromatic number*k*^{2}, then it has an acylic subgraph with chromatic number at least*k*, and it was recently observed that improvements to this bound would imply new bounds for an old conjecture of Burr. In this paper we consider the special case where*G*is a tournament, and improve some previous bounds by Nassar and Yuster, resolving one of their conjectures. Along the way, we prove a lemma showing that tournaments with many transitive subtournaments have a large almost-transitive subtournament; this may be of independent interest. - Anticoncentration for subgraph counts in random graphs (with Jacob Fox and Lisa Sauermann). Submitted.
Fix a graph

*H*and some 0 <*p*< 1, and let*X*be the number of copies of*H*in a random graph*G*(*n*,*p*). In this paper we study the*anticoncentration*behaviour of*X*: how likely can it be that*X*falls in some small interval or is equal to some particular value? We prove the almost-optimal result that if*H*is connected then for any integer*x*we have Pr(*X*=*x*) ≤*n*^{1−v(H)+o(1)}. Our proof proceeds by iteratively breaking*X*into different components which fluctuate at “different scales”, and relies on a new anticoncentration inequality for random vectors that behave “almost linearly”. - Almost all Steiner triple systems are almost resolvable (with Asaf Ferber).
*Forum of Mathematics, Sigma*, to appear.We show that for any

*n*divisible by 3, almost all order-*n*Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings. That is, almost all Steiner triple systems are almost*resolvable*. - Universality of random permutations (with Xiaoyu He).
*Bulletin of the London Mathematical Society*, to appear.It is a classical fact that for any

*ε*> 0, a random permutation of length*n*= (1/4+*ε*)*k*^{2}typically contains an increasing subsequence of length*k*. As a far-reaching generalisation, Alon conjectured that a random permutation of this same length*n*is typically, meaning that it simultaneously contains every pattern of length*k*-universal*k*. He also made the simple observation that some*n*=*O*(*k*^{2}log*k*) suffices. In this paper we make the first asymptotic improvement to this bound: if*n*= 2000*k*^{2}log log*k*, then a random permutation of order*n*is typically*k*-universal. - Combinatorial anti-concentration inequalities, with applications (with Jacob Fox and Lisa Sauermann).
*Mathematical Proceedings of the Cambridge Philosophical Society*, to appear.We prove several different anti-concentration inequalities for functions of independent Bernoulli-distributed random variables. First, motivated by a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, we prove some “Poisson-type” anti-concentration theorems that give bounds of the form 1/

*e*+*o*(1) for the point probabilities of certain polynomials. Second, we prove an anti-concentration inequality for polynomials with nonnegative coefficients which extends the classical Erdős–Littlewood–Offord theorem and improves a theorem of Meka, Nguyen and Vu for polynomials of this type. As an application, we prove some new anti-concentration bounds for subgraph counts in random graphs. - Halfway to Rota's basis conjecture (with Matija Bucic, Alexey Pokrovskiy and Benny Sudakov).
*International Mathematics Research Notices*, to appear.Given

*n*bases*B*_{1},...,*B*_{n}in an*n*-dimensional vector space*V*, a*transversal basis*is a basis of*V*containing exactly one element from each*B*_{i}. Rota's basis conjecture posits that it is always possible to find*n*disjoint transversal bases. In this paper we prove the partial result that one can always find (1/2 −*o*(1))*n*disjoint transversal bases, improving on the previous record of Ω(*n*/log*n*). Our result generalises to the setting of matroids. See also our companion note adapting our methods to the setting of a related conjecture due to Kahn. - Nearly-linear monotone paths in edge-ordered graphs (with Matija Bucic, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran and Adam Zsolt Wagner).
*Israel Journal of Mathematics*, to appear.How long a monotone path can one always find in any edge-ordering of the

*n*-vertex complete graph? This question was first asked by Chvátal and Komlós. The prevailing conjecture is that one can always find a monotone path of length Ω(*n*), but until now the best known lower bound was*n*^{2/3 − o(1)}. In this paper we prove that in any edge-ordering of the complete graph, there is a monotone path of length*n*^{1 − o(1)}. Our proof involves a “regularisation” lemma which may be of independent interest. - An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs (with Lisa Sauermann).
*Discrete Analysis*2020:12 (2020).Consider a quadratic polynomial

*f*(*ξ*_{1},...,*ξ*) of independent Bernoulli random variables. What can be said about the concentration of_{n}*f*on any single value? It is known that the point probabilities of*f*can be as large as about*n*^{−1/2}, but still poorly understood is the “inverse” question of understanding how algebraic and arithmetic features of*f*affect its point probabilities. In this paper we prove some results of an algebraic flavour, showing that if*f*has point probabilities much larger than 1/*n*then it must be close to a quadratic form with low rank. We also give an application to Ramsey graphs. - Almost all Steiner triple systems have perfect matchings.
*Proceedings of the London Mathematical Society*121.6 (2020), 1468-1495.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. - Dense induced bipartite subgraphs in triangle-free graphs (with Shoham Letzter, Benny Sudakov and Tuan Tran).
*Combinatorica*40 (2020), 283-305.We show that for any fixed

*t*, every*K*_{t}-free graph with minimum degree*d*contains an induced bipartite subgraph with minimum degree Ω(log*d*/log log*d*). This resolves some conjectures of Esperet, Kang, and Thomassé. We also obtain some further results concerning large induced bipartite subgraphs in triangle-free graphs, one of which answers a question of Erdős, Janson, Łuczak and Spencer. - Ramsey graphs induce subgraphs of quadratically many sizes (with Benny Sudakov).
*International Mathematics Research Notices*2020.6 (2020), 1621-1638.An

*n*-vertex graph is calledif it has no clique or independent set of size*C*-Ramsey*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 such a result: for any fixed*C*, every*n*-vertex*C*-Ramsey graph induces subgraphs of Θ(*n*^{2}) different sizes. This resolves a conjecture of Narayanan, Sahasrabudhe and Tomon, motivated by an old problem of Erdős and McKay. - Hypergraph cuts above the average (with David Conlon, Jacob Fox and Benny Sudakov).
*Israel Journal of Mathematics*233.1 (2019), 67-111.An

of a*r*-cut*k*-uniform hypergraph (*k*-graph)*H*is a partition of the vertex set into*r*parts, and the*size*of such a cut is the number of edges which have a vertex from every part. The*max-*of*r*-cut*H*is the maximum size of an*r*-cut of*H*. We prove some new bounds on the max-*r*-cut of a*k*-graph, for fixed*r*≤*k*, above the trivial “average” bound obtainable from a uniformly random cut. In particular, in contrast to the situation for max-cut in graphs and max-2-cut in 3-graphs, we show that if*k*≥ 4 or*r*≥ 3 then the worst-case behaviour is not governed by the standard deviation of a uniformly random cut. - Proof of a conjecture on induced subgraphs of Ramsey graphs (with Benny Sudakov).
*Transactions of the American Mathematical Society*372 (2019), 5571-5594.An

*n*-vertex graph is calledif it has no clique or independent set of size*C*-Ramsey*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 Ω(*n*^{5/2}) induced subgraphs, no pair of which have the same numbers of edges and vertices. - Anticoncentration for subgraph statistics (with Benny Sudakov and Tuan Tran).
*Journal of the London Mathematical Society*99.3 (2019), 757-777.Consider integers

*k*,*l*such that 0 ≤*l*≤ (*k*choose 2). Given a large graph*G*, what is the fraction of*k*-vertex subsets of*G*which span exactly*l*edges? When*l*is zero or (*k*choose 2), this fraction can be exactly 1. On the other hand, with Ramsey's theorem in mind, if*l*is far from these extreme values we might expect that this fraction must always be substantially smaller than 1. We prove an almost-best-possible theorem to this effect, improving on results of Alon, Hefetz, Krivelevich and Tyomkyn. We also make some first steps towards some analogous questions for hypergraphs. Our proofs take a probabilistic point of view, and involve polynomial anticoncentration inequalities, hypercontractivity, and a coupling trick for random variables defined on a “slice” of the Boolean hypercube. - The random
*k*-matching-free process (with Michael Krivelevich, Po-Shen Loh and Benny Sudakov).*Random Structures and Algorithms*53.4 (2018), 692-716.We study the

, where one starts with the empty*k*-matching-free process*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. - Counting Hamilton cycles in sparse random directed graphs (with Asaf Ferber and Benny Sudakov).
*Random Structures and Algorithms*53.4 (2018), 592-603.Frieze showed that a random directed graph with

*n*vertices and*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*/*n*^{2}(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. - Non-trivially intersecting multi-part families (with Benny Sudakov and Pedro Vieira).
*Journal of Combinatorial Theory, Series A*156 (2018), 44-60.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. - Intercalates and discrepancy in random Latin squares (with Benny Sudakov).
*Random Structures and Algorithms*52.2 (2018), 181-196.An

*intercalate*in a Latin square is a 2×2 Latin subsquare. We show that a random*n*×*n*Latin square typically has about*n*^{2}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. The primary tools in our proofs are the so-called “switching” method and permanent estimates. - Resilience for the Littlewood-Offord Problem (with Afonso Bandeira and Asaf Ferber).
*Advances in Mathematics*319 (2017), 292-312.Fix a sequence of nonzero real numbers

= (**a***a*_{1},...,*a*), consider a random ±1 sequence_{n}= (**ξ***ξ*_{1},...,*ξ*), and let_{n}*X*=*a*_{1}*ξ*_{1}+...+*a*. The Erdős–Littlewood–Offord theorem shows that, regardless of_{n}ξ_{n}, for any**a***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 ofcan we allow an adversary to change before they can force**ξ***X = x*? The answer is quite surprising, and its proof involves an interesting connection to combinatorial number theory. - The average number of spanning trees in sparse graphs with given degrees (with Catherine Greenhill, Mikhail Isaev and Brendan McKay).
*European Journal of Combinatorics*63 (2017), 6-25.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. - Bounded-degree spanning trees in randomly perturbed graphs (with Michael Krivelevich and Benny Sudakov).
*SIAM Journal on Discrete Mathematics*31 (2017), 155-171.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.

- Cycles and matchings in randomly perturbed digraphs and hypergraphs (with Michael Krivelevich and Benny Sudakov).
*Combinatorics, Probability and Computing*25 (2016), 909-927.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 unusual application of Szemerédi's regularity lemma to “beat the union bound”, which may be of independent interest.

- On the number of spanning trees in random regular graphs (with Catherine Greenhill and David Wind).
*Electronic Journal of Combinatorics*21:P1.45 (2014).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.