We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, strengthening an analogous result in the random setting by Draganić, Glock, and Krivelevich. More generally, we find long induced paths in sparse graphs that satisfy a mild upper-uniformity edge-distribution condition.

A cycle C of a graph G is dominating if $V(C)$ is a dominating set and $V(G)\backslash V(C)$ is an independent set. Wu et al. [‘Degree sums and dominating cycles’, Discrete Mathematics 344 (2021), Article no. 112224] proved that every longest cycle of a k-connected graph G on $n\geq 3$ vertices with $k\geq 2$ is dominating if the degree sum is more than $(k+1)(n+1)/3$ for any $k+1$ pairwise nonadjacent vertices. They also showed that this bound is sharp. In this paper, we show that the extremal graphs G for this condition satisfy $(n-2)/3K_1\vee (n+1)/3K_2 \subseteq G \subseteq K_{(n-2)/3}\vee (n+1)/3K_2$ or $2K_1\vee 3K_{(n-2)/3}\subseteq G \subseteq K_2\vee 3K_{(n-2)/3}.$

A digraph group is a group defined by non-empty presentation with the property that each relator is of the form $R(x, y)$, where x and y are distinct generators and $R(\cdot , \cdot )$ is determined by some fixed cyclically reduced word $R(a, b)$ that involves both a and b. Associated with each such presentation is a digraph whose vertices correspond to the generators and whose arcs correspond to the relators. In this article, we consider digraph groups for strong digraphs that are digon-free and triangle-free. We classify when the digraph group is finite and show that in these cases it is cyclic, giving its order. We apply this result to the Cayley digraph of the generalized quaternion group, to circulant digraphs, and to Cartesian and direct products of strong digraphs.

The bipartite independence number of a graph $G$, denoted as $\tilde \alpha (G)$, is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a+b=k+1$ with the property that for any two disjoint sets $A,B\subseteq V(G)$ with $|A|=a$ and $|B|=b$, there is an edge between $A$ and $B$. McDiarmid and Yolov showed that if $\delta (G)\geq \tilde \alpha (G)$ then $G$ is Hamiltonian, extending the famous theorem of Dirac which states that if $\delta (G)\geq |G|/2$ then $G$ is Hamiltonian. In 1973, Bondy showed that, unless $G$ is a complete bipartite graph, Dirac’s Hamiltonicity condition also implies pancyclicity, i.e., existence of cycles of all the lengths from $3$ up to $n$. In this paper, we show that $\delta (G)\geq \tilde \alpha (G)$ implies that $G$ is pancyclic or that $G=K_{\frac{n}{2},\frac{n}{2}}$, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.

In 1964, Erdős proposed the problem of estimating the Turán number of the d-dimensional hypercube $Q_d$. Since $Q_d$ is a bipartite graph with maximum degree d, it follows from results of Füredi and Alon, Krivelevich, Sudakov that $\mathrm {ex}(n,Q_d)=O_d(n^{2-1/d})$. A recent general result of Sudakov and Tomon implies the slightly stronger bound $\mathrm {ex}(n,Q_d)=o(n^{2-1/d})$. We obtain the first power-improvement for this old problem by showing that $\mathrm {ex}(n,Q_d)=O_d\left (n^{2-\frac {1}{d-1}+\frac {1}{(d-1)2^{d-1}}}\right )$. This answers a question of Liu. Moreover, our techniques give a power improvement for a larger class of graphs than cubes.

We use a similar method to prove that any n-vertex, properly edge-coloured graph without a rainbow cycle has at most $O(n(\log n)^2)$ edges, improving the previous best bound of $n(\log n)^{2+o(1)}$ by Tomon. Furthermore, we show that any properly edge-coloured n-vertex graph with $\omega (n\log n)$ edges contains a cycle which is almost rainbow: that is, almost all edges in it have a unique colour. This latter result is tight.

A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh, and Staden proved that for large $d$, among all graphs with minimum degree $d$, $K_{d+1}$ minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one ($\approx 2^{d+1}$). Among others, our bound implies that an $n$-vertex $C_4$-free graph with minimum degree $d$ contains at least $n2^{d^{2-o(1)}}$ Hamiltonian subsets.

In this paper, we consider the friendship paradox in the context of random walks and paths. Among our results, we give an equality connecting long-range degree correlation, degree variability, and the degree-wise effect of additional steps for a random walk on a graph. Random paths are also considered, as well as applications to acquaintance sampling in the context of core-periphery structure.

The Ramsey number $R(F,H)$ is the minimum number N such that any N-vertex graph either contains a copy of F or its complement contains H. Burr in 1981 proved a pleasingly general result that, for any graph H, provided n is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n,H)=(n-1)(\chi (H)-1)+\sigma (H)$ , where $\sigma (H)$ is the minimum possible size of a colour class in a $\chi (H)$ -colouring of H. Allen, Brightwell and Skokan conjectured that the same should be true already when $n\geq \lvert H\rvert \chi (H)$ .

We improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C\lvert H\rvert \log ^4\chi (H)$ , which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen–Brightwell–Skokan conjecture for all graphs H with large chromatic number.

Given a family $\mathcal{F}$ of bipartite graphs, the Zarankiewicz number $z(m,n,\mathcal{F})$ is the maximum number of edges in an $m$ by $n$ bipartite graph $G$ that does not contain any member of $\mathcal{F}$ as a subgraph (such $G$ is called $\mathcal{F}$ -free). For $1\leq \beta \lt \alpha \lt 2$ , a family $\mathcal{F}$ of bipartite graphs is $(\alpha,\beta )$ -smooth if for some $\rho \gt 0$ and every $m\leq n$ , $z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$ . Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any $(\alpha,\beta )$ -smooth family $\mathcal{F}$ , there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$ , any $n$ -vertex $\mathcal{F}\cup \{C_k\}$ -free graph with minimum degree at least $\rho (\frac{2n}{5}+o(n))^{\alpha -1}$ is bipartite. In this paper, we strengthen their result by showing that for every real $\delta \gt 0$ , there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$ , any $n$ -vertex $\mathcal{F}\cup \{C_k\}$ -free graph with minimum degree at least $\delta n^{\alpha -1}$ is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families $\mathcal{F}$ consisting of the single graph $K_{s,t}$ when $t\gg s$ . We also prove an analogous result for $C_{2\ell }$ -free graphs for every $\ell \geq 2$ , which complements a result of Keevash, Sudakov and Verstraëte.

In 1999, Jacobson and Lehel conjectured that, for $k \geq 3$ , every k-regular Hamiltonian graph has cycles of $\Theta (n)$ many different lengths. This was further strengthened by Verstraëte, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least $3$ . Despite attention from various researchers, until now, the best partial result towards both of these conjectures was a $\sqrt {n}$ lower bound on the number of cycle lengths. We resolve these conjectures asymptotically by showing that the number of cycle lengths is at least $n^{1-o(1)}$ .

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 Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. In this paper we introduce a new neighborhood of theorems which are almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own they are very weak. We generalize several conservativity classes ( $\Pi _{1}^{1}$ , r- $\Pi _{2}^{1}$ , and Tanaka) and show that all our examples (and many others) are conservative over RCA $_{0}$ in all these senses and weak in other recursion theoretic ways as well. We provide denizens, both mathematical and logical. These results answer a question raised by Hirschfeldt and reported in Montalbán [2011] 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.

For a subgraph $G$ of the blow-up of a graph $F$ , we let $\delta ^*(G)$ be the smallest minimum degree over all of the bipartite subgraphs of $G$ induced by pairs of parts that correspond to edges of $F$ . Johansson proved that if $G$ is a spanning subgraph of the blow-up of $C_3$ with parts of size $n$ and $\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$ , then $G$ contains $n$ vertex disjoint triangles, and presented the following conjecture of Häggkvist. If $G$ is a spanning subgraph of the blow-up of $C_k$ with parts of size $n$ and $\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$ , then $G$ contains $n$ vertex disjoint copies of $C_k$ such that each $C_k$ intersects each of the $k$ parts exactly once. A similar conjecture was also made by Fischer and the case $k=3$ was proved for large $n$ by Magyar and Martin.

In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of $G$ to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically.

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

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.

A graph G is called a $(P_{\geq n},k)$ -factor-critical covered graph if for any $Q\subseteq V(G)$ with $|Q|=k$ and any $e\in E(G-Q)$ , $G-Q$ has a $P_{\geq n}$ -factor covering e. We demonstrate that (i) a $(k+1)$ -connected graph G with at least $k+3$ vertices is a $(P_{\geq 3},k)$ -factor-critical covered graph if its toughness $t(G)>{(2+k)}/{3}$ ; (ii) a $(k+2)$ -connected graph G is a $(P_{\geq 3},k)$ -factor-critical covered graph if its isolated toughness $I(G)>{(5+k)}/{3}$ . Furthermore, we show that the conditions on $t(G)$ and $I(G)$ are sharp.

A graph G arrows a graph H if in every 2-edge-colouring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph $K_n$ arrows a small graph H, then every ‘dense’ subgraph of $K_n$ also arrows H, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large n, if $n = 3t+r$ where $r \in \{0,1,2\}$ and G is an n-vertex graph with $\delta(G) \ge (3n-1)/4$ , then for every 2-edge-colouring of G, either there are cycles of every length $\{3, 4, 5, \dots, 2t+r\}$ of the same colour, or there are cycles of every even length $\{4, 6, 8, \dots, 2t+2\}$ of the samecolour.

Our result is tight in the sense that no longer cycles (of length $>2t+r$ ) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large n, every $(3t-1)$ -vertex graph G with minimum degree larger than $3|V(G)|/4$ arrows the path $P_{2n}$ with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for $n=3t+r$ where $r \in \{0,1,2\}$ and every n-vertex graph G with $\delta(G) \ge 3n/4$ , in each 2-edge-colouring of G there exists a monochromatic cycle of length at least $2t+r$ .

In this short note we prove that every tournament contains the k-th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when k=2, showing that there is always a square of a directed path of length , which is best possible.

Magnant and Martin conjectured that the vertex set of any d-regular graph G on n vertices can be partitioned into $n / (d+1)$ paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when $d = \Omega(n)$ , improving a result of Han, who showed that in this range almost all vertices of G can be covered by $n / (d+1) + 1$ vertex-disjoint paths. In fact our proof gives a partition of V(G) into cycles. We also show that, if $d = \Omega(n)$ and G is bipartite, then V(G) can be partitioned into n/(2d) paths (this bound is tight for bipartite graphs).

In this note we study the emergence of Hamiltonian Berge cycles in random r-uniform hypergraphs. For $r\geq 3$ we prove an optimal stopping time result that if edges are sequentially added to an initially empty r-graph, then as soon as the minimum degree is at least 2, the hypergraph with high probability has such a cycle. In particular, this determines the threshold probability for Berge Hamiltonicity of the Erdős–Rényi random r-graph, and we also show that the 2-out random r-graph with high probability has such a cycle. We obtain similar results for weak Berge cycles as well, thus resolving a conjecture of Poole.