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 no(1)-dimensional polytope with at most n facets and extension complexity n1−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).
For 1 ≤ d < k and n divisible by k, let md(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 md(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+ε) md(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 md(k, n) without actually knowing its value.
A permutation is said to be k-universal or a k-superpattern if it contains every permutation of length k. A simple counting argument shows that every k-superpattern has length at least (1/e2 + o(1)) k2, 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.
It is a simple fact that if an oriented graph G has chromatic number k2, 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.
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) ≤ n1−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”.
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.
It is a classical fact that for any ε > 0, a random permutation of length n = (1/4+ε) k2 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 k-universal, meaning that it simultaneously contains every pattern of length k. He also made the simple observation that some n = O(k2 log k) suffices. In this paper we make the first asymptotic improvement to this bound: if n = 2000 k2 log log k, then a random permutation of order n is typically k-universal.
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.
Given n bases B1,...,Bn in an n-dimensional vector space V, a transversal basis is a basis of V containing exactly one element from each Bi. 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.
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 n2/3 − o(1). In this paper we prove that in any edge-ordering of the complete graph, there is a monotone path of length n1 − o(1). Our proof involves a “regularisation” lemma which may be of independent interest.
Consider a quadratic polynomial f(ξ1,...,ξn) of independent Bernoulli random variables. What can be said about the concentration of 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.
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 show that for any fixed t, every Kt-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.
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 such a result: for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of Θ(n2) different sizes. This resolves a conjecture of Narayanan, Sahasrabudhe and Tomon, motivated by an old problem of Erdős and McKay.
An r-cut of a 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-r-cut of 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.
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.
Consider integers k, l such that 0 ≤ l ≤ (k choose ). 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 ), 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.
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.
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/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.
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.
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. The primary tools in our proofs are the so-called “switching” method and permanent estimates.
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 ξ can 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.
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 unusual application 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.