It is known that w.h.p. the hitting time τ2σ for the random graph process to have minimum degree 2σ coincides with the hitting time for σ edge-disjoint Hamilton cycles [4, 9, 13]. In this paper we prove an online version of this property. We show that, for a fixed integer σ ⩾ 2, if random edges of Kn are presented one by one then w.h.p. it is possible to colour the edges online with σ colours so that at time τ2σ each colour class is Hamiltonian.

Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called Pólya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results.

Thomas conjectured that there is an absolute constant c such that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour every G ∈ with at most χ(G) + c colours. We introduce a parameter ρ(), called the degenerate value of , which is defined to be the smallest r such that every G ∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that is r-degenerate. Although the existence of one global bound for the degenerate values of all proper minor-closed classes would imply Thomas's conjecture, we prove that the values ρ() can be made arbitrarily large. The problem lies in the clique sum operation. As our main result, we show that excluding a planar graph with a fixed number of apex vertices gives rise to a minor-closed class with small degenerate value. As corollaries, we obtain that (i) the degenerate value of every class of graphs of bounded local tree-width is at most 6, and (ii) the degenerate value of the class of Kn-minor-free graphs is at most n + 1. These results give rise to P-time approximation algorithms for colouring any graph in these classes within an error of at most 7 and n + 2 of its chromatic number, respectively.

In generalisation of the beta law obtained under the GEM/Poisson–Dirichlet distribution in Hirth [12] we undertake here an analogous construction which results in the Dirichlet law. Our proof makes use of Hoppe's Pólya-like urn model in population genetics.

In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.

We analyse the performance of three related approximation algorithms for the uncapacitated facility location problem (from Jain, Mahdian, Markakis, Saberi and Vazirani (2003) and Mahdian, Ye and Zhang (2002)) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

To bound the probability of a union of n events from a single set of events, Bonferroni inequalities are sometimes used. There are sharper bounds which are called Sobel–Uppuluri–Galambos inequalities. When two (or more) sets of events are involved, bounds are considered on the probability of intersection of several such unions, one union from each set. We present a method for unified treatment of bivariate lower and upper bounds in this note. The lower bounds obtained are new and at least as good as lower bounds appearing in the literature so far. The upper bounds coincide with existing bivariate Sobel–Uppuluri–Galambos type upper bounds derived by the method of indicator functions. A numerical example is given to illustrate that the new lower bounds can be strictly better than existing ones.

The problem we consider here is based on the following question posed by François Jaeger in 1981 at a combinatorics meeting in Eger (Hungary):

Pursuit-evasion games, such as the game of Revolutionaries and Spies, are a simplified model for network security. In the game we consider in this paper, a team of r revolutionaries tries to hold an unguarded meeting consisting of m revolutionaries. A team of s spies wants to prevent this forever. For given r and m, the minimum number of spies required to win on a graph G is the spy number σ(G,r,m). We present asymptotic results for the game played on random graphs G(n,p) for a large range of p = p(n), r=r(n), and m=m(n). The behaviour of the spy number is analysed completely for dense graphs (that is, graphs with average degree at least n1/2+ε for some ε > 0). For sparser graphs, some bounds are provided.

We investigate the list packing number of a graph, the least $k$ such that there are always $k$ disjoint proper list-colourings whenever we have lists all of size $k$ associated to the vertices. We are curious how the behaviour of the list packing number contrasts with that of the list chromatic number, particularly in the context of bounded degree graphs. The main question we pursue is whether every graph with maximum degree $\Delta$ has list packing number at most $\Delta +1$. Our results highlight the subtleties of list packing and the barriers to, for example, pursuing a Brooks’-type theorem for the list packing number.

Consider a finite alphabet Ω and strings consisting of elements from Ω. For a given string w, let cor(w) denote the autocorrelation, which can be seen as a measure of the amount of overlap in w. Furthermore, let aw(n) be the number of strings of length n that do not contain w as a substring. Eriksson [4] stated the following conjecture: if cor(w)>cor(w′), thenaw(n)>aw′(n) from the first n where equality no longer holds. We prove that this is true if [mid ]Ω[mid ][ges ]3, by giving a lower bound for aw(n)−aw′(n).

Erdős asked if, for every pair of positive integers g and k, there exists a graph H having girth (H) = k and the property that every r-colouring of the edges of H yields a monochromatic cycle Ck. The existence of such graphs H was confirmed by the third author and Ruciński.

We consider the related numerical problem of estimating the order of the smallest graph H with this property for given integers r and k. We show that there exists a graph H on R10k2; k15k3 vertices (where R = R(Ck; r) is the r-colour Ramsey number for the cycle Ck) having girth (H) = k and the Ramsey property that every r-colouring of the edges of H yields a monochromatic Ck Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered.

Given an undirected graph G, let us randomly orient G by tossing independent (possibly biased) coins, one for each edge of G. Writing a → b for the event that there exists a directed path from a vertex a to a vertex b in such a random orientation, we prove that for any three vertices s, a and b of G, we have ℙ(s → a ∩ s → b) ⩾ ℙ(s → a) ℙ(s → b).

We consider a random digraph Din, out(n) on vertices 1, …, n, where, for each vertex v, we choose at random one of the n possible arcs with head v and one of the n possible arcs with tail v. We show that the expected size of the largest component of Din, out is .

For any c ≥ 2, a c-strong colouring of the hypergraph G is an assignment of colours to the vertices of G such that, for every edge e of G, the vertices of e are coloured by at least min{c,|e|} distinct colours. The hypergraph G is t-intersecting if every two edges of G have at least t vertices in common.

A natural variant of a question of Erdős and Lovász is: For fixed c ≥ 2 and t ≥ 1, what is the minimum number of colours that is sufficient to c-strong colour any t-intersecting hypergraphs? The purpose of this note is to describe some open problems related to this question.

Ramsey numbers for matroids, which mimic properties of Ramsey numbers for graphs, have been denned as follows. Let k and l be positive integers. Then n(k, l) is the least positive integer n such that every connected matroid with n elements contains either a circuit with at least k elements or a cocircuit with at least l elements. We determine the largest known value of these numbers in the sense of maximizing both k and l. We also find extremal matroids with small circuits and cocircuits. Results on matroid connectivity, geometry, and extremal matroid theory are used here.

A tournament T on a set V of n players is an orientation of the edges of the complete graph Kn on V; T will be called a random tournament if the directions of these edges are determined by a sequence {Yj[ratio ]j = 1, …, (n2)} of independent coin flips. If (y, x) is an edge in a (random) tournament, we say that y beats x. A set A ⊂ V, |A| = k, is said to be beaten if there exists a player y ∉ A such that y beats x for each x ∈ A. If such a y does not exist, we say that A is unbeaten. A (random) tournament on V is said to have property Sk if each k-element subset of V is beaten. In this paper, we use the Stein–Chen method to show that the probability distribution of the number W0 of unbeaten k-subsets of V can be well-approximated by that of a Poisson random variable with the same mean; an improved condition for the existence of tournaments with property Sk is derived as a corollary. A multivariate version of this result is proved next: with Wj representing the number of k-subsets that are beaten by precisely j external vertices, j = 0, 1, …, b, it is shown that the joint distribution of (W0, W1, …, Wb) can be approximated by a multidimensional Poisson vector with independent components, provided that b is not too large.

We compute the large N limit of the partition function of the Euclidean Yang–Mills measure on orientable compact surfaces with genus $g\geqslant 1$ and non-orientable compact surfaces with genus $g\geqslant 2$ , with structure group the unitary group ${\mathrm U}(N)$ or special unitary group ${\mathrm{SU}}(N)$ . Our proofs are based on asymptotic representation theory: more specifically, we control the dimension and Casimir number of irreducible representations of ${\mathrm U}(N)$ and ${\mathrm{SU}}(N)$ when N tends to infinity. Our main technical tool, involving ‘almost flat’ Young diagram, makes rigorous the arguments used by Gross and Taylor (1993, Nuclear Phys. B400(1–3) 181–208) in the setting of QCD, and in some cases, we recover formulae given by Douglas (1995, Quantum Field Theory and String Theory (Cargèse, 1993), Vol. 328 of NATO Advanced Science Institutes Series B: Physics, Plenum, New York, pp. 119–135) and Rusakov (1993, Phys. Lett. B303(1) 95–98).

Given a set $A\subset\mathbb{Z}_{N}$, we say that a function $f\colon A \to \mathbb{Z}_{N}$ is a Freiman homomorphism if f(a)+f(b)=f(c)+f(d) whenever a,b,c,d ∈ A satisfy a+b=c+d. This notion was introduced by Freiman in the 1970s, and plays an important role in the field of additive combinatorics. We say that A is linear if the only Freiman homomorphisms are functions of the form f(x) = ax+b.

Suppose the elements of A are chosen independently at random, each with probability p. We shall look at the following question: For which values of p=p(N) is A linear with high probability as N → ∞? We show that if p=(2logN − ω(N))1/3N−2/3, where ω(N) → ∞ as N → ∞, then A is not linear with high probability, whereas if p=N−1/2+ε for any ε>0 then A is linear with high probability.

Let $\mathcal{F}$ = {F1, F2,. . ., Fn} be a family of n sets on a ground set S, such as a family of balls in ℝd. For every finite measure μ on S, such that the sets of $\mathcal{F}$ are measurable, the classical inclusion–exclusion formula asserts that

$\[\mu(F_1\cup F_2\cup\cdots\cup F_n)=\sum_{I:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}\mu\biggl(\bigcap_{i\in I} F_i\biggr),\]$

$\mathcal{F}$

$\mathcal{F}$

$\mathcal{F}$