A conjecture of Alon, Krivelevich and Sudakov states that, for any graph $F$ , there is a constant $c_F \gt 0$ such that if $G$ is an $F$ -free graph of maximum degree $\Delta$ , then $\chi\!(G) \leqslant c_F \Delta/ \log\!\Delta$ . Alon, Krivelevich and Sudakov verified this conjecture for a class of graphs $F$ that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot and Sereni that if $G$ is $K_{t,t}$ -free, then $\chi\!(G) \leqslant (t + o(1)) \Delta/ \log\!\Delta$ as $\Delta \to \infty$ . We improve this bound to $(1+o(1)) \Delta/\log\!\Delta$ , making the constant factor independent of $t$ . We further extend our result to the DP-colouring setting (also known as correspondence colouring), introduced by Dvořák and Postle.

If all nonzero eigenvalues of the (normalized) Laplacian of a graph $G$ are close to 1, then $G$ is $t$-Turán in the sense that any subgraph of $G$ containing no $K_{t+1}$ contains at most $(1-1/t + o(1) ) e(G)$ edges where $e(G)$ denotes the number of edges in G.

The Lehmer–Euclid Algorithm is an improvement of the Euclid Algorithm when applied to large integers. The original Lehmer–Euclid Algorithm replaces divisions on multi-precision integers by divisions on single-precision integers. Here we study a slightly different algorithm that replaces computations on $n$-bit integers by computations on $\mu n$-bit integers. This algorithm depends on the truncation degree $\mu\in ]0, 1[$ and is denoted as the ${\mathcal{LE}}_\mu$ algorithm. The original Lehmer–Euclid Algorithm can be viewed as the limit of the ${\mathcal{LE}}_\mu$ algorithms for $\mu \to 0$. We provide here a precise analysis of the ${\mathcal{LE}}_\mu$ algorithm. For this purpose, we are led to study what we call the Interrupted Euclid Algorithm. This algorithm depends on some parameter $\alpha \in [0, 1]$ and is denoted by ${\mathcal E}_{\alpha}$. When running with an input $(a, b)$, it performs the same steps as the usual Euclid Algorithm, but it stops as soon as the current integer is smaller than $a^\alpha$, so that ${\mathcal E}_{0}$ is the classical Euclid Algorithm. We obtain a very precise analysis of the algorithm ${\mathcal E}_{\alpha}$, and describe the behaviour of main parameters (number of iterations, bit complexity) as a function of parameter $\alpha$. Since the Lehmer–Euclid Algorithm ${\mathcal {LE}}_\mu$ when running on $n$-bit integers can be viewed as a sequence of executions of the Interrupted Euclid Algorithm ${\mathcal E}_{1/2}$ on $\mu n $-bit integers, we then come back to the analysis of the ${\mathcal {LE}}_\mu$ algorithm and obtain our results.

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.

We study and classify proper q-colourings of the ℤd lattice, identifying three regimes where different combinatorial behaviour holds. (1) When $q\le d+1$ , there exist frozen colourings, that is, proper q-colourings of ℤd which cannot be modified on any finite subset. (2) We prove a strong list-colouring property which implies that, when $q\ge d+2$ , any proper q-colouring of the boundary of a box of side length $n \ge d+2$ can be extended to a proper q-colouring of the entire box. (3) When $q\geq 2d+1$ , the latter holds for any $n \ge 1$ . Consequently, we classify the space of proper q-colourings of the ℤd lattice by their mixing properties.

Given a subset $S$ of an abelian group $G$ and an integer $k\geq 1$, the $k$-deck of $S$ is the function that assigns to every $T\subseteq G$ with at most $k$ elements the number of elements $g\in G$ with $g+T\subseteq S$. The reconstruction problem for an abelian group $G$ asks for the minimal value of $k$ such that every subset $S$ of $G$ is determined, up to translation, by its $k$-deck. This minimal value is the set-reconstruction number$r_{\rm set}(G)$ of $G$; the corresponding value for multisets is the reconstruction number$r(G)$.

Previous work had given bounds for the set-reconstruction number of cyclic groups: Alon, Caro, Krasikov and Roditty [1] showed that $r_{\rm set}({\mathbb{Z}}_n)<\log_2n$ and Radcliffe and Scott [15] that $r_{\rm set}({\mathbb{Z}}_n)<9\frac{\ln n}{\ln\ln n}$. We give a precise evaluation of $r(G)$ for all abelian groups $G$ and deduce that $r_{\rm set}({\mathbb{Z}}_n)\leq 6$.

In this paper, we conclude the construction of all the matroids having circumference at most five. We use this result to prove a conjecture of Hochstättler and Jackson, in a special case.

Akbari and Alipour [1] conjectured that any Latin array of order n with at least n2/2 symbols contains a transversal. For large n, we confirm this conjecture, and moreover, we show that n399/200 symbols suffice.

For any Boolean function f, let L(f) be its formula size complexity in the basis {∧, [oplus ] 1}. For every n and every k[les ]n/2, we describe a probabilistic distribution on formulas in the basis {∧, [oplus ] 1} in some given set of n variables and of size at most [lscr ](k)=4k. Let pn,k(f) be the probability that the formula chosen from the distribution computes the function f. For every function f with L(f)[les ][lscr ](k)α, where α=log4(3/2), we have pn,k(f)>0. Moreover, for every function f, if pn,k(f)>0, then

formula here

where c>1 is an absolute constant. Although the upper and lower bounds are exponentially small in [lscr ](k), they are quasi-polynomially related whenever [lscr ](k)[ges ]lnΩ(1)n. The construction is a step towards developing a model appropriate for investigation of the properties of a typical (random) Boolean function of some given complexity.

Let $\cal{B}(n, \leq 4)$ denote the subsets of $[n]:=\{ 1, 2, \dots, n\}$ of at most 4 elements. Suppose that $\cal{F}$ is a set system with the property that every member of $\cal{B}$ can be written as a union of (at most) two members of $\cal{F}$. (Such an $\cal{F}$ is called a 2-base of $\cal{B}$.) Here we answer a question of Erdős proving that \[|\FF|\geq 1+n+\binom{n}{2}- \Bigl\lfloor \frac{4}{3}n\Bigr\rfloor\], and this bound is best possible for $n\geq 8$.

We consider first-passage percolation on a ladder, i.e., the graph ℕ × {0, 1}, where nodes at distance 1 are joined by an edge, and the times are exponentially i.i.d. with mean 1. We find an appropriate Markov chain to calculate an explicit expression for the time constant whose numerical value is ≈0.6827. This time constant is the long-term average inverse speed of the process. We also calculate the average residual time.

We obtain large-deviation approximations for the empirical distribution for a general family of occupancy problems. In the general setting, balls are allowed to fall in a given urn depending on the urn's contents prior to the throw. We discuss a parametric family of statistical models that includes Maxwell–Boltzmann, Bose–Einstein and Fermi–Dirac statistics as special cases. A process-level large-deviation analysis is conducted and the rate function for the original problem is then characterized, via the contraction principle, by the solution to a calculus of variations problem. The solution to this variational problem is shown to coincide with that of a simple finite-dimensional minimization problem. As a consequence, the large-deviation approximations and related qualitative information are available in more-or-less explicit form.

We give a new combinatorial interpretation of the stationary distribution of the (partially) asymmetric exclusion process on a finite number of sites in terms of decorated alternative trees and coloured permutations. The corresponding expressions of the multivariate partition functions are then related to multivariate generalisations of Eulerian polynomials for coloured permutations considered recently by N. Williams and the third author, and others. We also discuss stability and negative dependence properties satisfied by the partition functions.

We consider the complete graph 𝜅n on n vertices with exponential mean n edge lengths. Writing Cij for the weight of the smallest-weight path between vertices i, j ∈ [n], Janson [18] showed that maxi,j∈[n]Cij/logn converges in probability to 3. We extend these results by showing that maxi,j∈[n]Cij − 3 logn converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centred graph diameter of the barely supercritical Erdős–Rényi random graph in [22].

We study the problem of finding the root vertex in large growing networks. We prove that it is possible to construct confidence sets of size independent of the number of vertices in the network that contain the root vertex with high probability in various models of random networks. The models include uniform random recursive dags and uniform Cooper-Frieze random graphs.

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.

In this short note, we prove the following analog of the Kővári–Sós–Turán theorem for intersection graphs of boxes. If G is the intersection graph of n axis-parallel boxes in $${{\mathbb{R}}^d}$$ such that G contains no copy of Kt,t, then G has at most ctn( log n)2d+3 edges, where c = c(d)>0 only depends on d. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit, Chernikov, Starchenko, Tao and Tran of K2,2-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon, Basavaraju, Chandran, Mathew and Rajendraprasad. We show that there exist graphs of separation dimension 4 having superlinear number of edges.

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 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.

For an edge-coloured graph G, the minimum colour degree of G means the minimum number of colours on edges which are incident to each vertex of G. We prove that if G is an edge-coloured graph with minimum colour degree at least 5, then V(G) can be partitioned into two parts such that each part induces a subgraph with minimum colour degree at least 2. We show this theorem by proving amuch stronger form. Moreover, we point out an important relationship between our theorem and Bermond and Thomassen’s conjecture in digraphs.