Let c [les ] 0.076122 and T1, T2,…, Tn be a sequence of trees such that [mid ]V(Ti)[mid ] [les ] i−c(i−1). We prove that, if for each 1 [les ] i [les ] n there exists a vertex xi ∈ V(Ti) such that Ti−xi has at least (1−2c)(i−1) isolated vertices, then T1,…, Tn can be packed into Kn. We also prove that if T is a tree of order n+1−c′n, c′ [les ] 1/25 (37−8 √21 ) ≈ 0.0135748, such that there exists a vertex x ∈ V(T) and T−x has at least n(1−2c′) isolated vertices, then 2n+1 copies of T may be packed into K2n+1.

In 1978, Bollobás and Eldridge [5] made the following two conjectures.

1. (C1) There exists an absolute constant $c>0$ such that, if k is a positive integer and $G_1$ and $G_2$ are graphs of order n such that $\Delta(G_1),\Delta(G_2)\leq n-k$ and $e(G_1),e(G_2)\leq ck n$, then the graphs $G_1$ and $G_2$ pack.

2. (C2) For all $0<\alpha<1/2$ and $0<c<\sqrt{1/8}$, there exists an $n_0=n_0(\alpha,c)$ such that, if $G_1$ and $G_2$ are graphs of order $n>n_0$ satisfying $e(G_1)\leq \alpha n$ and $e(G_2)\leq c\sqrt{n^3/ \alpha}$, then the graphs $G_1$ and $G_2$ pack.

We give an example of a long range Bernoulli percolation process on a group non-quasi-isometric with ℤ, in which clusters are almost surely finite for all values of the parameter. This random graph admits diverse equivalent definitions, and we study their ramifications. We also study its expected size and point out certain phase transitions.

Consider first-passage percolation on the square lattice. Welsh, who together with Hammersley introduced the subject in 1963, has formulated a problem about mean first-passage times, which, although seemingly simple, has not been proved in any non-trivial case. In this paper we give a general proof of Welsh's problem.

We investigate the following problem of Erdős:

Determine the minimum number of k-cliques in a graph of order n with independence number [ges ] l.

We disprove the original conjecture of Erdős which was stated in 1962 for all but a finite number of pairs k, l, and give asymptotic estimates for l = 3, k [ges ] 4, and l = 4, k [ges ] 4.

The maximum expected length of an increasing subsequence which can be selected by a non-anticipating policy from a random permutation of 1, …, n is known to be asymptotic to √2n. We give a new proof of this fact and demonstrate a policy which achieves this value.

In a 1976 paper published in Science, Knuth presented an algorithm to sample (non-uniform) self-avoiding walks crossing a square of side k. From this sample, he constructed an estimator for the number of such walks. The quality of this estimator is directly related to the (relative) variance of a certain random variable Xk. From his experiments, Knuth suspected that this variance was extremely large (so that the estimator would not be very efficient). But how large? For the analogous Rosenbluth algorithm, which samples unconfined self-avoiding walks of length n, the variance of the corresponding estimator is believed to be exponential in n.

A few years ago, Bassetti and Diaconis showed that, for a sampler à la Knuth that generates walks crossing a k × k square and consisting of North and East steps, the relative variance is only $O(\sqrt k)$. In this note we take one step further and show that, for walks consisting of North, South and East steps, the relative variance jumps to $2^{k(k+1)}/(k+1)^{2k}$. This is exponential in the average length of the walks, which is of order k2. We also obtain partial results for general self-avoiding walks crossing a square, suggesting that the relative variance could be exponential in k2 (which is again the average length of these walks).

Knuth's algorithm is a basic example of a widely used technique called sequential importance sampling. The present paper, following the paper by Bassetti and Diaconis, is one of very few examples where the variance of the estimator can be found.

The d-dimensional Hamming torus is the graph whose vertices are all of the integer points inside an a1n × a2n × ⋅⋅⋅ × adn box in $\mathbb{R}^d$ (for constants a1, . . ., ad > 0), and whose edges connect all vertices within Hamming distance one. We study the size of the largest connected component of the subgraph generated by independently removing each vertex of the Hamming torus with probability 1 − p. We show that if p = λ/n, then there exists λc > 0, which is the positive root of a degree d polynomial whose coefficients depend on a1, . . ., ad, such that for λ < λc the largest component has O(log n) vertices (w.h.p. as n → ∞), and for λ > λc the largest component has $(1-q) \lambda \bigl(\prod_i a_i \bigr) n^{d-1} + o (n^{d-1})$ vertices and the second largest component has O(log n) vertices w.h.p. An implicit formula for q < 1 is also given. The value of λc that we find is distinct from the critical value for the emergence of a giant component in bond percolation on the Hamming torus.

We obtain a polynomial upper bound on the mixing time $T_{CHR}(\epsilon)$ of the coordinate Hit-and-Run (CHR) random walk on an $n-$ dimensional convex body, where $T_{CHR}(\epsilon)$ is the number of steps needed to reach within $\epsilon$ of the uniform distribution with respect to the total variation distance, starting from a warm start (i.e., a distribution which has a density with respect to the uniform distribution on the convex body that is bounded above by a constant). Our upper bound is polynomial in n, R and $\frac{1}{\epsilon}$ , where we assume that the convex body contains the unit $\Vert\cdot\Vert_\infty$ -unit ball $B_\infty$ and is contained in its R-dilation $R\cdot B_\infty$ . Whether CHR has a polynomial mixing time has been an open question.

Let $\{D_M\}_{M\geq 0}$ be the n-vertex random directed graph process, where $D_0$ is the empty directed graph on n vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $$\varepsilon > 0$$ , we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $1/2-\varepsilon$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\varepsilon)$ -resiliently Hamiltonian. Furthermore, for each $\varepsilon > 0$ , we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\varepsilon)$ -resiliently Hamiltonian.

This improves a result of Ferber, Nenadov, Noever, Peter and Škorić who showed, for each $\varepsilon > 0$ , that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\varepsilon)$ -resiliently Hamiltonian if $p=\omega(\log^8n/n)$ .

Let TBin(N, n, q) be the game on the complete graph KN in which two players, the Breaker and the Maker, alternately claim one and q edges, respectively. The Maker's aim is to build a binary tree on n<N vertices in n−1 turns while the Breaker tries to prevent him from doing so. It is shown that, for every constant ε>0, there exists n0 such that, for every n[ges ]n0, the Breaker has a winning strategy in TBin(N, n, q) if q>(1+ε)N/logn, while, for q<(1−ε)N/logn, the game TBin(N, n, q) can be won by the Maker provided that n=o(N).

We define uniformly spread sets as point sets in d-dimensional Euclidean space that are wobbling equivalent to the standard lattice ℤd. A linear image ϕ(ℤd) of ℤd is shown to be uniformly spread if and only if det(ϕ) = 1. Explicit geometrical and number-theoretical constructions are given. In 2-dimensional Euclidean space we obtain bounds for the wobbling distance for rotations, shearings and stretchings that are close to optimal. Our methods also allow us to analyse the discrepancy of certain billiards. Finally, we take a look at paradoxical situations and exhibit recursive point sets that are wobbling equivalent, but not recursively so.

We consider k-uniform set systems over a universe of size n such that the size of each pairwise intersection of sets lies in one of s residue classes mod q, but k does not lie in any of these s classes. A celebrated theorem of Frankl and Wilson [8] states that any such set system has size at most (ns) when q is prime. In a remarkable recent paper, Grolmusz [9] constructed set systems of superpolynomial size Ω(exp(c log2n/log log n)) when q = 6. We give a new, simpler construction achieving a slightly improved bound. Our construction combines a technique of Frankl [6] of ‘applying polynomials to set systems’ with Grolmusz's idea of employing polynomials introduced by Barrington, Beigel and Rudich [5]. We also extend Frankl's original argument to arbitrary prime-power moduli: for any ε > 0, we construct systems of size ns+g(s), where g(s) = Ω(s1−ε). Our work overlaps with a very recent technical report by Grolmusz [10].

Many applications of Szemerédi's Regularity Lemma for graphs are based on the following counting result. If ${\mathcal G}$ is an $s$-partite graph with partition $V({\mathcal G}) =\bigcup_{i=1}^{s} V_i$, $\vert V_i\vert =m$ for all $i\in [s]$, and all pairs $(V_i, V_j)$, $1\leq i < j\leq s$, are $\epsilon$-regular of density $d$, then $\mathcal{G}$ contains $(1\pm f(\epsilon))d^{({s\atop 2})}m^s$ cliques $K_{s}$, provided $\epsilon<\epsilon(d)$, where $f(\epsilon)$ tends to 0 as $\epsilon$ tends to 0.

Guided by the regularity lemma for 3-uniform hypergraphs established earlier by Frankl and Rödl, Nagle and Rödl proved a corresponding counting lemma. Their proof is rather technical, mostly due to the fact that the ‘quasi-random’ hypergraph arising after application of Frankl and Rödl's regularity lemma is ‘sparse’, and consequently difficult to handle.

When the ‘quasi-random’ hypergraph is ‘dense’ Kohayakawa, Rödl and Skokan (J. Combin. Theory Ser. A97 307–352) found a simpler proof of the counting lemma. Their result applies even to $k$-uniform hypergraphs for arbitrary $k$. While the Frankl–Rödl regularity lemma will not render the dense case, in this paper, for $k=3$, we are nevertheless able to reduce the harder, sparse case to the dense case.

Namely, we prove that a ‘dense substructure’ randomly chosen from the ‘sparse $\delta$-regular structure’ is $\delta$-regular as well. This allows us to count the number of cliques (and other subhypergraphs) using the Kohayakawa–Rödl–Skokan result, and provides an alternative proof of the counting lemma in the sparse case. Since the counting lemma in the dense case applies to $k$-uniform hypergraphs for arbitrary $k$, there is a possibility that the approach of this paper can be adopted to the general case as well.

Let $P(G,t)$ and $F(G,t)$ denote the chromatic and flow polynomials of a graph $G$. G. D. Birkhoff and D C. Lewis showed that, if $G$ is a plane near-triangulation, then the only zeros of $P(G,t)$ in $(-\infty,2]$ are 0, 1 and 2. We will extend their theorem by showing that a stronger result to the dual statement holds for both planar and non-planar graphs: if $G$ is a bridge graph with at most one vertex of degree other than three, then the only zeros of $F(G,t)$ in $(-\infty,\alpha]$ are 1 and 2, where $\alpha\approx 2.225\cdots$ is the real zero in $(2,3)$ of the polynomial $t^4-8t^3+22t^2-28t+17$. In addition we construct a sequence of ‘near-cubic’ graphs whose flow polynomials have zeros converging to $\alpha$ from above.

We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$ . We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min \{\delta (G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$ , where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac.

Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480–516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480–516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159–176], this fully resolves the existence of triangle factors in randomly perturbed graphs.

We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$ -universality.

We compute the first three terms of the 1/d expansions for the growth constants and one-point functions of nearest-neighbour lattice trees and lattice (bond) animals on the integer lattice $\mathbb{Z}^d$, with rigorous error estimates. The proof uses the lace expansion, together with a new expansion for the one-point functions based on inclusion–exclusion.

The chromatic polynomial PΓ(x) of a graph Γ is a polynomial whose value at the positive integer k is the number of proper k-colourings of Γ. If G is a group of automorphisms of Γ, then there is a polynomial OPΓ,G(x), whose value at the positive integer k is the number of orbits of G on proper k-colourings of Γ.

It is known that real chromatic roots cannot be negative, but they are dense in ∞). Here we discuss the location of real orbital chromatic roots. We show, for example, that they are dense in , but under certain hypotheses, there are zero-free regions.

We also look at orbital flow roots. Here things are more complicated because the orbit count is given by a multivariate polynomial; but it has a natural univariate specialization, and we show that the roots of these polynomials are dense in the negative real axis.

We compute the limit shape for several classes of restricted integer partitions, where the restrictions are placed on the part sizes rather than the multiplicities. Our approach utilizes certain classes of bijections which map limit shapes continuously in the plane. We start with bijections outlined in [43], and extend them to include limit shapes with different scaling functions.

We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider Xn, the normalized version of I(Tn), for a sequence of trees Tn. For fixed Tn's, we prove a sufficient condition for Xn to converge in distribution. As an application, we identify the limit of Xn for complete b-ary trees. For Tn being split trees [16], we show that Xn converges to the unique solution of a distributional equation. Finally, when Tn's are conditional Galton–Watson trees, we show that Xn converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].