A collection of permutation classes is exhibited whose growth rates form a perfect set, thereby refuting some conjectures of Balogh, Bollobás and Morris.

Given ω ≥ 1, let be the graph with vertex set in which two vertices are joined if they agree in one coordinate and differ by at most ω in the other. (Thus is precisely .) Let pc(ω) be the critical probability for site percolation on . Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that limω→∞ωpc(ω)=log(3/2). We also prove analogues of this result for the n-by-n grid and in higher dimensions, the latter involving interesting connections to Gilbert's continuum percolation model. To prove our results, we explore the component of the origin in a certain non-standard way, and show that this exploration is well approximated by a certain branching random walk.

We show that a maximum cut of a random graph below the giant-component threshold can be found in linear space and linear expected time by a simple algorithm. In fact, the algorithm solves a more general class of problems, namely binary 2-variable constraint satisfaction problems. In addition to Max Cut, such Max 2-CSPs encompass Max Dicut, Max 2-Lin, Max 2-Sat, Max-Ones-2-Sat, maximum independent set, and minimum vertex cover. We show that if a Max 2-CSP instance has an ‘underlying’ graph which is a random graph $G \in \mathcal{G}(n,c/n)$, then the instance is solved in linear expected time if $c \leq 1$. Moreover, for arbitrary values (or functions) $c>1$ an instance is solved in expected time $n \exp(O(1+(c-1)^3 n))$; in the ‘scaling window’ $c=1+\lambda n^{-1/3}$ with $\lambda$ fixed, this expected time remains linear.

Our method is to show, first, that if a Max 2-CSP has a connected underlying graph with $n$ vertices and $m$ edges, then $O(n 2^{(m-n)/2})$ is a deterministic upper bound on the solution time. Then, analysing the tails of the distribution of this quantity for a component of a random graph yields our result. Towards this end we derive some useful properties of binomial distributions and simple random walks.

Markov chain decomposition is a tool for analysing the convergence rate of a complicated Markov chain by studying its behaviour on smaller, more manageable pieces of the state space. Roughly speaking, if a Markov chain converges quickly to equilibrium when restricted to subsets of the state space, and if there is sufficient ergodic flow between the pieces, then the original Markov chain also must converge rapidly to equilibrium. We present a new version of the decomposition theorem where the pieces partition the state space, rather than forming a cover where pieces overlap, as was previously required. This new formulation is more natural and better suited to many applications. We apply this disjoint decomposition method to demonstrate the efficiency of simple Markov chains designed to uniformly sample circuits of a given length on certain Cayley graphs. The proofs further indicate that a Markov chain for sampling adsorbing staircase walks, a problem arising in statistical physics, is also rapidly mixing.

A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is ‘pseudorandom’, meaning that, for instance, the matching contains as many edges from a given set of edges as predicted by a heuristic argument.

The intersection exponent ξ for simple random walk in two and three dimensions gives a measure of the rate of decay of the probability that paths do not intersect. In this paper we show that the intersection exponent for random walks is the same as that for Brownian motion and show in fact that the probability of nonintersection up to distance n is comparable (equal up to multiplicative constants) to n−ξ.

Let G be a connected graph with n vertices and m edges (multiple edges allowed), and let k ≥ 2 be an integer. There is an algorithm with (optimal) running time of O(m) that finds

(i) a bipartite subgraph of G with ≥ m/2 + (n − 1)/4 edges,

(ii) a bipartite subgraph of G with ≥ m/2 + 3(n−1)/8 edges if G is triangle-free,

(iii) a k-colourable subgraph of G with ≥ m − m/k + (n−1)/k + (k − 3)/2 edges if k ≥ 3 and G is not k-colorable.

Infinite families of graphs show that each of those lower bounds on the worst-case performance are best possible (for every algorithm). Moreover, even if short cycles are excluded, the general lower bound of m − m/k cannot be replaced by m − m/k + εm for any fixed ε > 0; and it is NP-complete to decide whether a graph with m edges contains a k-colorable subgraph with more than m − m/k + εm edges, for any k ≥ 2 and ε> 0, ε < 1/k.

Determining the distribution of the number of empty urns after a number of balls have been thrown randomly into the urns is a classical and well understood problem. We study a generalization: Given a finite alphabet of size σ and a word length q, what is the distribution of the number X of words (of length q) that do not occur in a random text of length n+q−1 over the given alphabet? For q=1, X is the number Y of empty urns with σ urns and n balls. For q[ges ]2, X is related to the number Y of empty urns with σq urns and n balls, but the law of X is more complicated because successive words in the text overlap. We show that, perhaps surprisingly, the laws of X and Y are not as different as one might expect, but some problems remain currently open.

Consider sequences {Xi}mi=1 and {Yj}nj=1 of independent random variables, taking values in a finite alphabet, and assume that the variables X1, X2, … and Y1, Y2, … follow the distributions μ and v, respectively. Two variables Xi and Yj are said to match if Xi = Yj. Let the number of matching subsequences of length k between the two sequences, when r, 0 [les ] r < k, mismatches are allowed, be denoted by W.

In this paper we use Stein's method to bound the total variation distance between the distribution of W and a suitably chosen compound Poisson distribution. To derive rates of convergence, the case where E[W] stays bounded away from infinity, and the case where E[W] → ∞ as m, n → ∞, have to be treated separately. Under the assumption that ln n/ln(mn) → ρ ∈ (0, 1), we give conditions on the rate at which k → ∞, and on the distributions μ and v, for which the variation distance tends to zero.

The sizes of the cycles and unicyclic components in the random graph $G(n, n/2\pm s)$, where $n^{2/3}\ll s \ll n$, are studied using the language of point processes. This refines several earlier results by different authors. Asymptotic distributions of various random variables are given: these distributions include the gamma distributions with parameters 1/4, 1/2 and 3/4, as well as the Poisson–Dirichlet and GEM distributions with parameters 1/4 and 1/2.

We consider statistical properties of random integer partitions. In order to compute means, variances and higher moments of various partition statistics, one often has to study generating functions of the form P(x)F(x), where P(x) is the generating function for the number of partitions. In this paper, we show how asymptotic expansions can be obtained in a quasi-automatic way from expansions of F(x) around x = 1, which parallels the classical singularity analysis of Flajolet and Odlyzko in many ways. Numerous examples from the literature, as well as some new statistics, are treated via this methodology. In addition, we show how to compute further terms in the asymptotic expansions of previously studied partition statistics.

The first open case of the Brown–Erdős–Sós conjecture is equivalent to the following: for every c > 0, there is a threshold n0 such that if a quasigroup has order n ⩾ n0, then for every subset S of triples of the form (a, b, ab) with |S| ⩾ cn2, there is a seven-element subset of the quasigroup which spans at least four triples of S. In this paper we prove the conjecture for finite groups.

A celebrated theorem of Friedgut says that every function f : {0, 1}n → {0, 1} can be approximated by a function g : {0, 1}n → {0, 1} with , which depends only on eO(If / ε) variables, where If is the sum of the influences of the variables of f. Dinur and Friedgut later showed that this statement also holds if we replace the discrete domain {0, 1}n with the continuous domain [0, 1]n, under the extra assumption that f is increasing. They conjectured that the condition of monotonicity is unnecessary and can be removed.

We show that certain constant-depth decision trees provide counter-examples to the Dinur–Friedgut conjecture. This suggests a reformulation of the conjecture in which the function g : [0, 1]n → {0, 1}, instead of depending on a small number of variables, has a decision tree of small depth. In fact we prove this reformulation by showing that the depth of the decision tree of g can be bounded by eO(If / ε2).

Furthermore, we consider a second notion of the influence of a variable, and study the functions that have bounded total influence in this sense. We use a theorem of Bourgain to show that these functions have certain properties. We also study the relation between the two different notions of influence.

Given graphs H1, H2, a graph G is (H1, H2) -Ramsey if, for every colouring of the edges of G with red and blue, there is a red copy of H1 or a blue copy of H2. In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs. This is a random graph model introduced by Bohman, Frieze and Martin [8] in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali [30] in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (K3, Kt) -Ramsey (for t ≽ 3). They also raised the question of generalizing this result to pairs of graphs other than (K3, Kt). We make significant progress on this question, giving a precise solution in the case when H1 = Ks and H2 = Kt where s, t ≽ 5. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the (K3, Kt) -Ramsey question. Moreover, we give bounds for the corresponding (K4, Kt) -Ramsey question; together with a construction of Powierski [37] this resolves the (K4, K4) -Ramsey problem.

We also give a precise solution to the analogous question in the case when both H1 = Cs and H2 = Ct are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalization of the Krivelevich, Sudakov and Tetali [30] result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (Cs, Kt) -Ramsey (for odd s ≽ 5 and t ≽ 4).

To prove our results we combine a mixture of approaches, employing the container method, the regularity method as well as dependent random choice, and apply robust extensions of recent asymmetric random Ramsey results.

Let X1, …, Xn be a sequence of r.v.s produced by a stationary Markov chain with state space an alphabet Ω = {ω1, …, ωq}, q [ges ] 2. We consider a set of words {A1, …, Ar}, r [ges ] 2, with letters from the alphabet Ω. We allow the words to have self-overlaps as well as overlaps between them. Let [Escr ] denote the event of the appearance of a word from the set {A1, …, Ar} at a given position. Moreover, define by N the number of non-overlapping (competing renewal) appearances of [Escr ] in the sequence X1, …, Xn. We derive a bound on the total variation distance between the distribution of N and a Poisson distribution with parameter [ ]N. The Stein–Chen method and combinatorial arguments concerning the structure of words are employed. As a corollary, we obtain an analogous result for the i.i.d. case. Furthermore, we prove that, under quite general conditions, the r.v. N converges in distribution to a Poisson r.v. A numerical example is presented to illustrate the performance of the bound in the Markov case.

Two infinite 0–1 sequences are called compatible when it is possible to cast out $0\,$s from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two 0–1 sequences are random i.i.d. and independent from each other, with probability $p$ of $1\,$s, then if $p$ is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behaviour: the probability that the origin is blocked at distance $n$ but not closer decreases only polynomially fast and not, as usual, exponentially.

E. Thorp introduced the following card shuffling model. Suppose the number of cards is even. Cut the deck into two equal piles, then interleave them as follows. Choose the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then choose from the other pile. Continue this way, flipping an independent coin for each pair, until both piles are empty.

We prove an upper bound of O(d3) for the mixing time of the Thorp shuffle with 2d cards, improving on the best known bound of O(d4). As a consequence, we obtain an improved bound on the time required to encrypt a binary message of length d using the Thorp shuffle.

The main result of this paper has the following consequence. Let G be an abelian group of order n. Let {xi: 1 ≤ 2n − 1} be a family of elements of G and let {wi: 1 ≤ i ≤ n − 1} be a family of integers prime relative to n. Then there is a permutation & of [1,2n − 1] such that

Applying this result with wi = 1 for all i, one obtains the Erdős–Ginzburg–Ziv Theorem.

Associate to a finite labeled graph G(V, E) its multiset of neighborhoods (G) = {N(υ): υ ∈ V}. We discuss the question of when a list is realizable by a graph, and to what extent G is determined by (G). The main results are: the decision problem is NP-complete; for bipartite graphs the decision problem is polynomially equivalent to Graph Isomorphism; forests G are determined up to isomorphism by (G); and if G is connected bipartite and (H) = (G), then H is completely described.

Let A be an m × n matrix and q := [lfloor ]log2(m)[rfloor ]+1. In this article we improve the well-known bound lindisc(A) [les ] 2 herdisc(A) and show that

formula here

As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyse it using game theory.