We derive here the Friedland–Tverberg inequality for positive hyperbolic polynomials. This inequality is applied to give lower bounds for the number of matchings in r-regular bipartite graphs. It is shown that some of these bounds are asymptotically sharp. We improve the known lower bound for the three-dimensional monomer–dimer entropy.

Semple and Welsh [5] introduced the concept of correlated matroids, which relate to conjectures by Grimmett and Winkler [2], and Pemantle [4], respectively, that the uniformly random forest and the uniformly random connected subgraph of a finite graph have the edge-negative-association property. In this paper, we extend results of Semple and Welsh, and show that the Grimmett and Winkler, and Pemantle conjectures are equivalent to statements about correlated graphic matroids. We also answer some open questions raised in [5] regarding correlated matroids, and in particular show that the 2-sum of correlated matroids is correlated.

Semi-graphoids are combinatorial structures that arise in statistical learning theory. They are equivalent to convex rank tests and to polyhedral fans that coarsen the reflection arrangement of the symmetric group Sn. In this paper we resolve two problems on semi-graphoids posed in Studený's book (2005), and we answer a related question of Postnikov, Reiner and Williams on generalized permutohedra. We also study the semigroup and the toric ideal associated with semi-graphoids.

Let n ≥ 1 be an integer. Given a vector a=(a1,. . ,an)∈, write (the ‘projection of a onto the positive orthant’). For a set A⊆ put A+:={a+: a ∈ A} and A−A:={a−b: a, b ∈ A}. Improving previously known bounds, we show that |(A−A)+| ≥ |A|3/5/6 for any finite set A⊆, and that |(A−A)+| ≥ c|A|6/11/(log |A|)2/11 with an absolute constant c>0 for any finite set A⊆ such that |A| ≥ 2.

A graph construction game is a Maker–Breaker game. Maker and Breaker take turns in choosing previously unoccupied edges of the complete graph KN. Maker's aim is to claim a copy of a given target graph G while Breaker's aim is to prevent Maker from doing so. In this paper we show that if G is a d-degenerate graph on n vertices and N > d1122d+9n, then Maker can claim a copy of G in at most d1122d+7n rounds. We also discuss a lower bound on the number of rounds Maker needs to win, and the gap between these bounds.

We consider the number of vertices that must be removed from a graph G in order that the remaining subgraph have no component with more than k vertices. Our principal observation is that, if G is a sparse random graph or a random regular graph on n vertices with n → ∞, then the number in question is essentially the same for all values of k that satisfy both k → ∞ and k =o(n).

We use a greedy probabilistic method to prove that, for every ε > 0, every m × n Latin rectangle on n symbols has an orthogonal mate, where m = (1 − ε)n. That is, we show the existence of a second Latin rectangle such that no pair of the mn cells receives the same pair of symbols in the two rectangles.

We show that for each α>0 every sufficiently large oriented graph G with δ+(G), δ−(G)≥3|G|/8+α|G| contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen [21]. In fact, we prove the stronger result that G is still Hamiltonian if δ(G)+δ+(G)+δ−(G)≥3|G|/2 + α|G|. Up to the term α|G|, this confirms a conjecture of Häggkvist [10]. We also prove an Ore-type theorem for oriented graphs.

Babai and Sós have asked whether there exists a constant c > 0 such that every finite group G has a product-free subset of size at least c|G|: that is, a subset X that does not contain three elements x, y and z with xy = z. In this paper we show that the answer is no. Moreover, we give a simple sufficient condition for a group not to have any large product-free subset.

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.

A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.

The number of spanning trees in the giant component of the random graph (n, c/n) (c > 1) grows like exp{m(f(c)+o(1))} as n → ∞, where m is the number of vertices in the giant component. The function f is not known explicitly, but we show that it is strictly increasing and infinitely differentiable. Moreover, we give an explicit lower bound on f′(c). A key lemma is the following. Let PGW(λ) denote a Galton–Watson tree having Poisson offspring distribution with parameter λ. Suppose that λ*>λ>1. We show that PGW(λ*) conditioned to survive forever stochastically dominates PGW(λ) conditioned to survive forever.

An induced forest of a graph G is an acyclic induced subgraph of G. The present paper is devoted to the analysis of a simple randomized algorithm that grows an induced forest in a regular graph. The expected size of the forest it outputs provides a lower bound on the maximum number of vertices in an induced forest of G. When the girth is large and the degree is at least 4, our bound coincides with the best bound known to hold asymptotically almost surely for random regular graphs. This results in an alternative proof for the random case.

Both the hopcount HN (the number of links) and the weight WN (the sum of the weights on links) of the shortest path between two arbitrary nodes in the complete graph KN with i.i.d. exponential link weights is computed. We consider the joint distribution of the pair (HN, WN) and derive, after proper scaling, the joint limiting distribution. One of the results is that HN and WN, properly scaled, are asymptotically independent.

Let G denote a finite abelian group of order n and Davenport constant D, and put m = n + D − 1. Let x = (x1,. . .,xm) ∈ Gm. Gao's theorem states that there is a reordering (xj1, . . ., xjm) of x such that

Let w = (x1, . . ., wm) ∈ ℤm. As a corollary of the main result, we show that there are reorderings (xj1, . . ., xjm) of x and (wk1, . . ., wkm) of w, such that where xj1 is the most repeated value in x. For w = (1, . . ., 1), this result reduces to Gao's theorem.

The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold λc for the emergence of a non-trivial k-core in the random graph G(n, λ/n), and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the edges. As an example, we study the k-core in a certain power-law or ‘scale-free’ graph with a parameter c controlling the overall density of edges. For each k ≥ 3, we find the threshold value of c at which the k-core emerges, and the fraction of vertices in the k-core when c is ϵ above the threshold. In contrast to G(n, λ/n), this fraction tends to 0 as ϵ→0.

Given a digraph D, let δ0(D) := min{δ+(D), δ−(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with δ0(D)≥n/2 + l −1 is l-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [17]. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e., that for every sequence s1, . . ., sk of distinct vertices of D there is a directed cycle which encounters s1, . . ., sk in this order. This result will be used in [16].

In a random passive intersection graph model the edges of the graph are decided by taking the union of a fixed number of cliques of random size. We give conditions for a random passive intersection graph model to have a limiting vertex degree distribution, in particular to have a Poisson limiting vertex degree distribution. We give related conditions which, in addition to implying a limiting vertex degree distribution, imply convergence of expectation.

Let G be a graph with n vertices, and let k be an integer dividing n. G is said to be strongly k-colourable if, for every partition of V(G) into disjoint sets V1 ∪ ··· ∪ Vr, all of size exactly k, there exists a proper vertex k-colouring of G with each colour appearing exactly once in each Vi. In the case when k does not divide n, G is defined to be strongly k-colourable if the graph obtained by adding isolated vertices is strongly k-colourable. The strong chromatic number of G is the minimum k for which G is strongly k-colourable. In this paper, we study the behaviour of this parameter for the random graph Gn,p. In the dense case when p ≫ n−1/3, we prove that the strong chromatic number is a.s. concentrated on one value Δ + 1, where Δ is the maximum degree of the graph. We also obtain several weaker results for sparse random graphs.

Zeilberger's enumeration schemes can be used to completely automate the enumeration of many permutation classes. We extend his enumeration schemes so that they apply to many more permutation classes and describe the Maple package WilfPlus, which implements this process. We also compare enumeration schemes to three other systematic enumeration techniques: generating trees, substitution decompositions, and the insertion encoding.