A chordal graph is a graph with no induced cycles of length at least $4$. Let $f(n,m)$ be the maximal integer such that every graph with $n$ vertices and $m$ edges has a chordal subgraph with at least $f(n,m)$ edges. In 1985 Erdős and Laskar posed the problem of estimating $f(n,m)$. In the late 1980s, Erdős, Gyárfás, Ordman and Zalcstein determined the value of $f(n,n^2/4+1)$ and made a conjecture on the value of $f(n,n^2/3+1)$. In this paper we prove this conjecture and answer the question of Erdős and Laskar, determining $f(n,m)$ asymptotically for all $m$ and exactly for $m \leq n^2/3+1$.

The notion of cross-intersecting set pair system of size $m$ , $ (\{A_i\}_{i=1}^m, \{B_i\}_{i=1}^m )$ with $A_i\cap B_i=\emptyset$ and $A_i\cap B_j\ne \emptyset$ , was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m\le\binom{a+b}{a}$ if $|A_i|\le a$ and $|B_i|\le b$ for each $i$ . Our central problem is to see how this bound changes with the additional condition $|A_i\cap B_j|=1$ for $i\ne j$ . Such a system is called $1$ -cross-intersecting. We show that these systems are related to perfect graphs, clique partitions of graphs, and finite geometries. We prove that their maximum size is

• at least $5^{n/2}$ for $n$ even, $a=b=n$ ,

• equal to $\bigl (\lfloor \frac{n}{2}\rfloor +1\bigr )\bigl (\lceil \frac{n}{2}\rceil +1\bigr )$ if $a=2$ and $b=n\ge 4$ ,

• at most $|\cup _{i=1}^m A_i|$ ,

• asymptotically $n^2$ if $\{A_i\}$ is a linear hypergraph ( $|A_i\cap A_j|\le 1$ for $i\ne j$ ),

• asymptotically ${1\over 2}n^2$ if $\{A_i\}$ and $\{B_i\}$ are both linear hypergraphs.

A random two-cell embedding of a given graph $G$ is obtained by choosing a random local rotation around every vertex. We analyse the expected number of faces of such an embedding, which is equivalent to studying its average genus. In 1991, Stahl [5] proved that the expected number of faces in a random embedding of an arbitrary graph of order $n$ is at most $n\log (n)$ . While there are many families of graphs whose expected number of faces is $\Theta (n)$ , none are known where the expected number would be super-linear. This led the authors of [1] to conjecture that there is a linear upper bound. In this note we confirm their conjecture by proving that for any $n$ -vertex multigraph, the expected number of faces in a random two-cell embedding is at most $2n\log (2\mu )$ , where $\mu$ is the maximum edge-multiplicity. This bound is best possible up to a constant factor.

For a $k$ -uniform hypergraph $\mathcal{H}$ on vertex set $\{1, \ldots, n\}$ we associate a particular signed incidence matrix $M(\mathcal{H})$ over the integers. For $\mathcal{H} \sim \mathcal{H}_k(n, p)$ an Erdős–Rényi random $k$ -uniform hypergraph, ${\mathrm{coker}}(M(\mathcal{H}))$ is then a model for random abelian groups. Motivated by conjectures from the study of random simplicial complexes we show that for $p = \omega (1/n^{k - 1})$ , ${\mathrm{coker}}(M(\mathcal{H}))$ is torsion-free.

Given partially ordered sets (posets) $(P, \leq _P\!)$ and $(P^{\prime}, \leq _{P^{\prime}}\!)$ , we say that $P^{\prime}$ contains a copy of $P$ if for some injective function $f\,:\, P\rightarrow P^{\prime}$ and for any $X, Y\in P$ , $X\leq _P Y$ if and only if $f(X)\leq _{P^{\prime}} f(Y)$ . For any posets $P$ and $Q$ , the poset Ramsey number $R(P,Q)$ is the least positive integer $N$ such that no matter how the elements of an $N$ -dimensional Boolean lattice are coloured in blue and red, there is either a copy of $P$ with all blue elements or a copy of $Q$ with all red elements. We focus on a poset Ramsey number $R(P, Q_n)$ for a fixed poset $P$ and an $n$ -dimensional Boolean lattice $Q_n$ , as $n$ grows large. We show a sharp jump in behaviour of this number as a function of $n$ depending on whether or not $P$ contains a copy of either a poset $V$ , that is a poset on elements $A, B, C$ such that $B\gt C$ , $A\gt C$ , and $A$ and $B$ incomparable, or a poset $\Lambda$ , its symmetric counterpart. Specifically, we prove that if $P$ contains a copy of $V$ or $\Lambda$ then $R(P, Q_n) \geq n +\frac{1}{15} \frac{n}{\log n}$ . Otherwise $R(P, Q_n) \leq n + c(P)$ for a constant $c(P)$ . This gives the first non-marginal improvement of a lower bound on poset Ramsey numbers and as a consequence gives $R(Q_2, Q_n) = n + \Theta \left(\frac{n}{\log n}\right)$ .

Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running $k$ multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for worst-case start vertices (posed by Alon, Avin, Koucký, Kozma, Lotker and Tuttle in 2008) remains an open problem. First, we improve and tighten various bounds on the stationary cover time when $k$ random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of $\Omega ((n/k) \log n)$ on the stationary cover time, holding for any $n$ -vertex graph $G$ and any $1 \leq k =o(n\log n )$ . Secondly, we establish the stationary cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising worst-case cover times in terms of stationary cover times and a novel, relaxed notion of mixing time for multiple walks called the partial mixing time. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the worst-case cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.

For a random binary noncoalescing feedback shift register of width $n$ , with all $2^{2^{n-1}}$ possible feedback functions $f$ equally likely, the process of long cycle lengths, scaled by dividing by $N=2^n$ , converges in distribution to the same Poisson–Dirichlet limit as holds for random permutations in $\mathcal{S}_N$ , with all $N!$ possible permutations equally likely. Such behaviour was conjectured by Golomb, Welch and Goldstein in 1959.

The book graph $B_n ^{(k)}$ consists of $n$ copies of $K_{k+1}$ joined along a common $K_k$ . In the prequel to this paper, we studied the diagonal Ramsey number $r(B_n ^{(k)}, B_n ^{(k)})$ . Here we consider the natural off-diagonal variant $r(B_{cn} ^{(k)}, B_n^{(k)})$ for fixed $c \in (0,1]$ . In this more general setting, we show that an interesting dichotomy emerges: for very small $c$ , a simple $k$ -partite construction dictates the Ramsey function and all nearly-extremal colourings are close to being $k$ -partite, while, for $c$ bounded away from $0$ , random colourings of an appropriate density are asymptotically optimal and all nearly-extremal colourings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of $c$ .

An old conjecture of Erdős and McKay states that if all homogeneous sets in an $n$ -vertex graph are of order $O(\!\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$ . We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an $n \times n$ bipartite graph are of order $O(\!\log n)$ , then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$ .

We consider supercritical site percolation on the $d$ -dimensional hypercube $Q^d$ . We show that typically all components in the percolated hypercube, besides the giant, are of size $O(d)$ . This resolves a conjecture of Bollobás, Kohayakawa, and Łuczak from 1994.

A $(p,q)$ -colouring of a graph $G$ is an edge-colouring of $G$ which assigns at least $q$ colours to each $p$ -clique. The problem of determining the minimum number of colours, $f(n,p,q)$ , needed to give a $(p,q)$ -colouring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$ . The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in \{4,5\}$ , each of which was proved by giving a deterministic construction which combined a $(p,p-1)$ -colouring using few colours with an algebraic colouring.

In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colourings of $p$ -cliques with $p-1$ colours which can appear in our modified version of the $(p,p-1)$ -colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$ -colourings, which would otherwise make this problem intractable for large values of $p$ . In addition, we generalize our algebraic colouring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$ .

We study approximations for the Lévy area of Brownian motion which are based on the Fourier series expansion and a polynomial expansion of the associated Brownian bridge. Comparing the asymptotic convergence rates of the Lévy area approximations, we see that the approximation resulting from the polynomial expansion of the Brownian bridge is more accurate than the Kloeden–Platen–Wright approximation, whilst still only using independent normal random vectors. We then link the asymptotic convergence rates of these approximations to the limiting fluctuations for the corresponding series expansions of the Brownian bridge. Moreover, and of interest in its own right, the analysis we use to identify the fluctuation processes for the Karhunen–Loève and Fourier series expansions of the Brownian bridge is extended to give a stand-alone derivation of the values of the Riemann zeta function at even positive integers.

Motivated by problems from compressed sensing, we determine the threshold behaviour of a random $n\times d \pm 1$ matrix $M_{n,d}$ with respect to the property ‘every $s$ columns are linearly independent’. In particular, we show that for every $0\lt \delta \lt 1$ and $s=(1-\delta )n$ , if $d\leq n^{1+1/2(1-\delta )-o(1)}$ then with high probability every $s$ columns of $M_{n,d}$ are linearly independent, and if $d\geq n^{1+1/2(1-\delta )+o(1)}$ then with high probability there are some $s$ linearly dependent columns.

Strengthening Hadwiger’s conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd $K_t$ -minor is properly $(t-1)$ -colourable. This is known as the Odd Hadwiger’s conjecture. We prove a relaxation of the above conjecture, namely we show that every graph with no odd $K_t$ -minor admits a vertex $(2t-2)$ -colouring such that all monochromatic components have size at most $\lceil \frac{1}{2}(t-2) \rceil$ . The bound on the number of colours is optimal up to a factor of $2$ , improves previous bounds for the same problem by Kawarabayashi (2008, Combin. Probab. Comput. 17 815–821), Kang and Oum (2019, Combin. Probab. Comput. 28 740–754), Liu and Wood (2021, arXiv preprint, arXiv:1905.09495), and strengthens a result by van den Heuvel and Wood (2018, J. Lond. Math. Soc. 98 129–148), who showed that the above conclusion holds under the more restrictive assumption that the graph is $K_t$ -minor-free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on $t$ was given by a function arising from the graph minor structure theorem of Robertson and Seymour. Our short proof combines the method by van den Heuvel and Wood for $K_t$ -minor-free graphs with some additional ideas, which make the extension to odd $K_t$ -minor-free graphs possible.

In this paper, we study asymmetric Ramsey properties of the random graph $G_{n,p}$ . Let $r \in \mathbb{N}$ and $H_1, \ldots, H_r$ be graphs. We write $G_{n,p} \to (H_1, \ldots, H_r)$ to denote the property that whenever we colour the edges of $G_{n,p}$ with colours from the set $[r] \,{:\!=}\, \{1, \ldots, r\}$ there exists $i \in [r]$ and a copy of $H_i$ in $G_{n,p}$ monochromatic in colour $i$ . There has been much interest in determining the asymptotic threshold function for this property. In several papers, Rödl and Ruciński determined a threshold function for the general symmetric case; that is, when $H_1 = \cdots = H_r$ . A conjecture of Kohayakawa and Kreuter from 1997, if true, would fully resolve the asymmetric problem. Recently, the $1$ -statement of this conjecture was confirmed by Mousset, Nenadov and Samotij.

Building on work of Marciniszyn, Skokan, Spöhel and Steger from 2009, we reduce the $0$ -statement of Kohayakawa and Kreuter’s conjecture to a certain deterministic subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs. This therefore resolves the $0$ -statement for all such pairs of graphs.

We show that the $4$ -state anti-ferromagnetic Potts model with interaction parameter $w\in (0,1)$ on the infinite $(d+1)$ -regular tree has a unique Gibbs measure if $w\geq 1-\dfrac{4}{d+1_{_{\;}}}$ for all $d\geq 4$ . This is tight since it is known that there are multiple Gibbs measures when $0\leq w\lt 1-\dfrac{4}{d+1}$ and $d\geq 4$ . We moreover give a new proof of the uniqueness of the Gibbs measure for the $3$ -state Potts model on the $(d+1)$ -regular tree for $w\geq 1-\dfrac{3}{d+1}$ when $d\geq 3$ and for $w\in (0,1)$ when $d=2$ .

Let $G=(S,T,E)$ be a bipartite graph. For a matching $M$ of $G$ , let $V(M)$ be the set of vertices covered by $M$ , and let $B(M)$ be the symmetric difference of $V(M)$ and $S$ . We prove that if $M$ is a uniform random matching of $G$ , then $B(M)$ satisfies the BK inequality for increasing events.

We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$ . We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min \{\delta (G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$ , where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac.

Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480–516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480–516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159–176], this fully resolves the existence of triangle factors in randomly perturbed graphs.

We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$ -universality.

In 1975 Bollobás, Erdős, and Szemerédi asked the following question: given positive integers $n, t, r$ with $2\le t\le r-1$ , what is the largest minimum degree $\delta (G)$ among all $r$ -partite graphs $G$ with parts of size $n$ and which do not contain a copy of $K_{t+1}$ ? The $r=t+1$ case has attracted a lot of attention and was fully resolved by Haxell and Szabó, and Szabó and Tardos in 2006. In this article, we investigate the $r\gt t+1$ case of the problem, which has remained dormant for over 40 years. We resolve the problem exactly in the case when $r \equiv -1 \pmod{t}$ , and up to an additive constant for many other cases, including when $r \geq (3t-1)(t-1)$ . Our approach utilizes a connection to the related problem of determining the maximum of the minimum degrees among the family of balanced $r$ -partite $rn$ -vertex graphs of chromatic number at most $t$ .

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.