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.

We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $\delta \in (0,1)$ there exists $C = C(\delta ) \gt 0$ such that the following holds. Let $D_0$ be an $n$-vertex digraph with minimum semidegree at least $\delta n$ and suppose that each edge of the union of $D_0$ with a copy of the random digraph $\mathbf{D}(n,C/n)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup \mathbf{D}(n,C/n)$ has a rainbow directed Hamilton cycle.

This improves a result of Aigner-Horev and Hefetz ((2021) SIAM J. Discrete Math. 35(3) 1569–1577), who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon )n$ colours.

We show that for every $\eta \gt 0$ every sufficiently large $n$-vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta )\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs.

Further, we show that in the same setting, $D$ contains every $k$-edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$.

Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$.

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha \gt 0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery.

We recall several categories of graphs which are useful for describing homotopy-coherent versions of generalised operads (e.g. cyclic operads, modular operads, properads, and so on), and give new, uniform definitions for their morphisms. This allows for straightforward comparisons, and we use this to show that certain free-forgetful adjunctions between categories of generalised operads can be realised at the level of presheaves. This includes adjunctions between operads and cyclic operads, between dioperads and augmented cyclic operads, and between wheeled properads and modular operads.

We introduce the combinatorial notion of a q-factorization graph intended as a tool to study and express results related to the classification of prime simple modules for quantum affine algebras. These are directed graphs equipped with three decorations: a coloring and a weight map on vertices, and an exponent map on arrows (the exponent map can be seen as a weight map on arrows). Such graphs do not contain oriented cycles and, hence, the set of arrows induces a partial order on the set of vertices. In this first paper on the topic, beside setting the theoretical base of the concept, we establish several criteria for deciding whether or not a tensor product of two simple modules is a highest-$\ell $-weight module and use such criteria to prove, for type A, that a simple module whose q-factorization graph has a totally ordered vertex set is prime.

Negative dependence of sequences of random variables is often an interesting characteristic of their distribution, as well as a useful tool for studying various asymptotic results, including central limit theorems, Poisson approximations, the rate of increase of the maximum, and more. In the study of probability models of tournaments, negative dependence of participants’ outcomes arises naturally, with application to various asymptotic results. In particular, the property of negative orthant dependence was proved in several articles for different tournament models, with a special proof for each model. In this note we unify these results by proving a stronger property, negative association, a generalization leading to a very simple proof. We also present a natural example of a knockout tournament where the scores are negatively orthant dependent but not negatively associated. The proof requires a new result on a preservation property of negative orthant dependence that is of independent interest.

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.

We consider the component structure of the random digraph D(n,p) inside the critical window $p = n^{-1} + \lambda n^{-4/3}$ . We show that the largest component $\mathcal{C}_1$ has size of order $n^{1/3}$ in this range. In particular we give explicit bounds on the tail probabilities of $|\mathcal{C}_1|n^{-1/3}$ .

Kostochka and Thomason independently showed that any graph with average degree $\Omega(r\sqrt{\log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $\Omega(r\sqrt{\log r})$ contains a $K_r$ minor, a partial result towards Hadwiger’s famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong $\overrightarrow{K}_{\!\!r}$ minor is a digraph whose vertex set is partitioned into r parts such that each part induces a strongly connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong $\overrightarrow{K}_{\!\!r}$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least 2r contains a strong $\overrightarrow{K}_{\!\!r}$ minor, and any tournament with minimum out-degree $\Omega(r\sqrt{\log r})$ also contains a strong $\overrightarrow{K}_{\!\!r}$ minor. The latter result is tight up to the implied constant and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function $f\;:\;\mathbb{N} \rightarrow \mathbb{N}$ such that any digraph with minimum out-degree at least f(r) contains a strong $\overrightarrow{K}_{\!\!r}$ minor, but such a function exists when considering dichromatic number.

In a classical chess round-robin tournament, each of $n$ players wins, draws, or loses a game against each of the other $n-1$ players. A win rewards a player with 1 points, a draw with 1/2 point, and a loss with 0 points. We are interested in the distribution of the scores associated with ranks of $n$ players after ${{n \choose 2}}$ games, that is, the distribution of the maximal score, second maximum, and so on. The exact distribution for a general $n$ seems impossible to obtain; we obtain a limit distribution.

We introduce and study analogues of expander and hyperfinite graph sequences in the context of directed acyclic graphs, which we call ‘extender’ and ‘hypershallow’ graph sequences, respectively. Our main result is a probabilistic construction of non-hypershallow graph sequences.

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.

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.

A diregular bipartite tournament is a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in- and out-degree. In 1981 Jackson showed that a diregular bipartite tournament contains a Hamilton cycle, and conjectured that in fact its edge set can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: for every ε > 0 there exists n0 such that every diregular bipartite tournament on 2n ≥ n0 vertices contains a collection of (1/2–ε)n cycles of length at least (2–ε)n. Increasing the degree by a small proportion allows us to prove the existence of many Hamilton cycles: for every c > 1/2 and ε > 0 there exists n0 such that every cn-regular bipartite digraph on 2n ≥ n0 vertices contains (1−ε)cn edge-disjoint Hamilton cycles.

Let $\{D_M\}_{M\geq 0}$ be the n-vertex random directed graph process, where $D_0$ is the empty directed graph on n vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $$\varepsilon > 0$$ , we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $1/2-\varepsilon$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\varepsilon)$ -resiliently Hamiltonian. Furthermore, for each $\varepsilon > 0$ , we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\varepsilon)$ -resiliently Hamiltonian.

This improves a result of Ferber, Nenadov, Noever, Peter and Škorić who showed, for each $\varepsilon > 0$ , that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\varepsilon)$ -resiliently Hamiltonian if $p=\omega(\log^8n/n)$ .

In this paper we show that every non-cycle finite transitive directed graph has a Cuntz–Krieger family whose WOT-closed algebra is $B(\mathcal {H})$. This is accomplished through a new construction that reduces this problem to in-degree 2-regular graphs, which is then treated by applying the periodic Road Colouring Theorem of Béal and Perrin. As a consequence we show that finite disjoint unions of finite transitive directed graphs are exactly those finite graphs which admit self-adjoint free semigroupoid algebras.

We conjecture that bounded generalised polynomial functions cannot be generated by finite automata, except for the trivial case when they are ultimately periodic.

Using methods from ergodic theory, we are able to partially resolve this conjecture, proving that any hypothetical counterexample is periodic away from a very sparse and structured set. In particular, we show that for a polynomial $p(n)$ with at least one irrational coefficient (except for the constant one) and integer $m\geqslant 2$, the sequence $\lfloor p(n)\rfloor \hspace{0.2em}{\rm mod}\hspace{0.2em}m$ is never automatic.

We also prove that the conjecture is equivalent to the claim that the set of powers of an integer $k\geqslant 2$ is not given by a generalised polynomial.

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.