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 integers k, ℓ such that 0 ≤ ℓ ≤ (k choose ). Given a large graph G, what is the fraction of k-vertex subsets of G which span exactly ℓ edges? When ℓ is zero or (k choose ), this fraction can be exactly 1. On the other hand, with Ramsey's theorem in mind, if ℓ 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.
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. 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 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 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.
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.
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 ξ 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.
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.