The strong chromatic number χs(G) of a graph G on n vertices is the least number r with the following property: after adding $r\lceil n/r\rceil-n$ isolated vertices to G and taking the union with any collection of spanning disjoint copies of Kr in the same vertex set, the resulting graph has a proper vertex colouring with r colours. We show that for every c > 0 and every graph G on n vertices with Δ(G) ≥ cn, χs(G) ≤ (2+o(1))Δ(G), which is asymptotically best possible.

We consider transition operators P on a countable set, which are reversible, irreducible and invariant under a group G of permutations of X with compact point stabilizers. We relate the computation of the spectral radius (norm) of P with the spectral radii of certain matrices defined over the factor set G\X. In various cases, this allows easy computation of the norm of P.

A family of subsets of an n-set is 2-cancellative if, for every four-tuple {A, B, C, D} of its members, A∪ B∪C=A∪ B∪ D implies C = D. This generalizes the concept of cancellative set families, defined by the property that A∪B ≠A ∪ C for A, B, C all different. The asymptotics of the maximum size of cancellative families of subsets of an n-set is known (Tolhuizen [7]). We provide a new upper bound on the size of 2-cancellative families, improving the previous bound of 20.458n to 20.42n.

We extend a recent argument of Kahn, Narayanan and Park ((2021) Proceedings of the AMS 149 3201–3208) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of $C_4$ that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning $K_r$-cycles.

Hadwiger’s conjecture asserts that every graph without a $K_t$ -minor is $(t-1)$ -colourable. It is known that the exact version of Hadwiger’s conjecture does not extend to list colouring, but it has been conjectured by Kawarabayashi and Mohar (2007) that there exists a constant $c$ such that every graph with no $K_t$ -minor has list chromatic number at most $ct$ . More specifically, they also conjectured that this holds for $c=\frac{3}{2}$ .

Refuting the latter conjecture, we show that the maximum list chromatic number of graphs with no $K_t$ -minor is at least $(2-o(1))t$ , and hence $c \ge 2$ in the above conjecture is necessary. This improves the previous best lower bound by Barát, Joret and Wood (2011), who proved that $c \ge \frac{4}{3}$ . Our lower-bound examples are obtained via the probabilistic method.

Let k3reg(n, d) be the minimum number of triangles in d-regular graphs with n vertices. We find the exact value of k3reg(n, d) for d between and n/2. In addition, we identify the structure of the extremal graphs.

Consider the random graph process where we start with an empty graph on n vertices and, at time t, are given an edge et chosen uniformly at random among the edges which have not appeared so far. A classical result in random graph theory asserts that w.h.p. the graph becomes Hamiltonian at time (1/2+o(1))n log n. On the contrary, if all the edges were directed randomly, then the graph would have a directed Hamilton cycle w.h.p. only at time (1+o(1))n log n. In this paper we further study the directed case, and ask whether it is essential to have twice as many edges compared to the undirected case. More precisely, we ask if, at time t, instead of a random direction one is allowed to choose the orientation of et, then whether or not it is possible to make the resulting directed graph Hamiltonian at time earlier than n log n. The main result of our paper answers this question in the strongest possible way, by asserting that one can orient the edges on-line so that w.h.p. the resulting graph has a directed Hamilton cycle exactly at the time at which the underlying graph is Hamiltonian.

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.

A sequence S is called anagram-free if it contains no consecutive symbols r1r2. . .rkrk+1. . .r2k such that rk+1. . .r2k is a permutation of the block r1r2. . .rk. Answering a question of Erdős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Hałuszczak and Riordan [2], we consider a natural generalization of anagram-free sequences for graph colourings. A colouring of the vertices of a given graph G is called anagram-free if the sequence of colours on any path in G is anagram-free. We call the minimal number of colours needed for such a colouring the anagram-chromatic number of G.

In this paper we study the anagram-chromatic number of several classes of graphs like trees, minor-free graphs and bounded-degree graphs. Surprisingly, we show that there are bounded-degree graphs (such as random regular graphs) in which anagrams cannot be avoided unless we essentially give each vertex a separate colour.

Given two k-graphs (k-uniform hypergraphs) F and H, a perfect F-tiling (or F-factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H. For all complete k-partite k-graphs K, Mycroft proved a minimum codegree condition that guarantees a K-factor in an n-vertex k-graph, which is tight up to an error term o(n). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K(k)(1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.

We consider the problem of determining the maximum number N(m, k, r) of columns of a 0−1 matrix with m rows and exactly r ones in each column such that every k columns are linearly independent over ℤ2. For fixed integers k[ges ]4 and r[ges ]2, where k is even and gcd(k−1, r) = 1, we prove the lower bound N(m, k, r) = Ω(mkr/2(k−1) ·(ln m)1/k−1). This improves on earlier results from [14] by a factor Θ((ln m)1/k−1). Moreover, we describe a polynomial time algorithm achieving this new lower bound.

The prime factorization of a random integer has a GEM/Poisson-Dirichlet distribution as transparently proved by Donnelly and Grimmett [8]. By similarity to the arc-sine law for the mean distribution of the divisors of a random integer, due to Deshouillers, Dress and Tenenbaum [6] (see also Tenenbaum [24, II.6.2, p. 233]), – the ‘DDT theorem’ – we obtain an arc-sine law in the GEM/Poisson-Dirichlet context. In this context we also investigate the distribution of the number of components larger than ε which correspond to the number of prime factors larger than nε.

Given a graph G and a bijection f : E(G) → {1, 2,…,e(G)}, we say that a trail/path in G is f-increasing if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is n-1, and the case of a path is still wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path.

In this paper we consider the random graph G = Gn,p with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of Kn has w.h.p. an increasing trail of length (1-o(1))en, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with p = o(1).

The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let ${m=d(n-1)}$ be the degree and $V = n^d$ be the number of vertices of H(d, n). Let $p_c^{(d)}$ be the critical point for bond percolation on H(d, n). We show that, for $d \in \mathbb{N}$ fixed and $n \to \infty$,

$$p_c^{(d)} = {1 \over m} + {{2{d^2} - 1} \over {2{{(d - 1)}^2}}}{1 \over {{m^2}}} + O({m^{ - 3}}) + O({m^{ - 1}}{V^{ - 1/3}}),$$

$O(m^{-1}V^{-1/3})$

$d=4,5,6$

$m^{-3} = O(m^{-1}V^{-1/3})$

$p_c^{(d)}$

$d=2,3,4$

We consider the function χ(Gk), defined to be the smallest number of colours that can colour a graph G in such a way that no vertices of distance at most k receive the same colour. In particular we shall look at how small a value this function can take in terms of the order and diameter of G. We get general bounds for this and tight bounds for the cases k=2 and k=3.

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k [ges ] 3. The best known polynomial time approximation algorithms require nδ (for a positive constant δ depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be k-coloured almost surely in polynomial time.

In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into k colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) [ges ] n−1+ε where ε is a constant greater than 1/4.

The aim of this paper is to point to a difference between binary and hyperary structures. The modular counting functions of a class of structures defined by a sentence of second-order monadic logic with equality, based on binary relations, are ultimately periodic. However, this is not the case for sentences based on quaternary relations.

Let B = [b1, …, bn] (with column vectors bi) be a basis of ℝn. Then L = [sum ]biℤ is a lattice in ℝn and A = B[top ]B is the Gram matrix of B. The reciprocal lattice L* of L has basis B* = (B−1)[top ] with Gram matrix A−1. For any nonsingular matrix A = (ai,j) with inverse A−1 = (a*i,j), let τ(A) = max1[les ]i[les ]n {[sum ]nj =1[mid ]ai,j ·a*j,j[mid ]}. Then τ(A), τ(A−1)[ges ]1 holds, with equality for an orthogonal basis. We will show that for any lattice L there is a basis with Gram matrix A such that τ(A), τ(A−1) = exp (O((ln n)2)). This generalizes a result in [8] and [20].

For any basis transformation A→Ā with Ā = T[top ]AT, T = (ti,j)∈SLn(ℤ), we will show [mid ]ti,j[mid ][les ]τ(A−1) ·τ(Ā). This implies that every integral matrix representation of a finite group is equivalent to a representation where the coefficients of the matrices representing group elements are bounded by exp (O((ln n)2)). This new bound is considerably smaller than the known (exponential) bounds for automorphisms of Minkowski-reduced lattice bases: see, for example, [6].

The quantities τ(A), τ(A−1) have the following geometric interpretation. Let V(L) [ratio ]= {x∈ℝn[mid ]∀λ∈L [ratio ][mid ]x[mid ][les ][mid ]x−λ[mid ]} be the Voronoi cell (also called the Dirichlet region) of the lattice L. For a basis B of L, we call C(B) = {[sum ]xibi, [mid ]xi[mid ][les ]1/2} the basis cell of B. Both cells define a lattice tiling of ℝn (see [6]); they coincide for an orthogonal basis. For a general basis B of L with Gram matrix A we will show V(L)[les ]τ(A−1)·C(B) and C(B)[les ]n·τ(A)·V(L).

We show that certain topologically defined uniform spanning tree probabilities for graphs embedded in an annulus can be computed as linear combinations of Pfaffians of matrices involving the line-bundle Green's function, where the coefficients count cover-inclusive Dyck tilings of skew Young diagrams.

Given a locally finite connected infinite graph G, let the interval [pmin(G), pmax(G)] be the smallest interval such that if p > pmax(G), then every 1-independent bond percolation model on G with bond probability p percolates, and for p < pmin(G) none does. We determine this interval for trees in terms of the branching number of the tree. We also give some general bounds for other graphs G, in particular for lattices.