Note on Long Directed Cycles in Eulerian Digraphs
Jiangdong Ai Gregory Gutin Fankang He Anders Yeo · 2025
Read Note on Long Directed Cycles in Eulerian Digraphs by Jiangdong Ai Gregory Gutin Fankang He Anders Yeo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26426.txt.
Introduction
Jiangdong Ai, Gregory Gutin, Fankang He, and Anders Yeo write a short note on directed cycles in Eulerian digraphs. A digraph is a network of one-way links, and it is Eulerian when links balance at each point. A 2013 result showed that such a network with average out-degree d must contain a directed loop at least the square root of d long.
Catalog record
| CREATOR | Jiangdong Ai Gregory Gutin Fankang He Anders Yeo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 7 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26426
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Note on Long Directed Cycles in Eulerian Digraphs Jiangdong Ai Gregory Gutin Fankang He Anders Yeo Abstract Huang, Ma, Shapira, Sudakov and Yuster (Comb. Prob. Comput. 2013) proved that every Eulerian digraph of average out-degree d d has a directed cycle of length at least d . \sqrt{d}. We improve the lower bound from d \sqrt{d} to 2 d − 3 / 2 . \sqrt{2d}-3/2. 1 Introduction In this paper, digraphs do not have loops or multiple arcs. A digraph is Eulerian if it is strongly connected and the out-degree of every vertex is equal to its in-degree. Bollobás and Scott [ 3 ] stated the following conjecture. Conjecture 1.1 ( [ 3 ] ) . Every n -vertex Eulerian digraph G with a weight function w:A(G)\to\mathbb{R}_{\geq 0} has a directed cycle of length at least c\,\cdot\,w(G)/n for some universal constant c>0 . Huang, Ma, Shapira, Sudakov and Yuster [ 5 ] suggested trying to resolve the following two weaker versions of Bollobás-Scott conjecture as the first step in its resolution. Conjecture 1.2 . Every Eulerian digraph with average out-degree d has a directed cycle of length at least cd for some universal constant c>0 . Conjecture 1.3 . Every Eulerian digraph with average out-degree d has a directed path of length at least cd for some universal constant c>0 . The authors of [ 5 ] proved that every n -vertex Eulerian digraph with average out-degree d has a directed cycle of length at least \sqrt{d} , and hence it has a directed path of length \sqrt{d}-1 . Janzer, Sudakov and Tomon [ 6 ] first broke the \sqrt{d} barrier for paths by showing the existence of a directed path of length at least d^{1/2+\epsilon} , where \epsilon=1/40 . In fact, they proved a slightly stronger result that every vertex can start such a directed path. Subsequently, Knierim, Larcher and Martinsson [ 7 ] gave an almost linear bound by showing that there is a directed path of length at least d/(\log d+1) in such digraphs. However, for the existence of long cycles, \sqrt{d} obtained in [ 5 ] is still the best-known lower bound. If we take maximum degree into account, Knierim, Larcher, Martinsson and Noever [ 8 ] proved that an Eulerian digraph D with average out-degree d and maximum degree \Delta has a directed cycle of length at least \Omega(d/\log\Delta) by using a random walk technique. Moreover, they remarked that it seems likely that an \Omega(d/\log d) bound can be obtained by using their approach more carefully. However, no existing paper does this. The authors of [ 5 ] recall the argument using the DFS tree to find long cycles in undirected graphs and remarked that simply using such an argument in digraph settings will fail. They also pointed out that a possible reason that this approach fails is the fact that not all non-tree arcs are back arcs , that is, arcs directed from vertices to their ancestors. In this note, we use a final out-branching instead of a DFS tree to give the following result which improves the multiplicity constant of the result of Huang, Ma, Shapira, Sudakov and Yuster [ 5 ] . Theorem 1.4 . Let D be an n -vertex Eulerian digraph with average out-degree d . Then there is a directed cycle of length at least \sqrt{2d}-3/2 . 2 Proofs An out-tree T in a digraph D is an oriented tree in which every vertex, apart from one called the root of T , has in-degree 1. An out-forest is a disjoint union of out-trees and an out-branching of D is a spanning out-tree of D . Let D be a Eulerian digraph. Since D is strongly connected, it has an out-branching F_{0} (see, e.g., Proposition 1.8.1 in [ 2 ] ). For each out-branching of D rooted at v_{0} , we say a vertex u is in level i , L_{i} , if the unique directed path in F_{0} from v_{0} to u is of length i . If L_{i} and L_{j} are two levels and i<j then we say that L_{i} is a lower level and L_{j} is an upper level . The notion of a final spanning out-forest was explicitly introduced by El Sahili and Kouider [ 4 ] to solve a special case of Burr’s conjecture on oriented paths with two blocks. (The term final spanning out-forest was coined in [ 1 ] .) Let us recall the notion to make this note self-contained. For the same reason, we give proofs of the following lemmas. Let F be an out-branching of D . Suppose D has an arc uv that is not a back arc, where u lies at level i , v lies at level j and i\geq j . Then we can obtain a new out-branching F^{\prime} of D by adding arc u removing the arc of F with head v . We call above operation an elementary operation . Note that we can iteratively apply elementary operations on out-branchings of D until no such arcs exist, since each time we apply elementary operation there is a vertex going to an upper level. An out-branching is a final out-branching if we can not apply the elementary operation on it. By the definition of a final out-branching, we have the following lemma guaranteeing that all arcs sending from upper levels to lower levels are back arcs. Recall that an arc uv in a digraph D with out-branching F is a back arc if u is in an upper level than v and there is a directed path in F from u to v. Lemma 2.1 . Let F be a final out-branching of D . Then all arcs directed from upper levels to lower levels are back arcs. Moreover, each level is an independent set. Given a digraph D and W\subseteq V(D) , we use d^{+}(W) to denote the number of arcs from W to V(D)\setminus W and d^{-}(W) to denote the number of arcs from V(D)\setminus W to W . The following lemma is well known, see, e.g., Proposition 4.1.1 in [ 2 ] . Lemma 2.2 . Let D be an Eulerian digraph and W\subseteq V(D) , then d^{+}(W)=d^{-}(W) . Proof. Note that d^{+}(W)=\sum_{v\in W}d^{+}(v)-|A(D[W])|, and d^{-}(W)=\sum_{v\in W}d^{-}(v)-|A(D[W])|. Since D is Eulerian, we have d^{+}(x)=d^{-}(x) for every x\in V(D) . This yields d^{+}(W)=d^{-}(W) . ∎ Proof of Theorem 1.4 . Suppose the longest directed cycle in D is of length t . Take F as a final out-branching of D , then the number of back arcs is at most n(t-1) , since each vertex can send at most t-1 arcs to its ancestors otherwise there will be a directed cycle of length at least t+1 which contradicts the fact that the circumference of D is t . We call the arcs of D from lower levels of F to upper levels of F forward arcs . Note that the arcs in F are also forward arcs. Claim 2.3 . The number of forward arcs is at most nt(t+1)/2 . Let L_{i} be the set of vertices at i , and L_{\leq i}=\bigcup_{0\leq j\leq i}L_{j} . By Lemma 2.2 and Lemma 2.1