We analyse the weighted height of random tries built from independent strings of i.i.d. symbols on the finite alphabet {1, . . .d}. The edges receive random weights whose distribution depends upon the number of strings that visit that edge. Such a model covers the hybrid tries of de la Briandais and the TST of Bentley and Sedgewick, where the search time for a string can be decomposed as a sum of processing times for each symbol in the string. Our weighted trie model also permits one to study maximal path imbalance. In all cases, the weighted height is shown to be asymptotic to c log n in probability, where c is determined by the behaviour of the core of the trie (the part where all nodes have a full set of children) and the fringe of the trie (the part of the trie where nodes have only one child and form spaghetti-like trees). It can be found by maximizing a function that is related to the Cramér exponent of the distribution of the edge weights.

Given m positive integers R = (ri), n positive integers C = (cj) such that Σri = Σcj = N, and mn non-negative weights W=(wij), we consider the total weight T=T(R, C; W) of non-negative integer matrices D=(dij) with the row sums ri, column sums cj, and the weight of D equal to . For different choices of R, C, and W, the quantity T(R,C; W) specializes to the permanent of a matrix, the number of contingency tables with prescribed margins, and the number of integer feasible flows in a network. We present a randomized algorithm whose complexity is polynomial in N and which computes a number T′=T′(R,C;W) such that T′ ≤ T ≤ α(R,C)T′ where . In many cases, ln T′ provides an asymptotically accurate estimate of ln T. The idea of the algorithm is to express T as the expectation of the permanent of an N × N random matrix with exponentially distributed entries and approximate the expectation by the integral T′ of an efficiently computable log-concave function on ℝmn.

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

The λ-dilate of a set A is λċA={λa : a∈A}. We give an asymptotically sharp lower bound on the size of sumsets of the form λ1ċA+ċċċ+λkċA for arbitrary integers λ1,. . .,λk and integer sets A. We also establish an upper bound for such sums, which is similar to, but often stronger than Plünnecke's inequality.

In 1998 Łuczak Rödl and Szemerédi [7] proved, by means of the Regularity Lemma, that there exists n0 such that, for any n ≥ n0 and two-edge-colouring of Kn, there exists a pair of vertex-disjoint monochromatic cycles of opposite colours covering the vertices of Kn. In this paper we make use of an alternative method of finding useful structure in a graph, leading to a proof of the same result with a much smaller value of n0. The proof gives a polynomial-time algorithm for finding the two cycles.

Starting from a sequence regarded as a walk through some set of values, we consider the associated loop-erased walk as a sequence of directed edges, with an edge from i to j if the loop-erased walk makes a step from i to j. We introduce a colouring of these edges by painting edges with a fixed colour as long as the walk does not loop back on itself, then switching to a new colour whenever a loop is erased, with each new colour distinct from all previous colours. The pattern of colours along the edges of the loop-erased walk then displays stretches of consecutive steps of the walk left untouched by the loop-erasure process. Assuming that the underlying sequence generating the loop-erased walk is a sequence of independent random variables, each uniform on [N] := {1, 2, . . ., N}, we condition the walk to start at N and stop the walk when it first reaches the subset [k], for some 1 ≤ k ≤ N − 1. We relate the distribution of the random length of this loop-erased walk to the distribution of the length of the first loop of the walk, via Cayley's enumerations of trees, and via Wilson's algorithm. For fixed N and k, and i = 1, 2, . . ., let Bi denote the events that the loop-erased walk from N to [k] has i + 1 or more edges, and the ith and (i + 1)th of these edges are coloured differently. We show that, given that the loop-erased random walk has j edges for some 1 ≤ j ≤ N − k, the events Bi for 1 ≤ i ≤ j − 1 are independent, with the probability of Bi equal to 1/(k + i + 1). This determines the distribution of the sequence of random lengths of differently coloured segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as N → ∞.

We consider the problem of minimizing the size of a family of sets such that every subset of {1,. . ., n} can be written as a disjoint union of at most k members of , where k and n are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the question of finding the minimum of || so that every subset of {1,. . ., n} is the union of two sets in was asked by Erdős and studied recently by Füredi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n, k) for which n≤3k holds, and some individual values of n and k.

We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotic almost sure mixing time of the graph created by long-range percolation on the cycle of length N (). While it is known that the asymptotic almost sure diameter drops from linear to poly-logarithmic as the exponent s decreases below 2 [4, 9], the asymptotic almost sure mixing time drops from N2 only to Ns-1 (up to poly-logarithmic factors).

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.

We formulate and give partial answers to several combinatorial problems on volumes of simplices determined by n points in 3-space, and in general in d dimensions.

1. (i) The number of tetrahedra of minimum (non-zero) volume spanned by n points in 3 is at most , and there are point sets for which this number is . We also present an O(n3) time algorithm for reporting all tetrahedra of minimum non-zero volume, and thereby extend an algorithm of Edelsbrunner, O'Rourke and Seidel. In general, for every , the maximum number of k-dimensional simplices of minimum (non-zero) volume spanned by n points in d is Θ(nk).

2. (ii) The number of unit volume tetrahedra determined by n points in 3 is O(n7/2), and there are point sets for which this number is Ω(n3 log logn).

3. (iii) For every , the minimum number of distinct volumes of all full-dimensional simplices determined by n points in d, not all on a hyperplane, is Θ(n).

A set of integers is called a B2[g] set if every integer m has at most g representations of the form m = a + a′, with a ≤ a′ and a, a′ ∈ . We obtain a new lower bound for F(g, n), the largest cardinality of a B2[g] set in {1,. . .,n}. More precisely, we prove that infn→∞ where ϵg → 0 when g → ∞. We show a connection between this problem and another one discussed by Schinzel and Schmidt, which can be considered its continuous version.

Let denote the set of unrooted labelled trees of size n and let ℳ be a particular (finite, unlabelled) tree. Assuming that every tree of is equally likely, it is shown that the limiting distribution as n goes to infinity of the number of occurrences of ℳ is asymptotically normal with mean value and variance asymptotically equivalent to μn and σ2n, respectively, where the constants μ>0 and σ≥0 are computable.

We study the number of subtrees on the fringe of random recursive trees and random binary search trees whose limit law is known to be either normal or Poisson or degenerate depending on the size of the subtree. We introduce a new approach to this problem which helps us to further clarify this phenomenon. More precisely, we derive optimal Berry–Esseen bounds and local limit theorems for the normal range and prove a Poisson approximation result as the subtree size tends to infinity.

Sokal in 2001 proved that the complex zeros of the chromatic polynomial PG(q) of any graph G lie in the disc |q| < 7.963907Δ, where Δ is the maximum degree of G. This result answered a question posed by Brenti, Royle and Wagner in 1994 and hence proved a conjecture proposed by Biggs, Damerell and Sands in 1972. Borgs gave a short proof of Sokal's result. Fernández and Procacci recently improved Sokal's result to |q| < 6.91Δ. In this paper, we shall show that all real zeros of PG(q) are in the interval [0,5.664Δ). For the special case that Δ = 3, all real zeros of PG(q) are in the interval [0,4.765Δ).

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.

Let Γ =(V,E) be a point-symmetric reflexive relation and let υ ∈ V such that |Γ(υ)| is finite (and hence |Γ(x)| is finite for all x, by the transitive action of the group of automorphisms). Let j ∈ℕ be an integer such that Γj(υ)∩ Γ−(υ)={υ}. Our main result states that

As an application we have |Γj(υ)| ≥ 1+(|Γ(υ)|−1)j. The last result confirms a recent conjecture of Seymour in the case of vertex-symmetric graphs. Also it gives a short proof for the validity of the Caccetta–Häggkvist conjecture for vertex-symmetric graphs and generalizes an additive result of Shepherdson.

A partition of a positive integer n is a finite sequence of positive integers a1, a2, . . ., ak such that a1+a2+ċ ċ ċ+ak=n and ai+1 ≥ ai for all i. Let d be a fixed positive integer. We say that we have an ascent of size d or more if ai+1 ≥ ai+d.

We determine the mean, the variance and the limiting distribution of the number of ascents of size d or more (equivalently, the number of distinct part sizes of multiplicity d or more) in the partitions of n.

We prove that the chromatic polynomial of a finite graph of maximal degree Δ is free of zeros for |q| ≥ C*(Δ) with This improves results by Sokal and Borgs. Furthermore, we present a strengthening of this condition for graphs with no triangle-free vertices.

We consider Glauber dynamics on finite spin systems. The mixing time of Glauber dynamics can be bounded in terms of the influences of sites on each other. We consider three parameters bounding these influences: α, the total influence on a site, as studied by Dobrushin; α′, the total influence of a site, as studied by Dobrushin and Shlosman; and α″, the total influence of a site in any given context, which is related to the path-coupling method of Bubley and Dyer. It is known that if any of these parameters is less than 1 then random-update Glauber dynamics (in which a randomly chosen site is updated at each step) is rapidly mixing. It is also known that the Dobrushin condition α < 1 implies that systematic-scan Glauber dynamics (in which sites are updated in a deterministic order) is rapidly mixing. This paper studies two related issues, primarily in the context of systematic scan: (1) the relationship between the parameters α, α′ and α″, and (2) the relationship between proofs of rapid mixing using Dobrushin uniqueness (which typically use analysis techniques) and proofs of rapid mixing using path coupling. We use matrix balancing to show that the Dobrushin–Shlosman condition α′ < 1 implies rapid mixing of systematic scan. An interesting question is whether the rapid mixing results for scan can be extended to the α = 1 or α′ = 1 case. We give positive results for the rapid mixing of systematic scan for certain α = 1 cases. As an application, we show rapid mixing of systematic scan (for any scan order) for heat-bath Glauber dynamics for proper q-colourings of a degree-Δ graph G when q ≥ 2Δ.

We consider random graphs with a fixed degree sequence. Molloy and Reed [11, 12] studied how the size of the giant component changes according to degree conditions. They showed that there is a phase transition and investigated the order of components before and after the critical phase. In this paper we study more closely the order of components at the critical phase, using singularity analysis of a generating function for a branching process which models the random graph with a given degree sequence.