There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this situation is provided by a classical theorem of Babai, Erdős and Selkow, who showed that the simplest possible refinement-based algorithm is very effective on random graphs: for a uniformly random graph G on n vertices, naïve refinement provides a canonical labelling scheme which can be used to distinguish G from all other graphs (with probability tending to 1 as n tends to infinity).
We extend the Babai–Erdős–Selkow theorem to sparse random graphs (of any density), improving previous results of Bollobás, Czajka–Pandurangan and Linial–Moshieff. We also extend it to the smoothed analysis framework of Spielman and Teng, improving previous results of Gaudio–Rácz–Sridhar. In particular, one of our results is that for any n-vertex graph G, if we perturb G by adding and removing about n random edges, then refinement-based canonical labelling schemes typically become very efficient.
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 an n-vertex k-uniform hypergraph. Generalising a result of Cuckler and Kahn to the hypergraph setting, we prove that if an n-vertex k-uniform hypergraph G has minimum d-degree at least (1+ε) md(k, n) (for any constant ε ≥ 0), then the number of perfect matchings in G is controlled by an entropy-like parameter of G.
Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state |ψ⟩. Using local quantum operations on their respective subsystems, and classical communication, Alice and Bob may be able to transform |ψ⟩ into another state |φ⟩. In this paper we prove a conjecture of Nielsen, that in the limit of large dimensionality, for almost all pairs of states |ψ⟩, |φ⟩ (according to the natural unitary invariant measure) such a transformation is not possible. That is to say, typical pairs of quantum states are entangled in fundamentally different ways, that cannot be locally converted to each other. This turns out to be equivalent to a statement about majorisation of spectra of certain random matrices.
In this paper we prove a central limit theorem for the matching number of a sparse random graph, as conjectured by Aronson, Frieze and Pittel. This had recently been proved in the so-called supercritical regime (according to an algorithmic phase transition first observed by Karp and Sipser), using a stochastic generalisation of the differential equations method; we build on these methods and introduce new ideas to handle certain degeneracies present in the subcritical and critical regimes.
Here is a Mathematica notebook (PDF printout) for some of the more tedious calculations in the paper.
Consider a quadratic polynomial Q(ξ1,...,ξn) of independent Rademacher random variables. The quadratic Littlewood–Offord problem asks: to what extent can Q(ξ1,...,ξn) concentrate on a single value? In this paper, we obtain an essentially optimal bound for this problem, as conjectured by Nguyen and Vu. Specifically, if there is no way to pin down the value of Q(ξ1,...,ξn) by fixing values for fewer than m of the variables ξi, then we have Pr[Q(ξ1,...,ξn) = 0] ≤ O(m−1/2). A key ingredient in our proof is a new inductive decoupling scheme that reduces quadratic anticoncentration problems to high-dimensional linear anticoncentration problems.
Very sparse random graphs (and random bipartite graphs) are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of “low-degree dependencies” such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. In this paper we give a combinatorial description of the rank of a sparse random graph 𝔾(n, c/n) or 𝔾(n, n, c/n), in terms of such local dependencies, for all constants c ≠ e (and we present some evidence that the situation is very different for c = e). This gives an essentially complete answer to a question of Vu, and has a number of applications including a central limit theorem for the rank of a sparse random graph.
An ordered r-matching is an r-uniform hypergraph matching equipped with an ordering on its vertices. The theory of ordered 2-matchings is well-developed, but in the case r ≥ 3 much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings; in this paper we substantially improve several of their results and introduce some new directions of study.
There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of v have the same colour as v. As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every d, all but finitely many d-regular graphs have a partition into two nonempty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős–Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of “exceptional vertices”. Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes.
This paper is a collaboration with a team of cryptographers. We were able to use techniques from extremal combinatorics to study the efficiency of key-sharing schemes (which are used for secure communication between members of a group). I was only really involved in the combinatorics part!
Recall the classical “15 puzzle”, consisting of 15 sliding blocks in a 4×4 grid. The configuration space of this puzzle consists of two connected components, corresponding to the odd and even permutations of the symmetric group S15. Generalising results of Wilson, we study the connectedness of the configuration space of a puzzle consisting of an arbitrary number of sliding blocks on an arbitrary graph.
For any constant g, we show that for sufficiently large n congruent to 1 or 3 (mod 6) there is an order-n Steiner triple system with girth at least g. This resolves an old conjecture of Erdős.
The inertia bound is a powerful inequality in spectral graph theory, stating that for any graph G, and any weighted adjacency matrix A of G, the independence number of G is at most the number of non-negative eigenvalues of A. In general, it is a highly non-trivial matter to identify the best weighted adjacency matrix with which to apply this bound, and the limits of the inertia bound are therefore rather unclear. In fact, only recently Sinkovic found the first example of a graph for which the inertia bound is not tight. In this paper we obtain some new results showing that the inertia bound can be extremely far from tight.
As a discrete analogue of Kac's celebrated question on “hearing the shape of a drum”, and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers, is that “almost all graphs are determined by their spectrum”, meaning that the fraction of unlabelled n-vertex graphs which are determined by their spectrum converges to 1 as n → ∞. In this paper we make a step towards this conjecture, showing that there are exponentially many n-vertex graphs which are determined by their spectrum.
We prove several theorems about substructures in Latin squares. First, we prove the first nontrivial lower bound on the number of the number of n×n Latin squares which have no intercalates (2×2 Latin subsquares). We also prove an essentially best-possible bound on the upper tail for intercalates in random Latin squares. Then, we prove a conjecture of Linial on the existence of Latin squares with high girth. Finally, we study the number of cuboctahedra in a random Latin square (this is a measure of “how associative” the quasigroup associated with the Latin square is).
An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n (i.e., if it has near-optimal Ramsey behavior). In this paper we study edge-statistics in Ramsey graphs, obtaining very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay. The proof proceeds via an “additive structure” dichotomy, and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation.
Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of “low-degree dependencies” such as isolated vertices and pairs of degree-1 vertices with the same neighbour. We prove that these kinds of dependencies are in some sense the only causes of singularity: for any fixed k ≥ 3 and c > 0, a random graph with n vertices and edge probability c/n typically has the property that its k-core (its maximal subgraph with minimum degree at least k) is nonsingular. This resolves a conjecture of Vu, and adds to a very short list of nonsingularity theorems for “extremely sparse” random matrices with density O(1/n). Note: a previous version of this paper included a remark that our proof also yields a hitting-time result. We since discovered that modifying our proof to this setting is not as trivial as we thought, and this should still be viewed as an open problem.
The Littlewood–Offord problem is concerned with upper bounds on probabilities of events of the form a1ξ1+...+anξn = x, where (ξ1,...,ξn) is a random ±1 sequence and a1,...,an,x ∈ ℝd are vectors. In this paper we consider some geometric variants of the Littlewood–Offord problem. In particular, we are able to obtain near-optimal bounds on probabilities of events of the form a1ξ1+...+anξn ∈ S, when S ⊆ ℝd is definable with respect to an o-minimal structure.
We show that the number of linear spaces on a set of n points and the number of rank-3 matroids on a ground set of size n are both of the form (cn+o(n))n2/6, for an explicit constant c ≈ 0.162. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: the numbers of rank-1 and rank-2 matroids on a ground set of size n have exact representations in terms of well-known combinatorial functions, and it was recently proved by van der Hofstad, Pendavingh and van der Pol that for constant r ≥ 4 there are (e1−rn+o(n))nr−1/r! rank-r matroids on a ground set of size n.
Resolving an old conjecture of Füredi, we prove that, for n even, almost every n-vertex graph admits a partition of its vertex set into two parts of equal size in which almost all vertices have more neighbours on their own side than across. The proof relies on new methods to study stochastic processes driven by degree information in random graphs; in particular, we combine enumeration techniques with an abstract second moment argument.
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 an n-vertex 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.
In this note, we study large deviations of the number of intercalates (2×2 Latin subsquares) in a random n×n Latin square. We obtain near-optimal tail bounds, and as a consequence prove that a typical n×n Latin square has (1+o(1))n2/4 intercalates, resolving an old conjecture of McKay and Wanless.
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).
We prove that there exist Reed–Solomon codes which are list-decodable with radius 1 − ε and have rate Ω(ε) (which is the best possible for any code, by the list decoding capacity theorem). This improves a result of Guo, Li, Shangguan, Tamo and Wootters, and resolves the motivating question of their work.
Resolving a conjecture of Vu, we prove that the permanent of a uniformly random symmetric n×n matrix with ±1 entries typically has magnitude nn/2 + o(n). Our result can be extended to very general models of symmetric random matrices.
Consider a random n×n zero-one matrix with “density” p, sampled according to one of the following two models: either every entry is independently set to one with probability p (the “Bernoulli” model), or each row is independently uniformly sampled from the set of all length-n zero-one vectors with exactly pn ones (the “combinatorial” model). We give simple proofs of the (essentially best-possible) fact that in both cases, if min(p,1 − p) ≥ (1+ε) log n / n for any constant ε > 0, then our random matrix is nonsingular with probability 1 − o(1). In the Bernoulli case this fact was already well-known, but in the combinatorial case this resolves a conjecture of Aigner-Horev and Person.
We prove several different anti-concentration inequalities for functions of independent Bernoulli-distributed random variables. First, 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.
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.
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”.
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.
We show that for any n congruent to 3 (mod 6), 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.
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.
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.
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. See also the companion note with Ashwin Sah and Mehtaab Sawhney, where we record and prove some analogues of the lemmas in this paper for random Latin squares.
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. Note: a minor oversight in the definition of “(δ,ε)-richness” has been corrected since publication of this paper. The corrected version can be found here or on the arXiv.
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. Note: a minor oversight in the definition of “(δ,ε)-richness” has been corrected since publication of this paper. The corrected version can be found here or on the arXiv.
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.
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.
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.