We describe a short and easy-to-analyse construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold, Vadhan and Wigderson (2002) to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which applies the replacement product (only twice!) to turn the Cayley expanders of Alon and Roichman (1994), whose degree is polylog n, into constant-degree expanders. This enables us to prove the required expansion using a simple new combinatorial analysis of the replacement product (instead of the spectral analysis used by Reingold, Vadhan and Wigderson).

We show that for 0<α<1 and θ>−α, the Poisson–Dirichlet distribution with parameter (α, θ) is the unique reversible distribution of a rather natural fragmentation–coalescence process. This completes earlier results in the literature for certain split-and-merge transformations and the parameter α = 0.

Let be a sequence of real numbers satisfying for each k ≥ 0, where M ≥ 1 is a fixed number. We prove that, for any sequence of real numbers , there is a real number ξ such that for each k ≥ 0. Here, denotes the distance from to the nearest integer. This is a corollary derived from our main theorem, which is a more general matrix version of this statement with explicit constants.

We derive here the Friedland–Tverberg inequality for positive hyperbolic polynomials. This inequality is applied to give lower bounds for the number of matchings in r-regular bipartite graphs. It is shown that some of these bounds are asymptotically sharp. We improve the known lower bound for the three-dimensional monomer–dimer entropy.

Babai and Sós have asked whether there exists a constant c > 0 such that every finite group G has a product-free subset of size at least c|G|: that is, a subset X that does not contain three elements x, y and z with xy = z. In this paper we show that the answer is no. Moreover, we give a simple sufficient condition for a group not to have any large product-free subset.

An induced forest of a graph G is an acyclic induced subgraph of G. The present paper is devoted to the analysis of a simple randomized algorithm that grows an induced forest in a regular graph. The expected size of the forest it outputs provides a lower bound on the maximum number of vertices in an induced forest of G. When the girth is large and the degree is at least 4, our bound coincides with the best bound known to hold asymptotically almost surely for random regular graphs. This results in an alternative proof for the random case.

Given a digraph D, let δ0(D) := min{δ+(D), δ−(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with δ0(D)≥n/2 + l −1 is l-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [17]. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e., that for every sequence s1, . . ., sk of distinct vertices of D there is a directed cycle which encounters s1, . . ., sk in this order. This result will be used in [16].

The following two conjectures arose in the work of Grimmett and Winkler, and Pemantle: the uniformly random forest F and the uniformly random connected subgraph C of a finite graph G have the edge-negative association property. In other words, for all distinct edges e and f of G, the probability that F (respectively, C) contains e conditioned on containing f is less than or equal to the probability that F (respectively, C) contains e. Grimmett and Winkler showed that the first conjecture is true for all simple graphs on 8 vertices and all graphs on 9 vertices with at most 18 edges. In this paper, we describe an infinite, nontrivial class of graphs and matroids for which a generalized version of both conjectures holds.

We obtain large-deviation approximations for the empirical distribution for a general family of occupancy problems. In the general setting, balls are allowed to fall in a given urn depending on the urn's contents prior to the throw. We discuss a parametric family of statistical models that includes Maxwell–Boltzmann, Bose–Einstein and Fermi–Dirac statistics as special cases. A process-level large-deviation analysis is conducted and the rate function for the original problem is then characterized, via the contraction principle, by the solution to a calculus of variations problem. The solution to this variational problem is shown to coincide with that of a simple finite-dimensional minimization problem. As a consequence, the large-deviation approximations and related qualitative information are available in more-or-less explicit form.