Our aim in this note is to make some conjectures about extremal densities of daisy-free families, where a ‘daisy’ is a certain hypergraph. These questions turn out to be related to some Turán problems in the hypercube, but they are also natural in their own right. We start by giving the daisy conjectures, and some related problems, and shall then go on to describe the connection with vertex-Turán problems in the hypercube.

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.

Let (r−1)n ≥ rk and let . Suppose that F1 ∩ ⋅⋅⋅ ∩ Fr ≠ ∅ holds for all Fi ∈ i, 1 ≤ i ≤ r. Then we show that .

Plünnecke's inequality is a standard tool for obtaining estimates on the cardinality of sumsets and has many applications in additive combinatorics. We present a new proof. The main novelty is that the proof is completed with no reference to Menger's theorem or Cartesian products of graphs. We also investigate the sharpness of the inequality and show that it can be sharp for arbitrarily long, but not for infinite commutative graphs. A key step in our investigation is the construction of arbitrarily long regular commutative graphs. Lastly we prove a necessary condition for the inequality to be attained.

Let Ωn be the nn-element set consisting of all functions that have {1, 2, 3, . . ., n} as both domain and codomain. Let T(f) be the order of f, i.e., the period of the sequence f, f(2), f(3), f(4) . . . of compositional iterates. A closely related number, B(f) = the product of the lengths of the cycles of f, has previously been used as an approximation for T. This paper proves that the average values of these two quantities are quite different. The expected value of T is where k0 is a complicated but explicitly defined constant that is approximately 3.36. The expected value of B is much larger:

We consider a variant of the Cops and Robbers game where the robber can move t edges at a time, and show that in this variant, the cop number of a d-regular graph with girth larger than 2t+2 is Ω(dt). By the known upper bounds on the order of cages, this implies that the cop number of a connected n-vertex graph can be as large as Ω(n2/3) if t ≥ 2, and Ω(n4/5) if t ≥ 4. This improves the Ω() lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers, J. Graph Theory, to appear) when 2 ≤ t ≤ 6. We also conjecture a general upper bound O(nt/t+1) for the cop number in this variant, generalizing Meyniel's conjecture.

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.

Szemerédi's Regularity Lemma is an important tool for analysing the structure of dense graphs. There are versions of the Regularity Lemma for sparse graphs, but these only apply when the graph satisfies some local density condition. In this paper, we prove a sparse Regularity Lemma that holds for all graphs. More generally, we give a Regularity Lemma that holds for arbitrary real matrices.

We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of C4. We show that, with probability tending to 1 as n → ∞, the final graph produced by this process has maximum degree O((nlogn)1/3) and consequently size O(n4/3(logn)1/3), which are sharp up to constants. This confirms conjectures of Bohman and Keevash and of Osthus and Taraz, and improves upon previous bounds due to Bollobás and Riordan and Osthus and Taraz.

Two players share a connected graph with non-negative weights on the vertices. They alternately take the vertices (one in each turn) and collect their weights. The rule they have to obey is that the remaining part of the graph must be connected after each move. We conjecture that the first player can get at least half of the weight of any tree with an even number of vertices. We provide a strategy for the first player to get at least 1/4 of an even tree. Moreover, we confirm the conjecture for subdivided stars. The parity condition is necessary: Alice gets nothing on a three-vertex path with all the weight at the middle. We suspect a kind of general parity phenomenon, namely, that the first player can gather a substantial portion of the weight of any ‘simple enough’ graph with an even number of vertices.

We introduce a discrete random process which we call the passenger model, and show that it is connected to a certain random model of the assignment problem and in particular to the so-called Buck–Chan–Robbins urn process. We propose a conjecture on the distribution of the location of the minimum cost assignment in a cost matrix with zeros at specified positions and remaining entries of exponential distribution. The conjecture is consistent with earlier results on the participation probability of an individual matrix entry. We also use the passenger model to verify a conjecture by V. Dotsenko on the assignment problem.

We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe approximation of the Ising partition function. The other is a polynomial of one variable that is obtained by the specialization of the first one. It is shown that these polynomials satisfy deletion–contraction relations and are new examples of the V-function, which was introduced by Tutte (Proc. Cambridge Philos. Soc.43, 1947, p. 26). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs, i.e., spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer–dimer partition function with weights parametrized by that variable. The properties of the coefficients and the possible region of zeros are also discussed for this polynomial.

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.

The tools of zero biasing are adapted to yield a general result suitable for analysing the behaviour of certain growth processes. The main theorem is applied to prove a central limit theorem, with explicit error terms in the L1 metric, for a natural statistic of the Jack measure on partitions.

Let G be a graph with m edges, and let k be a positive integer. We show that V(G) admits a k-partition V1, . . . Vk such that for i ∈ {1, 2, . . . k}, and , where e(Vi) denotes the number of edges with both ends in Vi and . This answers a problem of Bollobás and Scott [2] in the affirmative. Moreover, for i ∈ {1, 2, . . ., k}, which is close to being best possible and settles another problem of Bollobás and Scott [2].

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.

The classical Erdős–Pósa theorem states that for each positive integer k there is an f(k) such that, in each graph G which does not have k + 1 disjoint cycles, there is a blocker of size at most f(k); that is, a set B of at most f(k) vertices such that G−B has no cycles. We show that, amongst all such graphs on vertex set {1,. . .,n}, all but an exponentially small proportion have a blocker of size k. We also give further properties of a random graph sampled uniformly from this class, concerning uniqueness of the blocker, connectivity, chromatic number and clique number.

A key step in the proof of the main theorem is to show that there must be a blocker as in the Erdős–Pósa theorem with the extra ‘redundancy’ property that B–v is still a blocker for all but at most k vertices v ∈ B.