We prove that there exists a constant c such that, for any integer Δ, the Ramsey number of a bipartite graph on n vertices with maximum degree Δ is less than 2cΔn. A probabilistic argument due to Graham, Rödl and Ruciński implies that this result is essentially sharp, up to the constant c in the exponent. Our proof hinges upon a quantitative form of a hypergraph packing result of Rödl, Ruciński and Taraz.

We prove that every connected graph of order n ≥ 2 has an induced subgraph with all degrees odd of order at least cn/log n, where cis a constant. We also give a bound in terms of chromatic number, and resolve the analogous problem for random graphs.

In this work we determine the expected number of vertices of degree k = k(n) in a graph with n vertices that is drawn uniformly at random from a subcritical graph class. Examples of such classes are outerplanar, series-parallel, cactus and clique graphs. Moreover, we provide exponentially small bounds for the probability that the quantities in question deviate from their expected values.

The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovász and Vu [25] yielded a (log logn)2 polynomial time approximation. We refine the upper bound of [25], and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdős–Rényi random graph G(n, c/n) in the supercritical regime with c > 1 fixed, is asymptotic to ϕ(c)nlog2n, where ϕ(c) → 1 as c ↓ 1. However, our new bound implies that the cover time for the critical Erdős–Rényi random graph G(n, 1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0, 1}n, on high-girth expanders, and on tori ℤdn for fixed large d. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on k vertices is of order k3/2. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman [45], is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.

We provide an alternative, simpler and more general derivation of the Clarkson–Shor probabilistic technique [7] and use it to obtain several extensions and new combinatorial bounds.

A spanning tree T of a graph G is called a homeomorphically irreducible spanning tree (HIST) if T does not contain vertices of degree 2. A graph G is called locally connected if, for every vertex v ∈ V(G), the subgraph induced by the neighbourhood of v is connected. In this paper, we prove that every connected and locally connected graph with more than 3 vertices contains a HIST. Consequently, we confirm the following conjecture due to Archdeacon: every graph that triangulates some surface has a HIST, which was proposed as a question by Albertson, Berman, Hutchinson and Thomassen.

The notion of conductance introduced by Jerrum and Sinclair [8] has been widely used to prove rapid mixing of Markov chains. Here we introduce a bound that extends this in two directions. First, instead of measuring the conductance of the worst subset of states, we bound the mixing time by a formula that can be thought of as a weighted average of the Jerrum–Sinclair bound (where the average is taken over subsets of states with different sizes). Furthermore, instead of just the conductance, which in graph theory terms measures edge expansion, we also take into account node expansion. Our bound is related to the logarithmic Sobolev inequalities, but it appears to be more flexible and easier to compute.

In the case of random walks in convex bodies, we show that this new bound is better than the known bounds for the worst case. This saves a factor of $O(n)$ in the mixing time bound, which is incurred in all proofs as a ‘penalty’ for a ‘bad start’. We show that in a convex body in $\mathbb{R}^n$, with diameter $D$, random walk with steps in a ball with radius $\delta$ mixes in $O^*(nD^2/\delta^2)$ time (if idle steps at the boundary are not counted). This gives an $O^*(n^3)$ sampling algorithm after appropriate preprocessing, improving the previous bound of $O^*(n^4)$.

The application of the general conductance bound in the geometric setting depends on an improved isoperimetric inequality for convex bodies.

Inequalities for martingales with bounded differences have recently proved to be very useful in combinatorics and in the mathematics of operational research and computer science. We see here that these inequalities extend in a natural way to ‘centering sequences’ with bounded differences, and thus include, for example, better inequalities for sequences related to sampling without replacement.

Many of the classical results of Ramsey Theory, including those of Hilbert, Schur, and van der Waerden, are naturally stated as instances of the following problem: given a u × ν matrix A with rational entries, is it true, that whenever the set ℕ of positive integers is finitely coloured, there must exist some x∈ℕν such that all entries of Ax are the same colour? While the theorems cited are all consequences of Rado's theorem, the general problem had remained open. We provide here several solutions for the alternate problem, which asks that x∈ℕν. Based on this, we solve the general problem, giving various equivalent characterizations.

The branching random walk on a regular graph turns out to be particularly easy to analyse using results for the corresponding simple random walk. In this way, one can show that there is an intermediate phase of weak survival if and only if the graph is nonamenable. No such simple analysis holds more generally, and it is known that the nonamenability equivalence does not extend to general connected graphs of bounded degree (although we observe that it does hold for such graphs if the branching random walk is modified in a certain natural way). The most important general class of (bounded degree, connected) graphs for which it is thought that the equivalence may hold is that of quasi-transitive graphs: we show that this is indeed the case.

Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then connects pairs of points by an edge if they are within a fixed distance of one another. In addition to giving rise to a range of basic theoretical questions, this class of random graphs has been a central analytical tool in the wireless networking community.

For many of the primary applications of wireless networks, however, the underlying environment has a large number of obstacles, and communication can only take place among nodes when they are close in space and when they have line-of-sight access to one another – consider, for example, urban settings or large indoor environments. In such domains, the standard model of random geometric graphs is not a good approximation of the true constraints, since it is not designed to capture the line-of-sight restrictions.

Here we propose a random-graph model incorporating both range limitations and line-of-sight constraints, and we prove asymptotically tight results for k-connectivity. Specifically, we consider points placed randomly on a grid (or torus), such that each node can see up to a fixed distance along the row and column it belongs to. (We think of the rows and columns as ‘streets’ and ‘avenues’ among a regularly spaced array of obstructions.) Further, we show that when the probability of node placement is a constant factor larger than the threshold for connectivity, near-shortest paths between pairs of nodes can be found, with high probability, by an algorithm using only local information. In addition to analysing connectivity and k-connectivity, we also study the emergence of a giant component, as well an approximation question, in which we seek to connect a set of given nodes in such an environment by adding a small set of additional ‘relay’ nodes.

In the group testing problem the aim is to identify a small set of k ⁓ nθ infected individuals out of a population size n, 0 < θ < 1. We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result if and only if at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition minf for non-adaptive group testing, where all tests are conducted in parallel. Thus with more than minf tests the infected individuals can be identified in polynomial time with high probability, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages.

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

Given an r-graph F, an r-graph G is called weakly F-saturated if the edges missing from G can be added, one at a time, in some order, each extra edge creating a new copy of F. Let w-sat(n, F) be the minimal size of a weakly F-saturated graph of order n. We compute the w-sat function for a wide class of r-graphs called pyramids: these include many examples for which the w-sat function was known, as well as many new examples, such as the computation of w-sat(n,Ks + Kt), and enable us to prove a conjecture of Tuza.

Our main technique, developed from ideas of Kalai, is based on matroids derived from exterior algebra. We prove that if it succeeds for some graphs then the same is true for the ‘cones’ and ‘joins’ of such graphs, so that the w-sat function can be computed for many graphs that are built up from certain elementary graphs by these operations.

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

A generalization of the random assignment problem asks the expected cost of the minimum-cost matching of cardinality k in a complete bipartite graph Km,n, with independent random edge weights. With weights drawn from the exponential distribution with intensity 1, the answer has been conjectured to be

Σi,j≥0, i+j<k1/(m−i)(n−j).

Here, we prove the conjecture for k [les ] 4, k = m = 5, and k = m = n = 6, using a structured, automated proof technique that results in proofs with relatively few cases. The method yields not only the minimum assignment cost's expectation but the Laplace transform of its distribution as well. From the Laplace transform we compute the variance in these cases, and conjecture that, with k = m = n → ∞, the variance is 2/n + O(log n/n2). We also include some asymptotic properties of the expectation and variance when k is fixed.

Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k − 1)-degree of H is at least ⌊n/k⌋, then H contains a matching with ⌊n/k⌋ edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k − 1)-degree n/k + O(log n) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.

It is well known that a graph with m edges can be made triangle-free by removing (slightly less than) m/2 edges. On the other hand, there are many classes of graphs which are hard to make triangle-free, in the sense that it is necessary to remove roughly m/2 edges in order to eliminate all triangles.

We prove that dense graphs that are hard to make triangle-free have a large packing of pairwise edge-disjoint triangles. In particular, they have more than m(1/4+cβ) pairwise edge-disjoint triangles where β is the density of the graph and c ≥ is an absolute constant. This improves upon a previous m(1/4−o(1)) bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. We conjecture that such graphs have an asymptotically optimal triangle packing of size m(1/3−o(1)).

We extend our result from triangles to larger cliques and odd cycles.

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 consider a random permutation drawn from the set of 132-avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by nλ(σ)/2, where λ(σ) is the length of σ plus the number of descents. The limit is not normal, and can be expressed as a functional of a Brownian excursion. Moments can be found by recursion.