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.

Under the assumption that sequences of graphs equipped with resistances, associated measures, walks and local times converge in a suitable Gromov-Hausdorff topology, we establish asymptotic bounds on the distribution of the $\varepsilon$-blanket times of the random walks in the sequence. The precise nature of these bounds ensures convergence of the $\varepsilon$-blanket times of the random walks if the $\varepsilon$-blanket time of the limiting diffusion is continuous at $\varepsilon$ with probability 1. This result enables us to prove annealed convergence in various examples of critical random graphs, including critical Galton-Watson trees and the Erdős-Rényi random graph in the critical window. We highlight that proving continuity of the $\varepsilon$-blanket time of the limiting diffusion relies on the scale invariance of a finite measure that gives rise to realizations of the limiting compact random metric space, and therefore we expect our results to hold for other examples of random graphs with a similar scale invariance property.

We show that for a fixed $q$, the number of $q$-ary $t$-error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - 2\sqrt{n \log n}$, where $H_q(n, t) = q^n/ V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner, who showed the result for $t = o(n^{1/3} (\log n)^{-2/3})$.

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.

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

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 $A \subseteq \{0,1\}^n$ be a set of size $2^{n-1}$, and let $\phi \,:\, \{0,1\}^{n-1} \to A$ be a bijection. We define the average stretch of $\phi$ as

\begin{equation*} {\sf avgStretch}(\phi ) = {\mathbb E}[{{\sf dist}}(\phi (x),\phi (x'))], \end{equation*}

$x,x' \in \{0,1\}^{n-1}$

In this paper, we continue the line of research studying mappings on the discrete hypercube with small average stretch. We prove the following results.

• For any set $A \subseteq \{0,1\}^n$ of density $1/2$ there exists a bijection $\phi _A \,:\, \{0,1\}^{n-1} \to A$ such that ${\sf avgStretch}(\phi _A) = O\left(\sqrt{n}\right)$.

• For $n = 3^k$ let ${A_{\textsf{rec-maj}}} = \{x \in \{0,1\}^n \,:\,{\textsf{rec-maj}}(x) = 1\}$, where ${\textsf{rec-maj}} \,:\, \{0,1\}^n \to \{0,1\}$ is the function recursive majority of 3’s. There exists a bijection $\phi _{{\textsf{rec-maj}}} \,:\, \{0,1\}^{n-1} \to{A_{\textsf{rec-maj}}}$ such that ${\sf avgStretch}(\phi _{{\textsf{rec-maj}}}) = O(1)$.

• Let ${A_{{\sf tribes}}} = \{x \in \{0,1\}^n \,:\,{\sf tribes}(x) = 1\}$. There exists a bijection $\phi _{{\sf tribes}} \,:\, \{0,1\}^{n-1} \to{A_{{\sf tribes}}}$ such that ${\sf avgStretch}(\phi _{{\sf tribes}}) = O(\!\log (n))$.

These results answer the questions raised by Benjamini, Cohen, and Shinkar (Isr. J. Math 2016).

In this note, we give a precise description of the limiting empirical spectral distribution for the non-backtracking matrices for an Erdős-Rényi graph $G(n,p)$ assuming $np/\log n$ tends to infinity. We show that derandomizing part of the non-backtracking random matrix simplifies the spectrum considerably, and then, we use Tao and Vu’s replacement principle and the Bauer-Fike theorem to show that the partly derandomized spectrum is, in fact, very close to the original spectrum.

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.

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