Let P be a monotone increasing graph property, let G = (V, E) be a graph, and let q be a positive integer. In this paper, we study the (1: q) Maker–Breaker game, played on the edges of G, in which Maker's goal is to build a graph that satisfies the property P. It is clear that in order for Maker to have a chance of winning, G itself must satisfy P. We prove that if G satisfies P in some strong sense, that is, if one has to delete sufficiently many edges from G in order to obtain a graph that does not satisfy P, then Maker has a winning strategy for this game. We also consider a different notion of satisfying some property in a strong sense, which is motivated by a problem of Duffus, Łuczak and Rödl [6].

We consider the k-party communication complexity of the problem of determining if a word w is of the form , for fixed letters . Using the well-known theorem of Hindman (a Ramsey-type result about finite subsets of natural numbers), we prove that for and 5 the communication complexity of the problem increases with the length of the word w.

A detachment of a graph $G$ is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. In this paper we consider the question of whether a graph $H$ is a detachment of some complete graph $K_n$. When $H$ is large and restricted to belong to certain classes of graphs, for example bounded degree planar triangle-free graphs, we obtain necessary and sufficient conditions which give a complete characterization.

A harmonious colouring of a simple graph $G$ is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number$h(G)$ is the least number of colours in such a colouring. The results on detachments of complete graphs give exact results on harmonious chromatic number for many classes of graphs, as well as algorithmic results.

For any partition of $\{1, 2, \ldots{,}\, n\}$ we define its increments$X_i, 1 \leq i \leq n$ by $X_i = 1$ if $i$ is the smallest element in the partition block that contains it, $X_i = 0$ otherwise. We prove that for partially exchangeable random partitions (where the probability of a partition depends only on its block sizes in order of appearance), the law of the increments uniquely determines the law of the partition. One consequence is that the Chinese Restaurant Process CRP($\theta$) (the partition with distribution given by the Ewens sampling formula with parameter $\theta$) is the only exchangeable random partition with independent increments.

We generalize a minimal 3-connectivity result of Halin from graphs to binary matroids. As applications of this theorem to minimally 3-connected matroids, we obtain new results and short inductive proofs of results of Oxley and Wu. We also give new short inductive proofs of results of Dirac and Halin on minimally k-connected graphs for k ∈ {2,3}.

For a subgroup W of the hyperoctahedral group On which is generated by reflections, we consider the linear dependence matroid MW on the column vectors corresponding to the reflections in W. We determine all possible automorphism groups of MW and determine when W ≅ = Aut(MW). This allows us to connect combinatorial and geometric symmetry. Applications to zonotopes are also considered. Signed graphs are used as a tool for constructing the automorphisms.

In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. The evolution of the rescaled size of the largest component in such variations of the Erdős–Rényi random graph process has recently received considerable attention, in particular for Bollobás's ‘product rule’. In this paper we establish the following result for rules such as the product rule: the limit of the rescaled size of the ‘giant’ component exists and is continuous provided that a certain system of differential equations has a unique solution. In fact, our result applies to a very large class of Achlioptas-like processes.

Our proof relies on a general idea which relates the evolution of stochastic processes to an associated system of differential equations. Provided that the latter has a unique solution, our approach shows that certain discrete quantities converge (after appropriate rescaling) to this solution.

Suppose that [Cscr ]={cij[ratio ]i, j[ges ]1} is a collection of i.i.d. nonnegative continuous random variables and suppose T is a rooted, directed tree on vertices labelled 1,2,[ctdot ],n. Then the ‘cost’ of T is defined to be c(T)=[sum ] (i,j)∈Tcij, where (i, j) denotes the directed edge from i to j in the tree T. Let Tn denote the ‘optimal’ tree, i.e. c(Tn) =min{c(T)[ratio ]T is a directed, rooted tree in with n vertices}. We establish general conditions on the asymptotic behaviour of the moments of the order statistics of the variables c11, c12, [ctdot ], cin which guarantee the existence of sequences {an}, {bn}, and {dn} such that b−1n (c(Tn)−an) →N(0, 1) in distribution, d−1nc(Tn)→1 in probability, and d−1nE(c(Tn))→1 as n→∞, and we explicitly determine these sequences. The proofs of the main results rely upon the properties of general random mappings of the set {1, 2, [ctdot ], n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.

We propose a counting dimension for subsets of $\mathbb{Z}$ and prove that, under certain conditions on E,F ⊂ $\mathbb{Z}$, for Lebesgue almost every λ ∈ $\mathbb{R}$ the counting dimension of E + ⌊λF⌋ is at least the minimum between 1 and the sum of the counting dimensions of E and F. Furthermore, if the sum of the counting dimensions of E and F is larger than 1, then E + ⌊λF⌋ has positive upper Banach density for Lebesgue almost every λ ∈ $\mathbb{R}$. The result has direct consequences when E,F are arithmetic sets, e.g., the integer values of a polynomial with integer coefficients.

This paper is devoted to an online variant of the minimum spanning tree problem in randomly weighted graphs. We assume that the input graph is complete and the edge weights are uniformly distributed over [0,1]. An algorithm receives the edges one by one and has to decide immediately whether to include the current edge into the spanning tree or to reject it. The corresponding edge sequence is determined by some adversary. We propose an algorithm which achieves $\mathbb{E}[ALG]/\mathbb{E}[OPT]=O(1)$ and $\mathbb{E}[ALG/OPT]=O(1)$ against a fair adaptive adversary, i.e., an adversary which determines the edge order online and is fair in a sense that he does not know more about the edge weights than the algorithm. Furthermore, we prove that no online algorithm performs better than $\mathbb{E}[ALG]/\mathbb{E}[OPT]=\Omega(\log n)$ if the adversary knows the edge weights in advance. This lower bound is tight, since there is an algorithm which yields $\mathbb{E}[ALG]/\mathbb{E}[OPT]=O(\log n)$ against the strongest-imaginable adversary.

Let c(G) be the smallest number of edges we have to test in order to determine an unknown acyclic orientation of the given graph G in the worst case. For example, if G is the complete graph on n vertices, then c(G) is the smallest number of comparisons needed to sort n numbers.

We prove that c(G) ≤ (1/4 + o(1))n2 for any graph G on n vertices, answering in the affirmative a question of Aigner, Triesch and Tuza [Discrete Mathematics144 (1995) 3–10]. Also, we show that, for every ϵ > 0, it is NP-hard to approximate the parameter c(G) within a multiplicative factor 74/73 − ϵ.

A tight Hamilton cycle in a k-uniform hypergraph (k-graph) G is a cyclic ordering of the vertices of G such that every set of k consecutive vertices in the ordering forms an edge. Rödl, Ruciński and Szemerédi proved that for $k\ge 3$ , every k-graph on n vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such k-graphs is ${\exp(n\ln n-\Theta(n))}$ . As a corollary, we obtain a similar estimate on the number of Hamilton ${\ell}$ -cycles in such k-graphs for all ${\ell\in\{0,\ldots,k-1\}}$ , which makes progress on a question of Ferber, Krivelevich and Sudakov.

In this paper, we study certain pairings which are defined as follows: if A and B are finite subsets of an arbitrary group, a Wakeford–Fan–Losonczy pairing from B onto A is a bijection φ : B → A such that bφ(b) ∉ A, for every b ∈ B. The number of such pairings is denoted by μ(B, A).

We investigate the quantity μ(B, A) for A and B, two finite subsets of an arbitrary group satisfying 1 ∉ B, |A| = |B|, and the fact that the order of every element of B is ≥ |B| + 1. Extending earlier results, we show that in this case, μ(B, A) is never equal to 0. Furthermore we prove an explicit lower bound on μ(B, A) in terms of |B| and the cardinality of the group generated by B, which is valid unless A and B have a special form explicitly described. In the case A = B, our bound holds unless B is a translate of a progression.

Given a set of s points and a set of n2 lines in three-dimensional Euclidean space such that each line is incident to n points but no n lines are coplanar, we show that s = Ω(n11/4). This is the first non-trivial answer to a question recently posed by Jean Bourgain.

We prove that for all $\alpha,c>0$ and for all bipartite graphs $H$, all but at most $\alpha n$ vertices of every $cn$-regular graph $G$ whose order $n$ is sufficiently large can be covered by vertex-disjoint copies of $H$. If the vertex classes of $H$ have different size, then even all but a constant number of vertices of $G$ can be covered. This implies that for all $c>0$ and all $r\geq 4$ there exists a constant $C$ such that, in every $cn$-regular graph $G$, all but at most $C$ vertices can be covered by vertex-disjoint subdivisions of $K_r$. We also show that for $r=4,5$ one can take $C=0$.

We present an elementary proof that if $A$ is a finite set of numbers, and the sumset $A+_GA$ is small, $|A+_GA|\leq c|A|$, along a dense graph $G$, then $A$ contains $k$-term arithmetic progressions.

For any fixed l < k we present families of asymptotically good packings and coverings of the l-subsets of an n-element set by k-subsets, and an algorithm that, given a natural number i, finds the ith k-subset of the family in time and space polynomial in log n.

We develop a method to compute the generating function of the number of vertices inside certain regions of the Uniform Infinite Planar Triangulation (UIPT). The computations are mostly combinatorial in flavour and the main tool is the decomposition of the UIPT into layers, called the skeleton decomposition, introduced by Krikun [20]. In particular, we get explicit formulas for the generating functions of the number of vertices inside hulls (or completed metric balls) centred around the root, and the number of vertices inside geodesic slices of these hulls. We also recover known results about the scaling limit of the volume of hulls previously obtained by Curien and Le Gall by studying the peeling process of the UIPT in [17].

Let G be an abelian group of cardinality n, where hcf(n, 6) = 1, and let A be a random subset of G. Form a graph ΓA on vertex set G by joining x to y if and only if x + y ∈ A. Then, with high probability as n → ∞, the chromatic number χ(ΓA) is at most $(1 + o(1))\tfrac{n}{2\log_2 n}$. This is asymptotically sharp when G = ℤ/nℤ, n prime.

We consider connectivity properties and asymptotic slopes for certain random directed graphs on ℤ2 in which the set of points $\mathcal{C}_o$ that the origin connects to is always infinite. We obtain conditions under which the complement of $\mathcal{C}_o$ has no infinite connected component. Applying these results to one of the most interesting such models leads to an improved lower bound for the critical occupation probability for oriented site percolation on the triangular lattice in two dimensions.