Consider the following communication problem, which leads to a new notion of edge colouring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the transmitters and the nodes on the other side are the receivers. The edges correspond to messages, and every edge e is associated with an integer c(e), corresponding to the time it takes the message to reach its destination. A proper k-edge-colouring with delays is a function f from the edges to {0, 1, . . ., k − 1}, such that, for every two edges e1 and e2 with the same transmitter, f(e1) ≠ f(e2), and for every two edges e1 and e2 with the same receiver, f(e1) + c(e1) ≢ f(e2) + c(e2) (mod k). Ross, Bambos, Kumaran, Saniee and Widjaja [18] conjectured that there always exists a proper edge colouring with delays using k = Δ + o(Δ) colours, where Δ is the maximum degree of the graph. Haxell, Wilfong and Winkler [11] conjectured that a stronger result holds: k = Δ + 1 colours always suffice. We prove the weaker conjecture for simple bipartite graphs, using a probabilistic approach, and further show that the stronger conjectureholds for some multigraphs, applying algebraic tools.

In this note we give a very short proof for the description of all maximum size two-part Sperner systems.

We define a variant of the crossing number for an embedding of a graph G into ℝ3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the rectilinear space crossing numbers of pseudo-random graphs.

Suppose $n$ circular arcs of lengths $\len_i \in [0,1],0\leq i<n$, are placed uniformly at random on a unit length circle. We study the maximum overlap, i.e., the number of arcs that overlap at the same position of the circle. In particular, we give almost exact tail bounds for this random variable. By applying these tail bounds we can characterize the expected maximum overlap exactly up to constant factors in lower order terms. We illustrate the strength of our results by presenting new performance guarantees for three algorithmic applications: minimizing rotational delays for disks, scheduling accesses to parallel disks, and allocating memory blocks to limit cache interference misses.

In [1] we introduced and studied for product hypergraphs where ℋi = (i,ℰi), the minimal size π(ℋn) of a partition of into sets that are elements of . The main result was that

if the ℋis are graphs with all loops included. A key step in the proof concerns the special case of complete graphs. Here we show that (1) also holds when the ℋi are complete d-uniform hypergraphs with all loops included, subject to a condition on the sizes of the i. We also present an upper bound on packing numbers.

Lemke and Kleitman [2] showed that, given a positive integer d and d (necessarily non-distinct) divisors of da1, …, ad there exists a subset Q ⊆ {1, …, d} such that d = [sum ]i∈Qai answering a conjecture of Erdo″s and Lemke. Here we extend this result, showing that, provided [sum ]p|d1/p [les ] 1 (where the sum is taken over all primes p), there is some collection from a1, …, ad which both sum to d and which can themselves be ordered so that each element divides its successor in the order. Furthermore, we shall show that the condition on the prime divisors is in some sense also necessary.

We consider continuous time random walks on a product graph G×H, where G is arbitrary and H consists of two vertices x and y linked by an edge. For any t>0 and any a, b∈V(G), we show that the random walk starting at (a, x) is more likely to have hit (b, x) than (b, y) by time t. This contrasts with the discrete time case and proves a conjecture of Bollobás and Brightwell. We also generalize the result to cases where H is either a complete graph on n vertices or a cycle on n vertices.

A type of evolution of graphs with maximum vertex degree at most d is introduced. This evolution can start from any initial graph whose set of vertices of degree less than d is independent. The main concern is the regularity of graphs generated by this graph process when the initial graph has no edges. By analysis of the solutions of systems of differential equations it is shown that the final graph of this evolution is asymptotically almost surely a d-regular graph (subject to the usual parity condition).

We say a graph is (Qn,Qm)-saturated if it is a maximal Qm-free subgraph of the n-dimensional hypercube Qn. A graph is said to be (Qn,Qm)-semi-saturated if it is a subgraph of Qn and adding any edge forms a new copy of Qm. The minimum number of edges a (Qn,Qm)-saturated graph (respectively (Qn,Qm)-semi-saturated graph) can have is denoted by sat(Qn,Qm) (respectively s-sat(Qn,Qm)). We prove that

$$ \begin{linenomath} \lim_{n\to\infty}\ffrac{\sat(Q_n,Q_m)}{e(Q_n)}=0, \end{linenomath}$$

$$ \begin{linenomath} \ssat(Q_n,Q_m)\geq \ffrac{m+1}{2}\cdot 2^n, \end{linenomath}$$

An exact formula for the expected length of the minimum spanning tree of a connected graph, with independent and identical edge distribution, is given, which generalizes Steele's formula in the uniform case. For a complete graph, the difference of expected lengths between exponential distribution, with rate one, and uniform distribution on the interval (0, 1) is shown to be positive and of rate ζ(3)/n. For wheel graphs, precise values of expected lengths are given via calculations of the associated Tutte polynomials.

We give an alternative proof of a conjecture of Bollobás, Brightwell and Leader, first proved by Peter Allen, stating that the number of Boolean functions definable by 2-SAT formulae is . One step in the proof determines the asymptotics of the number of ‘odd-blue-triangle-free’ graphs on n vertices.

Problems associated with m-ary trees have been studied by computer scientists and combinatorialists. It is well known that a simple generalization of the Catalan numbers counts the number of m-ary trees on n nodes. In this paper we consider τm, n, the number of m-ary search trees on n keys, a quantity that arises in studying the space of m-ary search trees under the uniform probability model. We prove an exact formula for τm, n, both by analytic and by combinatorial means. We use uniform local approximations for sums of i.i.d. random variables to study the asymptotic development of τm, n for fixed m as n→∞.

Given a (multi)digraph H, a digraph D is H-linked if every injective function ι:V(H) → V(D) can be extended to an H-subdivision. In this paper, we give sharp degree conditions that ensure a sufficiently large digraph D is H-linked for arbitrary H. The notion of an H-linked digraph extends the classes of m-linked, m-ordered and strongly m-connected digraphs.

First, we give sharp minimum semi-degree conditions for H-linkedness, extending results of Kühn and Osthus on m-linked and m-ordered digraphs. It is known that the minimum degree threshold for an undirected graph to be H-linked depends on a partition of the (undirected) graph H into three parts. Here, we show that the corresponding semi-degree threshold for H-linked digraphs depends on a partition of H into as many as nine parts.

We also determine sharp Ore–Woodall-type degree-sum conditions ensuring that a digraph D is H-linked for general H. As a corollary, we obtain (previously undetermined) sharp degree-sum conditions for m-linked and m-ordered digraphs.

Every general graph with degrees 2k and 2k − 2, k ≥ 3, with zero or at least two vertices of degree 2k − 2 in each component, has a k-edge-colouring such that each monochromatic subgraph has degree 1 or 2 at every vertex.

In particular, if T is a triangle in a 6-regular general graph, there exists a 2-factorization of G such that each factor uses an edge in T if and only if T is non-separating.

Given a class of combinatorial structures [Cscr ], we consider the quantity N(n, m), the number of multiset constructions [Pscr ] (of [Cscr ]) of size n having exactly m [Cscr ]-components. Under general analytic conditions on the generating function of [Cscr ], we derive precise asymptotic estimates for N(n, m), as n→∞ and m varies through all possible values (in general 1[les ]m[les ]n). In particular, we show that the number of [Cscr ]-components in a random (assuming a uniform probability measure) [Pscr ]-structure of size n obeys asymptotically a convolution law of the Poisson and the geometric distributions. Applications of the results include random mapping patterns, polynomials in finite fields, parameters in additive arithmetical semigroups, etc. This work develops the ‘additive’ counterpart of our previous work on the distribution of the number of prime factors of an integer [20].

What simple condition on a graph $G$ will ensure that $G\,{\succ}\,K_t$? As usual, $G\,{\succ}\,K_t$ means that $K_t$ is a minor of the graph $G$ (in other words, $G$ has vertex disjoint connected subgraphs $W_1,\ldots,W_t$ and at least one edge between $W_i$ and $W_j$, $1\,{\le}\, i<j\,{\le}\, t$).

Let G be a graph on n vertices and with maximum degree Δ, and let k be an integer. The k-recolouring graph of G is the graph whose vertices are k-colourings of G and where two k-colourings are adjacent if they differ at exactly one vertex. It is well known that the k-recolouring graph is connected for $k\geq \Delta+2$ . Feghali, Johnson and Paulusma (J. Graph Theory83 (2016) 340–358) showed that the (Δ + 1)-recolouring graph is composed by a unique connected component of size at least 2 and (possibly many) isolated vertices.

In this paper, we study the proportion of isolated vertices (also called frozen colourings) in the (Δ + 1)-recolouring graph. Our first contribution is to show that if G is connected, the proportion of frozen colourings of G is exponentially smaller in n than the total number of colourings. This motivates the use of the Glauber dynamics to approximate the number of (Δ + 1)-colourings of a graph. In contrast to the conjectured mixing time of O(nlog n) for $k\geq \Delta+2$ colours, we show that the mixing time of the Glauber dynamics for (Δ + 1)-colourings restricted to non-frozen colourings can be Ω(n2). Finally, we prove some results about the existence of graphs with large girth and frozen colourings, and study frozen colourings in random regular graphs.

An equitable colouring of a graph G is a vertex colouring where no two adjacent vertices are coloured the same and, additionally, the colour class sizes differ by at most 1. The equitable chromatic number χ=(G) is the minimum number of colours required for this. We study the equitable chromatic number of the dense random graph ${\mathcal{G}(n,m)}$ where $m = \left\lfloor {p\left( \matrix{ n \cr 2 \cr} \right)} \right\rfloor $ and 0 < p < 0.86 is constant. It is a well-known question of Bollobás [3] whether for p = 1/2 there is a function f(n) → ∞ such that, for any sequence of intervals of length f(n), the normal chromatic number of ${\mathcal{G}(n,m)}$ lies outside the intervals with probability at least 1/2 if n is large enough. Bollobás proposes that this is likely to hold for f(n) = log n. We show that for the equitable chromatic number, the answer to the analogous question is negative. In fact, there is a subsequence ${({n_j})_j}_{ \in {\mathbb {N}}}$ of the integers where $\chi_=({\mathcal{G}(n_j,m_j)})$ is concentrated on exactly one explicitly known value. This constitutes surprisingly narrow concentration since in this range the equitable chromatic number, like the normal chromatic number, is rather large in absolute value, namely asymptotically equal to n/(2logbn) where b = 1/(1 − p).

In a recent paper, Baxter and Zeilberger showed that the two most important Mahonian statistics, the inversion number and the major index, are asymptotically independently normally distributed on permutations. In another recent paper, Canfield, Janson and Zeilberger proved the result, already known to statisticians, that the Mahonian distribution is asymptotically normal on words. This leaves one question unanswered: What, asymptotically, is the joint distribution of the inversion number and the major index on words? We answer this question by establishing convergence to a bivariate normal distribution.

A 2×2 table of nonnegative integers is subdivided additively into n 2×2 subtables of nonnegative integers in an arbitrary way. The first case of Simpson's Paradox (SP) occurs when the determinant of the original table is less than zero, but the determinant of each of the n 2×2 subtables is greater than or equal to zero. The second case of SP occurs when the previous inequalities hold with ‘less than’ and ‘greater than or equal’ replaced by ‘greater than’ and ‘less than or equal’, respectively. For the case n=2, this paper calculates the asymptotic proportion of the subdivisions of the original 2×2 table such that SP occurs. It is shown that this asymptotic proportion is bounded above by 1/12.