We consider graphs Gn generated by multisets [Iscr ]n with n random integers as elements, such that vertices of Gn are connected by edges if the elements of [Iscr ]n that the vertices represent are the same, and prove asymptotic results on the sparsity of edges connecting the different subgraphs Gn of the random graph generated by ∪∞n=1[Iscr ]n. These results are of independent interest and, for two models of the bootstrap, we also use them here to link almost sure and complete convergence of the corresponding bootstrap means and averages of related randomly chosen subsequences of a sequence of independent and identically distributed random variables with a finite mean. Complete convergence of these means and averages is then characterized in terms of a relationship between a moment condition on the bootstrapped sequence and the bootstrap sample size. While we also obtain new sufficient conditions for the almost sure convergence of bootstrap means, the approach taken here yields the first necessary conditions.

A solid diagram of volume n is a packing of n unit cubes into a corner so that the heights of vertical stacks of cubes do not increase in either of two horizontal directions away from the corner. An asymptotic distribution of the dimensions – heights, depths, and widths – of the diagram chosen uniformly at random among all such diagrams is studied. For each k, the planar base of k tallest stacks is shown to be Plancherel distributed in the limit $n\to\infty$.

We study the asymptotic behaviour of the relative entropy (to stationarity) for a commonly used model for riffle shuffling a deck of n cards m times. Our results establish and were motivated by a prediction in a recent numerical study of Trefethen and Trefethen. Loosely speaking, the relative entropy decays approximately linearly (in m) for m < log2n, and approximately exponentially for m > log2n. The deck becomes random in this information-theoretic sense after m = 3/2 log2n shuffles.

In this paper we prove lower and upper bounds for the extinction time of the contact process on random geometric graphs with connection radius tending to infinity. We obtain that for any infection rate λ > 0, the contact process on these graphs survives a time super-exponential in the number of vertices.

We prove that the number of multigraphs with vertex set {1, . . ., n} such that every four vertices span at most nine edges is an2+o(n2) where a is transcendental (assuming Schanuel's conjecture from number theory). This is an easy consequence of the solution to a related problem about maximizing the product of the edge multiplicities in certain multigraphs, and appears to be the first explicit (somewhat natural) question in extremal graph theory whose solution is transcendental. These results may shed light on a question of Razborov, who asked whether there are conjectures or theorems in extremal combinatorics which cannot be proved by a certain class of finite methods that include Cauchy–Schwarz arguments.

Our proof involves a novel application of Zykov symmetrization applied to multigraphs, a rather technical progressive induction, and a straightforward use of hypergraph containers.

Multiway trees, also known as m–ary search trees, are data structures generalising binary search trees. A common probability model for analysing the behaviour of these structures is the random permutation model. The probability mass function Q on the set of m–ary search trees under the random permutation model is the distribution induced by sequentially inserting the records of a uniformly random permutation into an initially empty m–ary search tree. We study some basic properties of the functional Q, which serves as a measure of the ‘shape’ of the tree. In particular, we determine exact and asymptotic expressions for the maximum and minimum values of Q and identify and count the trees achieving those values.

For any positive integer k and ε > 0, there exist nk,ε, ck, e > 0 with the following property. Given any system of n > nk,ε points in the plane with minimal distance at least 1 and any t1, t2…, tk ≥ 1, the number of those pairs of points whose distance is between ti and for some 1 ≤ i ≤ k, is at most (n2/2) (1 − 1/(k+1)+ε). This bound is asymptotically tight.

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let fb(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then for some absolute constant B, thus establishing fb(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that We conjecture that f2(n) = n1 + o(1) as n → ∞.

As usual, let us write $G_{n,p}$ for a random graph with vertex set $[n]=\{1, 2, \dots , n\}$, in which the edges are chosen independently, with probability $p$. Similarly, $G_{n,m}$ is a random graph on $[n]$ with $m$ edges. For $p=m/({{n}\atop{2}})$, in many respects, the random graphs $G_{n,m}$ and $G_{n,p}$ are practically indistinguishable. (See [4] for an introduction to random graphs.) When in the late 1950s and early 1960s Erdős and Rényi founded the theory of random graphs, one of the most important problems they left open was the determination of the chromatic number of a random graph $G_{n,m}$. The original question concerned the case $m=O(n)$, but when in the 1970s Erdős popularized the problem, he was asking for good estimates on the chromatic number of $G_{n,m}$ for $m \sim n^2/4$ (equivalently, the chromatic number of $G_{{n,1/2}}$).

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring.

For any positive integer m, let Q(m) be the least positive integer k such that ≥ m. We show that for almost all unlabelled, unrooted trees T, h(T) = Q(m), where m is the number of edges of T.

Paul Erdős has conjectured that Menger's theorem extends to infinite graphs in the following way: whenever A, B are two sets of vertices in an infinite graph, there exist a set of disjoint A−B paths and an A−B separator in this graph such that the separator consists of a choice of precisely one vertex from each of the paths. We prove this conjecture for graphs that contain a set of disjoint paths to B from all but countably many vertices of A. In particular, the conjecture is true when A is countable.

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.

Heap ordered trees are planted plane trees, labelled in such a way that the labels always increase from the root to a leaf. We study two parameters, assuming that $p$ of the $n$ nodes are selected at random: the size of the ancestor tree of these nodes and the smallest subtree generated by these nodes. We compute expectation, variance, and also the Gaussian limit distribution, the latter as an application of Hwang's quasi-power theorem.

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.

In this short note, we prove the following analog of the Kővári–Sós–Turán theorem for intersection graphs of boxes. If G is the intersection graph of n axis-parallel boxes in $${{\mathbb{R}}^d}$$ such that G contains no copy of Kt,t, then G has at most ctn( log n)2d+3 edges, where c = c(d)>0 only depends on d. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit, Chernikov, Starchenko, Tao and Tran of K2,2-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon, Basavaraju, Chandran, Mathew and Rajendraprasad. We show that there exist graphs of separation dimension 4 having superlinear number of edges.

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$, for every graph $G \in \mathcal{G}$ there is a graph $H$ with $\textrm{tw}(H) \leqslant c$ such that $G$ is isomorphic to a subgraph of $H \boxtimes K_{f(\textrm{tw}(G))}$. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth $3$; the class of $K_{s,t}$-minor-free graphs has underlying treewidth $s$ (for $t \geqslant \max \{s,3\}$); and the class of $K_t$-minor-free graphs has underlying treewidth $t-2$. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.

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.

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 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.