Consider a randomly oriented graph G = (V, E) and let a, s and b be three distinct vertices in V. We study the correlation between the events {a → s} and {s → b}. We show that, counter-intuitively, when G is the complete graph Kn, n ≥ 5, then the correlation is positive. (It is negative for n = 3 and zero for n = 4.) We briefly discuss and pose problems for the same question on other graphs.

The line graph G of a directed graph G has a vertex for every edge of G and an edge for every path of length 2 in G. In 1967, Knuth used the Matrix Tree Theorem to prove a formula for the number of spanning trees of G, and he asked for a bijective proof [6]. In this paper, we give a bijective proof of Knuth's formula. As a result of this proof, we find a bijection between binary de Bruijn sequences of degree n and binary sequences of length 2n−1. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine [7].

Let I be an independent set drawn from the discrete d-dimensional hypercube Qd = {0, 1}d according to the hard-core distribution with parameter λ > 0 (that is, the distribution in which each independent set I is chosen with probability proportional to λ|I|). We show a sharp transition around λ = 1 in the appearance of I: for λ > 1, min{|I ∩ Ɛ|, |I ∩ |} = 0 asymptotically almost surely, where Ɛ and are the bipartition classes of Qd, whereas for λ < 1, min{|I ∩ Ɛ|, |I ∩ |} is asymptotically almost surely exponential in d. The transition occurs in an interval whose length is of order 1/d.

A key step in the proof is an estimation of Zλ(Qd), the sum over independent sets in Qd with each set I given weight λ|I| (a.k.a. the hard-core partition function). We obtain the asymptotics of Zλ(Qd) for , and nearly matching upper and lower bounds for , extending work of Korshunov and Sapozhenko. These bounds allow us to read off some very specific information about the structure of an independent set drawn according to the hard-core distribution.

We also derive a long-range influence result. For all fixed λ > 0, if I is chosen from the independent sets of Qd according to the hard-core distribution with parameter λ, conditioned on a particular v ∈ Ɛ being in I, then the probability that another vertex w is in I is o(1) for w ∈ but Ω(1) for w ∈ Ɛ.

The asymptotics of 2-colour Ramsey numbers of loose and tight cycles in 3-uniform hypergraphs were recently determined [16, 17]. We address the same problem for Berge cycles and for 3 colours. Our main result is that the 3-colour Ramsey number of a 3-uniform Berge cycle of length n is asymptotic to . The result is proved with the Regularity Lemma via the existence of a monochromatic connected matching covering asymptotically 4n/5 vertices in the multicoloured 2-shadow graph induced by the colouring of Kn(3).

Let k ≥ 1 be an integer, and let H be a graph with no isolated vertices embedded in the projective plane, such that every homotopically non-trivial closed curve intersects H at least k times, and the deletion and contraction of any edge in this embedding results in an embedding that no longer has this property. Let G be the planar double cover of H obtained by lifting G into the universal covering space of the projective plane, the sphere. We prove that G is minor-minimal of branch-width 2k. We also exhibit examples of minor-minimal planar graphs of branch-width 6 that do not arise in this way.

In this paper we consider the influences of variables on Boolean functions in general product spaces. Unlike the case of functions on the discrete cube, where there is a clear definition of influence, in the general case several definitions have been presented in different papers. We propose a family of definitions for the influence that contains all the known definitions, as well as other natural definitions, as special cases. We show that the proofs of the BKKKL theorem and of other results can be adapted to our new definition. The adaptation leads to generalizations of these theorems, which are tight in terms of the definition of influence used in the assertion.

We study a problem on edge percolation on product graphs G × K2. Here G is any finite graph and K2 consists of two vertices {0, 1} connected by an edge. Every edge in G × K2 is present with probability p independent of other edges. The bunkbed conjecture states that for all G and p, the probability that (u, 0) is in the same component as (v, 0) is greater than or equal to the probability that (u, 0) is in the same component as (v, 1) for every pair of vertices u, v ∈ G.

We generalize this conjecture and formulate and prove similar statements for randomly directed graphs. The methods lead to a proof of the original conjecture for special classes of graphs G, in particular outerplanar graphs.

We show that the number of halving sets of a set of n points in ℝ4 is O(n4−1/18), improving the previous bound of [10] with a simpler (albeit similar) proof.

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.

Let X be the random variable that counts the number of triangles in the binomial random graph G(n, p). We show that for some positive constant c, the probability that X deviates from its expectation by at least λVar(X)1/2 is at most e−cλ2, provided p = o(1), λ = ω() and λ ≤ (n3p3 + n4p5)1/6.