We use the probabilistic method to obtain versions of the colourful Carathéodory theorem and Tverberg's theorem with tolerance.

In particular, we give bounds for the smallest integer N = N(t,d,r) such that for any N points in ℝd, there is a partition of them into r parts for which the following condition holds: after removing any t points from the set, the convex hulls of what is left in each part intersect.

We prove a bound N = rt + O($\sqrt{t}$) for fixed r,d which is polynomial in each parameters. Our bounds extend to colourful versions of Tverberg's theorem, as well as Reay-type variations of this theorem.

In 1981 Beck and Fiala proved an upper bound for the discrepancy of a set system of degree d that is independent of the size of the ground set. In the intervening years the bound has been decreased from 2d − 2 to 2d − 4. We improve the bound to 2d − log*d.

We show that there are graphs with n vertices containing no K5,5 which have about n7/4 edges, thus proving that ex(n, K5,5) ≥ (1 + o(1))n7/4. This bound gives an asymptotic improvement to the known lower bounds on ex(n, Kt, s) for t = 5 when 5 ≤ s ≤ 12, and t = 6 when 6 ≤ s ≤ 8.

In a balls-in-bins process with feedback, balls are sequentially thrown into bins so that the probability that a bin with n balls obtains the next ball is proportional to f(n) for some function f. A commonly studied case where there are two bins and f(n) = np for p > 0, and our goal is to study the fine behaviour of this process with two bins and a large initial number t of balls. Perhaps surprisingly, Brownian Motions are an essential part of both our proofs.

For p > 1/2, it was known that with probability 1 one of the bins will lead the process at all large enough times. We show that if the first bin starts with balls (for constant λ∈ℝ), the probability that it always or eventually leads has a non-trivial limit depending on λ.

For p ≤ 1/2, it was known that with probability 1 the bins will alternate in leadership. We show, however, that if the initial fraction of balls in one of the bins is > 1/2, the time until it is overtaken by the remaining bin scales like Θ(t1+1/(1-2p)) for p < 1/2 and exp(Θ(t)) for p = 1/2. In fact, the overtaking time has a non-trivial distribution around the scaling factor, which we determine explicitly.

Our proofs use a continuous-time embedding of the balls-in-bins process (due to Rubin) and a non-standard approximation of the process by Brownian Motion. The techniques presented also extend to more general functions f.

The bond percolation critical probability of the Kagomé lattice is greater than 0.5209 and less than 0.5291. The proof of these bounds uses the substitution method, comparing the percolative behaviour of the Kagomé lattice bond model with that of the exactly solved hexagonal lattice bond model via stochastic ordering.

Let A and B be two affinely generating sets of ℤ2n. As usual, we denote their Minkowski sum by A+B. How small can A+B be, given the cardinalities of A and B? We give a tight answer to this question. Our bound is attained when both A and B are unions of cosets of a certain subgroup of ℤ2n. These cosets are arranged as Hamming balls, the smaller of which has radius 1.

By similar methods, we re-prove the Freiman–Ruzsa theorem in ℤ2n, with an optimal upper bound. Denote by F(K) the maximal spanning constant |〈 A 〉|/|A| over all subsets A ⊆ ℤ2n with doubling constant |A+A|/|A| ≤ K. We explicitly calculate F(K), and in particular show that 4K/4K ≤ F(K)⋅(1+o(1)) ≤ 4K/2K. This improves the estimate F(K) = poly(K)4K, found recently by Green and Tao [17] and by Konyagin [23].

In this paper we are concerned with the following conjecture.

Conjecture. For any positive integers n and k satisfying k < n, and any sequence a1, a2, … ak of not necessarily distinct elements of Zn, there exists a permutation π ∈ Sk such that the elements aπ(i)+i are all distinct modulo n.

We prove this conjecture when 2k [les ] n+1. We then apply this result to tree embeddings. Specifically, we show that, if T is a tree with n edges and radius r, then T decomposes Kt for some t [les ] 32(2r+4)n2+1.

Recently, Galvin [7] proved that every k-edge-colourable bipartite multigraph is k-edge-choosable. In particular, for a bipartite multigraph G, . Here we give a brief self-contained proof of this result.

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

We consider large random graphs with prescribed degrees, as generated by the configuration model. In the regime where the empirical degree distribution approaches a limit μ with finite mean, we establish the systematic convergence of a broad class of graph parameters that includes the independence number, the maximum cut size, the logarithm of the Tutte polynomial, and the free energy of the anti-ferromagnetic Ising and Potts models. Contrary to previous works, our results are not a priori limited to the free energy of some prescribed graphical model. They apply more generally to any additive, Lipschitz and concave graph parameter. In addition, the corresponding limits are shown to be Lipschitz and concave in the degree distribution μ. This considerably extends the applicability of the celebrated interpolation method, introduced in the context of spin glasses, and recently related to the challenging question of right-convergence of sparse graphs.

Let S be a closed surface with boundary ∂S and let G be a graph. Let K ⊆ G be a subgraph embedded in S such that ∂S ⊆ K. An embedding extension of K to G is an embedding of G in S that coincides on K with the given embedding of K. Minimal obstructions for the existence of embedding extensions are classified in cases when S is the disk or the cylinder. Linear time algorithms are presented that either find an embedding extension, or return an obstruction to the existence of extensions. These results are to be used as the corner stones in the design of linear time algorithms for the embeddability of graphs in an arbitrary surface and for solving more general embedding extension problems.

We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does so within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis also covers monotone subsequences.

For a random permutation of $n$ objects, as $n \to \infty$, the process giving the proportion of elements in the longest cycle, the second-longest cycle, and so on, converges in distribution to the Poisson–Dirichlet process with parameter 1. This was proved in 1977 by Kingman and by Vershik and Schmidt. For soft reasons, this is equivalent to the statement that the random permutations and the Poisson–Dirichlet process can be coupled so that zero is the limit of the expected $\ell_1$ distance between the process of cycle length proportions and the Poisson–Dirichlet process. We investigate how rapid this metric convergence can be, and in doing so, give two new proofs of the distributional convergence.

One of the couplings we consider has an analogue for the prime factorizations of a uniformly distributed random integer, and these couplings rely on the ‘scale-invariant spacing lemma’ for the scale-invariant Poisson processes, proved in this paper.

The random assignment problem is to minimize the cost of an assignment in an $n\times n$ matrix of random costs. In this paper we study the problem for some integer-valued cost distributions. We consider both uniform distributions on $1,2,\dots ,m$, for $m=n$ or $n^2$, and random permutations of $1,2,\dots ,n$ for each row, or of $1,2,\dots ,n^2$ for the whole matrix. We find the limit of the expected cost for the ‘$n^2$’ cases, and prove bounds for the ‘$n$’ cases. This is done by simple coupling arguments together with recent results of Aldous for the continuous case. We also present a simulation study of these cases.

Given non-negative weights wS on the k-subsets S of a km-element set V, we consider the sum of the products wS1 ⋅⋅⋅ wSm over all partitions V = S1 ∪ ⋅⋅⋅ ∪Sm into pairwise disjoint k-subsets Si. When the weights wS are positive and within a constant factor of each other, fixed in advance, we present a simple polynomial-time algorithm to approximate the sum within a polynomial in m factor. In the process, we obtain higher-dimensional versions of the van der Waerden and Bregman–Minc bounds for permanents. We also discuss applications to counting of perfect and nearly perfect matchings in hypergraphs.

There is a simple greedy algorithm for seeking large values of a function f defined on the vertices of the binary tree. Modeling f as a random function whose increments along edges are i.i.d., we show that (under a natural assumption) the values found by the greedy algorithm grow linearly in time, with rate specified in terms of a fixed-point identity for distributions.

We study the ‘rank 1 case’ of the inhomogeneous random graph model. In the subcritical case we derive an exact formula for the asymptotic size of the largest connected component scaled to log n. This result complements the corresponding known result in the supercritical case. We provide some examples of applications of the derived formula.

We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that

$$ P(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) $$

Two-sided bounds are explored for concentration functions and Rényi entropies in the class of discrete log-concave probability distributions. They are used to derive certain variants of the entropy power inequalities.

A simple explicit construction is provided of a partition-valued fragmentation process whose distribution on partitions of [n] = 1,. . .,n at time θ ≥ 0 is governed by the Ewens sampling formula with parameter θ. These partition-valued processes are exchangeable and consistent, as n varies. They can be derived by uniform sampling from a corresponding mass fragmentation process defined by cutting a unit interval at the points of a Poisson process with intensity θx−1dx on/mathbbR+, arranged to beintensifying as θ increases.