The classical Andrásfai-Erdős-Sós theorem considers the chromatic number of $K_{r + 1}$ -free graphs with large minimum degree, and in the case, $r = 2$ says that any n-vertex triangle-free graph with minimum degree greater than $2/5 \cdot n$ is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each k, what minimum degree guarantees that a triangle-free graph is k-colourable? The chromatic profile has been extensively studied and was finally determined by Brandt and Thomassé. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, Luczak and Thomassé introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is b-colourable (locally b-partite graphs) as well as the family where the common neighbourhood of every a-clique is b-colourable. Our results include the chromatic thresholds of these families (extending a result of Allen, Böttcher, Griffiths, Kohayakawa and Morris) as well as showing that every n-vertex locally b-partite graph with minimum degree greater than $(1 - 1/(b + 1/7)) \cdot n$ is $(b + 1)$ -colourable. Understanding these locally colourable graphs is crucial for extending the Andrásfai-Erdős-Sós theorem to non-complete graphs, which we develop elsewhere.

We show that after forcing with a countable support iteration or a finite product of Sacks or splitting forcing over L, every analytic hypergraph on a Polish space admits a $\mathbf {\Delta }^1_2$ maximal independent set. This extends an earlier result by Schrittesser (see [25]). As a main application we get the consistency of $\mathfrak {r} = \mathfrak {u} = \mathfrak {i} = \omega _2$ together with the existence of a $\Delta ^1_2$ ultrafilter, a $\Pi ^1_1$ maximal independent family, and a $\Delta ^1_2$ Hamel basis. This solves open problems of Brendle, Fischer, and Khomskii [5] and the author [23]. We also show in ZFC that $\mathfrak {d} \leq \mathfrak {i}_{cl}$ , addressing another question from [5].

For a uniform random labelled tree, we find the limiting distribution of tree parameters which are stable (in some sense) with respect to local perturbations of the tree structure. The proof is based on the martingale central limit theorem and the Aldous–Broder algorithm. In particular, our general result implies the asymptotic normality of the number of occurrences of any given small pattern and the asymptotic log-normality of the number of automorphisms.

We study two models of an age-biased graph process: the $\delta$ -version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with m attachments for each of the incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for $m=1$ , to a limit whose distribution is a mixture of two beta distributions and a single beta distribution respectively, and that for $m>1$ the limit is 1. We also analyze the likely performance of two greedy (online) algorithms, for a large matching set and a large independent set, and determine – for each model and each greedy algorithm – both a limiting fraction of vertices involved and an almost sure convergence rate.

In 1974, Erdős posed the following problem. Given an oriented graph H, determine or estimate the maximum possible number of H-free orientations of an n-vertex graph. When H is a tournament, the answer was determined precisely for sufficiently large n by Alon and Yuster. In general, when the underlying undirected graph of H contains a cycle, one can obtain accurate bounds by combining an observation of Kozma and Moran with celebrated results on the number of F-free graphs. As the main contribution of the paper, we resolve all remaining cases in an asymptotic sense, thereby giving a rather complete answer to Erdős’s question. Moreover, we determine the answer exactly when H is an odd cycle and n is sufficiently large, answering a question of Araújo, Botler and Mota.

An oriented graph is called singular or nonsingular according as its adjacency matrix is singular or nonsingular. In this note, by a new approach, we determine the singularity of oriented quasi-trees. The main results of Chen et al. [‘Singularity of oriented graphs from several classes’, Bull. Aust. Math. Soc. 102(1) (2020), 7–14] follow as corollaries. Furthermore, we give a necessary condition for an oriented bipartite graph to be nonsingular. By applying this condition, we characterise nonsingular oriented bipartite graphs $B_{m,n}$ when $\min \{m,n\}\leq 3$ .

A connected, locally finite graph $\Gamma $ is a Cayley–Abels graph for a totally disconnected, locally compact group G if G acts vertex-transitively on $\Gamma $ with compact, open vertex stabilizers. Define the minimal degree of G as the minimal degree of a Cayley–Abels graph of G. We relate the minimal degree in various ways to the modular function, the scale function and the structure of compact open subgroups. As an application, we prove that if $T_{d}$ denotes the d-regular tree, then the minimal degree of $\mathrm{Aut}(T_{d})$ is d for all $d\geq 2$ .

This is the second of a series of two papers dealing with local limit theorems in relatively hyperbolic groups. In this second paper, we restrict our attention to non-spectrally degenerate random walks and we prove precise asymptotics of the probability $p_n(e,e)$ of going back to the origin at time $n$. We combine techniques adapted from thermodynamic formalism with the rough estimates of the Green function given by part I to show that $p_n(e,e)\sim CR^{-n}n^{-3/2}$, where $R$ is the inverse of the spectral radius of the random walk. This both generalizes results of Woess for free products and results of Gouëzel for hyperbolic groups.

The $\chi $ -stability index $\mathrm {es}_{\chi }(G)$ of a graph G is the minimum number of its edges whose removal results in a graph with chromatic number smaller than that of G. We consider three open problems from Akbari et al. [‘Nordhaus–Gaddum and other bounds for the chromatic edge-stability number’, European J. Combin. 84 (2020), Article no. 103042]. We show by examples that a known characterisation of k-regular ( $k\le 5$ ) graphs G with $\mathrm {es}_{\chi }(G) = 1$ does not extend to $k\ge 6$ , and we characterise graphs G with $\chi (G)=3$ for which $\mathrm { es}_{\chi }(G)+\mathrm {es}_{\chi }(\overline {G}) = 2$ . We derive necessary conditions on graphs G which attain a known upper bound on $\mathrm { es}_{\chi }(G)$ in terms of the order and the chromatic number of G and show that the conditions are sufficient when $n\equiv 2 \pmod 3$ and $\chi (G)=3$ .

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion-theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof-theoretic principles which are THAs. Until the papers reported on in this communication, there was only one mathematical example. Barnes, Goh, and Shore [1] analyze an array of ubiquity theorems in graph theory descended from Halin’s [9] work on rays in graphs. They seem to be typical applications of ACA $_{0}$ but are actually THAs. These results answer Question 30 of Montalbán’s Open Questions in Reverse Mathematics [19] and supply several other natural principles of different and unusual levels of complexity.

This work led in [25] to a new neighborhood of the reverse mathematical zoo: almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own are very weak. Denizens both mathematical and logical are provided. Generalizations of several conservativity classes ( $\Pi _{1}^{1}$ , r- $\Pi _{1}^{1}$ , and Tanaka) are defined and these ATHAs as well as many other principles are shown to be conservative over RCA $_{0}$ in all these senses and weak in other recursion-theoretic ways as well. These results answer a question raised by Hirschfeldt and reported in [19] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second-order arithmetic.

We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $\hat{R}_{\mathrm{ind}}(P_n)\leq 5 \cdot 10^7n$ , thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and Łuczak. We also provide a bound for the k-colour version, showing that $\hat{R}_{\mathrm{ind}}^k(P_n)=O(k^3\log^4k)n$ . Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,\frac{1+\varepsilon}{n})$ , contains typically an induced path of length $\Theta(\varepsilon^2) n$ .

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter $\lambda $ on the unit circle in the complex plane. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics but have also been key in the recent deterministic approximation scheme for all $|\lambda |\neq 1$ by Liu, Sinclair and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle and on the tantalising question of what happens around $\lambda =1$, where, on one hand, the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability and, on the other hand, the presence of Lee–Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point $\lambda =1$ and, more generally, on the entire unit circle. For an integer $\Delta \geq 3$ and edge interaction parameter $b\in (0,1)$, we show $\mathsf {\#P}$-hardness for approximating the partition function on graphs of maximum degree $\Delta $ on the arc of the unit circle where the Lee–Yang zeros are dense. This result contrasts with known approximation algorithms when $|\lambda |\neq 1$ or when $\lambda $ is in the complementary arc around $1$ of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee–Yang zeros and the tractability of efficiently approximating the partition function on bounded-degree graphs.

Let X be a finite connected poset and K a field. We study the question, when all Lie automorphisms of the incidence algebra I(X, K) are proper. Without any restriction on the length of X, we find only a sufficient condition involving certain equivalence relation on the set of maximal chains of X. For some classes of posets of length one, such as finite connected crownless posets (i.e., without weak crown subposets), crowns, and ordinal sums of two anti-chains, we give a complete answer.

Reaction networks are commonly used within the mathematical biology and mathematical chemistry communities to model the dynamics of interacting species. These models differ from the typical graphs found in random graph theory since their vertices are constructed from elementary building blocks, i.e. the species. We consider these networks in an Erdös–Rényi framework and, under suitable assumptions, derive a threshold function for the network to have a deficiency of zero, which is a property of great interest in the reaction network community. Specifically, if the number of species is denoted by n and the edge probability by $p_n$ , then we prove that the probability of a random binary network being deficiency zero converges to 1 if $p_n\ll r(n)$ as $n \to \infty$ , and converges to 0 if $p_n \gg r(n)$ as $n \to \infty$ , where $r(n)=\frac{1}{n^3}$ .

We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma, states that for each $\epsilon>0$ there exists M such that every triangle-free graph G has an $\epsilon$ -approximate homomorphism to a triangle-free graph F on at most M vertices (here an $\epsilon$ -approximate homomorphism is a map $V(G) \to V(F)$ where all but at most $\epsilon \left\lvert{V(G)}\right\rvert^2$ edges of G are mapped to edges of F). One consequence of our results is that the least possible M in the triangle-free lemma grows faster than exponential in any polynomial in $\epsilon^{-1}$ . We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.

We introduce a notion of finite sampling consistency for phylogenetic trees and show that the set of finitely sampling-consistent and exchangeable distributions on n-leaf phylogenetic trees is a polytope. We use this polytope to show that the set of all exchangeable and sampling-consistent distributions on four-leaf phylogenetic trees is exactly Aldous’ beta-splitting model, and give a description of some of the vertices for the polytope of distributions on five leaves. We also introduce a new semialgebraic set of exchangeable and sampling consistent models we call the multinomial model and use it to characterize the set of exchangeable and sampling-consistent distributions. Using this new model, we obtain a finite de Finetti-type theorem for rooted binary trees in the style of Diaconis’ theorem on finite exchangeable sequences.

Given a fixed graph H that embeds in a surface $\Sigma$ , what is the maximum number of copies of H in an n-vertex graph G that embeds in $\Sigma$ ? We show that the answer is $\Theta(n^{f(H)})$ , where f(H) is a graph invariant called the ‘flap-number’ of H, which is independent of $\Sigma$ . This simultaneously answers two open problems posed by Eppstein ((1993) J. Graph Theory17(3) 409–416.). The same proof also answers the question for minor-closed classes. That is, if H is a $K_{3,t}$ minor-free graph, then the maximum number of copies of H in an n-vertex $K_{3,t}$ minor-free graph G is $\Theta(n^{f'(H)})$ , where f′(H) is a graph invariant closely related to the flap-number of H. Finally, when H is a complete graph we give more precise answers.

We determine the asymptotics of the number of independent sets of size $\lfloor \beta 2^{d-1} \rfloor$ in the discrete hypercube $Q_d = \{0,1\}^d$ for any fixed $\beta \in (0,1)$ as $d \to \infty$ , extending a result of Galvin for $\beta \in (1-1/\sqrt{2},1)$ . Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard-core model at any fixed fugacity $\lambda>0$ . In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.

Suppose G and H are bipartite graphs and $L: V(G)\to 2^{V(H)}$ induces a partition of $V(H)$ such that the subgraph of H induced between $L(v)$ and $L(v')$ is a matching, whenever $vv'\in E(G)$ . We show for each $\varepsilon>0$ that if H has maximum degree D and $|L(v)| \ge (1+\varepsilon )D/\log D$ for all $v\in V(G)$ , then H admits an independent transversal with respect to L, provided D is sufficiently large. This bound on the part sizes is asymptotically sharp up to a factor $2$ . We also show some asymmetric variants of this result.

The bandwidth theorem of Böttcher, Schacht and Taraz states that any n-vertex graph G with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)n$ contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). Recently, a subset of the authors proved a random graph analogue of this statement: for $p\gg \big(\tfrac{\log n}{n}\big)^{1/\Delta}$ a.a.s. each spanning subgraph G of G(n,p) with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)pn$ contains all n-vertex k-colourable graphs H with maximum degree $\Delta$ , bandwidth o(n), and at least $C p^{-2}$ vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper, we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in G contain many copies of $K_\Delta$ then we can drop the restriction on H that $Cp^{-2}$ vertices should not be in triangles.