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

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.

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.

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.

For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.

Thomas conjectured that there is an absolute constant c such that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour every G ∈ with at most χ(G) + c colours. We introduce a parameter ρ(), called the degenerate value of , which is defined to be the smallest r such that every G ∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that is r-degenerate. Although the existence of one global bound for the degenerate values of all proper minor-closed classes would imply Thomas's conjecture, we prove that the values ρ() can be made arbitrarily large. The problem lies in the clique sum operation. As our main result, we show that excluding a planar graph with a fixed number of apex vertices gives rise to a minor-closed class with small degenerate value. As corollaries, we obtain that (i) the degenerate value of every class of graphs of bounded local tree-width is at most 6, and (ii) the degenerate value of the class of Kn-minor-free graphs is at most n + 1. These results give rise to P-time approximation algorithms for colouring any graph in these classes within an error of at most 7 and n + 2 of its chromatic number, respectively.

We consider first-passage percolation on a ladder, i.e., the graph ℕ × {0, 1}, where nodes at distance 1 are joined by an edge, and the times are exponentially i.i.d. with mean 1. We find an appropriate Markov chain to calculate an explicit expression for the time constant whose numerical value is ≈0.6827. This time constant is the long-term average inverse speed of the process. We also calculate the average residual time.

Let G = (G, +) be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A − B, while the inverse sumset theory of Freiman, Ruzsa, and others characterizes those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A ⊂ G is replaced by a discrete random variable X taking values in G, and the cardinality |A| is replaced by the Shannon entropy H(X). In particular, we classify those random variables X which have small doubling in the sense that H(X1 + X2) = H(X) + O(1) when X1, X2 are independent copies of X, by showing that they factorize as X = U + Z, where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1).

When G is torsion-free, we also establish the sharp lower bound , where o(1) goes to zero as H(X) → ∞.