We consider the complete graph 𝜅n on n vertices with exponential mean n edge lengths. Writing Cij for the weight of the smallest-weight path between vertices i, j ∈ [n], Janson [18] showed that maxi,j∈[n]Cij/logn converges in probability to 3. We extend these results by showing that maxi,j∈[n]Cij − 3 logn converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centred graph diameter of the barely supercritical Erdős–Rényi random graph in [22].

Consider the complete graph on n vertices, with edge weights drawn independently from the exponential distribution with unit mean. Janson showed that the typical distance between two vertices scales as log n/n, whereas the diameter (maximum distance between any two vertices) scales as 3 log n/n. Bollobás, Gamarnik, Riordan and Sudakov showed that, for any fixed k, the weight of the Steiner tree connecting k typical vertices scales as (k − 1)log n/n, which recovers Janson's result for k = 2. We extend this to show that the worst case k-Steiner tree, over all choices of k vertices, has weight scaling as (2k − 1)log n/n and finally, we generalize this result to Steiner trees with a mixture of typical and worst case vertices.

A subset C of edges in a k-uniform hypergraph H is a loose Hamilton cycle if C covers all the vertices of H and there exists a cyclic ordering of these vertices such that the edges in C are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random k-uniform hypergraph Hkn,p has vertex set [n] and an edge set E obtained by adding each k-tuple e ∈ ($\binom{[n]}{k}$) to E with probability p, independently at random.

Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but o(|E|) edges, referred to as the packing problem. While it is known that the threshold probability of the appearance of a loose Hamilton cycle in Hkn,p is

$p=\Theta\biggl(\frac{\log n}{n^{k-1}}\biggr),$

$N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$

Our proof utilizes and modifies the idea of ‘online sprinkling’ recently introduced by Vu and the first author.

We almost completely solve a number of problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number k, the smallest number m = m(k) such that every digraph can be coloured with m colours where each vertex has the same colour as at most a 1/k proportion of its out-neighbours. We show that m(k) ∈ {2k − 1,2k}. We also prove a result supporting the conjecture that m(2) = 3. Moreover, we prove similar results for a more general concept called majority choosability.

Given hypergraphs F and H, an F-factor in H is a set of vertex-disjoint copies of F which cover all the vertices in H. Let K−4 denote the 3-uniform hypergraph with four vertices and three edges. We show that for sufficiently large n ∈ 4ℕ, every 3-uniform hypergraph H on n vertices with minimum codegree at least n/2−1 contains a K−4-factor. Our bound on the minimum codegree here is best possible. It resolves a conjecture of Lo and Markström [15] for large hypergraphs, who earlier proved an asymptotically exact version of this result. Our proof makes use of the absorbing method as well as a result of Keevash and Mycroft [11] concerning almost perfect matchings in hypergraphs.

The (a,b)-eye is the graph Ia,b = Ka+b \ Kb obtained by deleting the edges of a clique of size b from a clique of size a+b. We show that for any a,b ≥ 2 and p ∈ (0,1), if we condition the random graph G ~ G(n,p) on having no induced copy of Ia,b, then with high probability G is close to an a-partite graph or the complement of a (b−1)-partite graph. Our proof uses the recently developed theory of hypergraph containers, and a stability result for an extremal problem with two weighted colours. We also apply the stability method to obtain an exact Turán-type result for this extremal problem.

We give a minimum degree condition sufficient to ensure the existence of a fractional Kr-decomposition in a balanced r-partite graph (subject to some further simple necessary conditions). This generalizes the non-partite problem studied recently by Barber, Lo, Kühn, Osthus and the author, and the 3-partite fractional K3-decomposition problem studied recently by Bowditch and Dukes. Combining our result with recent work by Barber, Kühn, Lo, Osthus and Taylor, this gives a minimum degree condition sufficient to ensure the existence of a (non-fractional) Kr-decomposition in a balanced r-partite graph (subject to the same simple necessary conditions).

Let G be a finite D-quasirandom group and A ⊂ Gk a δ-dense subset. Then the density of the set of side lengths g of corners

$$ \{(a_{1},\dotsc,a_{k}),(ga_{1},a_{2},\dotsc,a_{k}),\dotsc,(ga_{1},\dotsc,ga_{k})\} \subset A $$

Due to a calculation error, the constant in the main theorem is not $80 \sqrt{k\log k}$ but $80\sqrt{k} \log k$. The error was discovered by Xizhi Liu.

For a new discussion on the limit of the method used in this paper see the revised arXiv version of the paper.

In my paper [1], a normalization factor of |G|−1 was missing in the statements of Theorem 2.4, Theorem 2.6 and Corollary 2.7.