We consider the minimum-weight path between any pair of nodes of the n-vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the longest of these minimum-weight paths has about α* log n edges, where α* ≈ 3.5911 is the unique solution of the equation α log α − α = 1. This answers a question posed by Janson [8].

Let P be a monotone increasing graph property, let G = (V, E) be a graph, and let q be a positive integer. In this paper, we study the (1: q) Maker–Breaker game, played on the edges of G, in which Maker's goal is to build a graph that satisfies the property P. It is clear that in order for Maker to have a chance of winning, G itself must satisfy P. We prove that if G satisfies P in some strong sense, that is, if one has to delete sufficiently many edges from G in order to obtain a graph that does not satisfy P, then Maker has a winning strategy for this game. We also consider a different notion of satisfying some property in a strong sense, which is motivated by a problem of Duffus, Łuczak and Rödl [6].

A digraph is m-labelled if every arc is labelled by an integer in {1, . . ., m}. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study n-fibre colourings of labelled digraphs. These are colourings of the arcs of D such that at each vertex v, and for each colour α, in(v, α) + out(v, α) ≤ n with in(v, α) the number of arcs coloured α entering v and out(v, α) the number of labels l such that there is at least one arc of label l leaving v and coloured with α. The problem is to find the minimum number of colours λn(D) such that the m-labelled digraph D has an n-fibre colouring. In the particular case when D is 1-labelled, λ1(D) is called the directed star arboricity of D, and is denoted by dst(D). We first show that dst(D) ≤ 2Δ−(D)+1, and conjecture that if Δ−(D) ≥ 2, then dst(D) ≤ 2Δ−(D). We also prove that for a subcubic digraph D, then dst(D) ≤ 3, and that if Δ+(D), Δ−(D) ≤ 2, then dst(D) ≤ 4. Finally, we study λn(m, k) = max{λn(D) | D is m-labelled and Δ−(D) ≤ k}. We show that if m ≥ n, then for some constant C. We conjecture that the lower bound should be the correct value of λn(m, k).

This special issue is devoted to papers from the meeting on Combinatorics and Probability, held at the Mathematisches Forschungsinstitut in Oberwolfach from 26 April to 2 May. This meeting focused on the common themes of Combinatorics, Discrete Probability and Theoretical Computer Science, and the lectures, many of which were given by young participants, stimulated fruitful discussions. The open problems session held during the meeting, and the fact that the participants work in different and related topics, encouraged interesting discussions and collaborations.

We investigate the rank of random (symmetric) sparse matrices. Our main finding is that with high probability, any dependency that occurs in such a matrix is formed by a set of few rows that contains an overwhelming number of zeros. This allows us to obtain an exact estimate for the co-rank.

We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function f: {−1, 1}n → {−1, 1} that depends on k (unknown) coordinates. While the best-known algorithms for the general problem of learning a k-junta require running times of nk poly(n, 2k), we show that, given access to k different product distributions with biases separated by γ > 0, the functions may be learned in time poly(n, 2k, γ−k). More generally, given access to t ≤ k different product distributions, the functions may be learned in time nk/tpoly(n, 2k, γ−k). Our techniques involve novel results in Fourier analysis, relating Fourier expansions with respect to different biases, and a generalization of Russo's formula.

Define the Linus sequence Ln for n ≥ 1 as a 0–1 sequence with L1 = 0, and Ln chosen so as to minimize the length of the longest immediately repeated block Ln−2r+1 ⋅⋅⋅ Ln−r = Ln−r+1 ⋅⋅⋅ Ln. Define the Sally sequence Sn as the length r of the longest repeated block that was avoided by the choice of Ln. We prove several results about these sequences, such as exponential decay of the frequency of highly periodic subwords of the Linus sequence, zero entropy of any stationary process obtained as a limit of word frequencies in the Linus sequence and infinite average value of the Sally sequence. In addition we make a number of conjectures about both sequences.

We provide a framework for online conflict-free colouring of any hypergraph. We introduce the notion of a degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an efficient randomized online algorithm for conflict-free colouring of any k-degenerate hypergraph with n vertices. Our algorithm uses O(k log n) colours with high probability and this bound is asymptotically optimal. Moreover, our algorithm uses O(k log k log n) random bits with high probability. We introduce algorithms that are allowed to perform a few recolourings of already coloured points. We provide deterministic online conflict-free colouring algorithms for points on the line with respect to intervals and for points on the plane with respect to half-planes (or unit disks) that use O(log n) colours and perform a total of at most O(n) recolourings.

We introduce the concept of a relative Tutte polynomial of coloured graphs. We show that this relative Tutte polynomial can be computed in a way similar to the classical spanning tree expansion used by Tutte in his original paper on this subject. We then apply the relative Tutte polynomial to virtual knot theory. More specifically, we show that the Kauffman bracket polynomial (and hence the Jones polynomial) of a virtual knot can be computed from the relative Tutte polynomial of its face (Tait) graph with some suitable variable substitutions. Our method offers an alternative to the ribbon graph approach, using the face graph obtained from the virtual link diagram directly.

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A ⊂ V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t → ∞. The main question is to determine the critical probability pc([n]d, r) at which percolation becomes likely, and to give bounds on the size of the critical window. In this paper we study this problem when r = 2, for all functions n and d satisfying d ≫ log n.

The bootstrap process has been extensively studied on [n]d when d is a fixed constant and 2 ⩽ r ⩽ d, and in these cases pc([n]d, r) has recently been determined up to a factor of 1 + o(1) as n → ∞. At the other end of the scale, Balogh and Bollobás determined pc([2]d, 2) up to a constant factor, and Balogh, Bollobás and Morris determined pc([n]d, d) asymptotically if d ≥ (log log n)2+ϵ, and gave much sharper bounds for the hypercube.

Here we prove the following result. Let λ be the smallest positive root of the equation so λ ≈ 1.166. Then if d is sufficiently large, and moreover as d → ∞, for every function n = n(d) with d ≫ log n.

This article presents uniform random generators of plane partitions according to size (the number of cubes in the 3D interpretation). Combining a bijection of Pak with the method of Boltzmann sampling, we obtain random samplers that are slightly superlinear: the complexity is O(n(ln n)3) in approximate-size sampling and O(n4/3) in exact-size sampling (under a real-arithmetic computation model). To our knowledge, these are the first polynomial-time samplers for plane partitions according to size (there exist polynomial-time samplers of another type, which draw plane partitions that fit inside a fixed bounding box). The same principles yield efficient samplers for (a × b)-boxed plane partitions (plane partitions with two dimensions bounded), and for skew plane partitions. The random samplers allow us to perform simulations and observe limit shapes and frozen boundaries, which have been analysed recently by Cerf and Kenyon for plane partitions, and by Okounkov and Reshetikhin for skew plane partitions.

We investigate the end spaces of infinite dual graphs. We show that there exists a natural homeomorphism * between the end spaces of a graph and its dual, and that * preserves the ‘end degree’. In particular, * maps thick ends to thick ends. Along the way, we prove that Tutte-connectivity is invariant under taking (infinite) duals.

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with m edges can be separated into two parts of roughly equal size by the removal of vertices. This result is then used to deduce that every string graph with n vertices and no complete bipartite subgraph Kt,t has at most ctn edges, where ct is a constant depending only on t. Another application shows that locally tree-like string graphs are globally tree-like: for any ε > 0, there is an integer g(ε) such that every string graph with n vertices and girth at least g(ε) has at most (1 + ε)n edges. Furthermore, the number of such labelled graphs is at most (1 + ε)nT(n), where T(n) = nn−2 is the number of labelled trees on n vertices.

We consider the problem of testing expansion in bounded-degree graphs. We focus on the notion of vertex expansion: an α-expander is a graph G = (V, E) in which every subset U ⊆ V of at most |V|/2 vertices has a neighbourhood of size at least α ⋅ |U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time . We prove that the property-testing algorithm proposed by Goldreich and Ron with appropriately set parameters accepts every α-expander with probability at least and rejects every graph that is ϵ-far from any α*-expander with probability at least , where and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is .

Let R = (r1, . . ., rm) and C = (c1, . . ., cn) be positive integer vectors such that r1 + ⋯ + rm = c1 + ⋯ + cn. We consider the set Σ(R, C) of non-negative m × n integer matrices (contingency tables) with row sums R and column sums C as a finite probability space with the uniform measure. We prove that a random table D ∈ Σ(R, C) is close with high probability to a particular matrix (‘typical table’) Z defined as follows. We let g(x) = (x + 1)ln(x + 1) − x ln x for x ≥ 0 and let g(X) = ∑i,jg(xij) for a non-negative matrix X = (xij). Then g(X) is strictly concave and attains its maximum on the polytope of non-negative m × n matrices X with row sums R and column sums C at a unique point, which we call the typical table Z.

We derive new results for the performance of a simple greedy algorithm for finding large independent sets and matchings in constant-degree regular graphs. We show that for r-regular graphs with n nodes and girth at least g, the algorithm finds an independent set of expected cardinality where f(r) is a function which we explicitly compute. A similar result is established for matchings. Our results imply improved bounds for the size of the largest independent set in these graphs, and provide the first results of this type for matchings. As an implication we show that the greedy algorithm returns a nearly perfect matching when both the degree r and girth g are large. Furthermore, we show that the cardinality of independent sets and matchings produced by the greedy algorithm in arbitrary bounded-degree graphs is concentrated around the mean. Finally, we analyse the performance of the greedy algorithm for the case of random i.i.d. weighted independent sets and matchings, and obtain a remarkably simple expression for the limiting expected values produced by the algorithm. In fact, all the other results are obtained as straightforward corollaries from the results for the weighted case.

We study the number of random records in a binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

Consider a finite irreducible Markov chain on state space S with transition matrix M and stationary distribution π. Let R be the diagonal matrix of return times, Rii = 1/πi. Given distributions σ, τ and k ∈ S, the exit frequency xk(σ, τ) denotes the expected number of times a random walk exits state k before an optimal stopping rule from σ to τ halts the walk. For a target distribution τ, we define Xτ as the n × n matrix given by (Xτ)ij = xj(i, τ), where i also denotes the singleton distribution on state i.

The dual Markov chain with transition matrix = RM⊤R−1 is called the reverse chain. We prove that Markov chain duality extends to matrices of exit frequencies. Specifically, for each target distribution τ, we associate a unique dual distribution τ*. Let denote the matrix of exit frequencies from singletons to τ* on the reverse chain. We show that , where b is a non-negative constant vector (depending on τ). We explore this exit frequency duality and further illuminate the relationship between stopping rules on the original chain and reverse chain.

In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a ‘latent’ partition V1,. . ., Vk. Moreover, consider a ‘density matrix’ Ɛ = (Ɛvw)v, sw∈V such that, for v ∈ Vi and w ∈ Vj, the entry Ɛvw is the fraction of all possible Vi−Vj-edges that are actually present in G. We show that on input (G, k) the partition V1,. . ., Vk can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: Ɛ approximates the adjacency matrix of G in the operator norm, for vertices v ∈ Vi, w ∈ Vj ≠ Vi the corresponding column vectors Ɛv, Ɛw are separated, and G is sufficiently ‘regular’ with respect to the matrix Ɛ. This result in particular applies to sparse graphs with bounded average degree as n = #V → ∞, and it has various consequences on partitioning random graphs.

We analyse a simple random process in which a token is moved in the interval A = {0, . . ., n}. Fix a probability distribution μ over D = {1, . . ., n}. Initially, the token is placed in a random position in A. In round t, a random step sized is chosen according to μ. If the token is in position x ≥ d, then it is moved to position x − d. Otherwise it stays put. Let TX be the number of rounds until the token reaches position 0. We show tight bounds for the expectation Eμ(TX) of TX for varying distributions μ. More precisely, we show that . The same bounds are proved for the analogous continuous process, where step sizes and token positions are real values in [0, n + 1), and one measures the time until the token has reached a point in [0, 1). For the proofs, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over [0, 1] with a ‘blind’ optimization strategy.