An equality for balanced digraphs
Darij Grinberg, Benjamin Liber · 2025
Read An equality for balanced digraphs by Darij Grinberg, Benjamin Liber (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-2507-22388.txt.
Introduction
Darij Grinberg and Benjamin Liber prove a counting equality for balanced directed graphs in a 2025 math paper. A balanced graph sends as many arrows into each point as it sends out. Pick a root point, and count the sets of arrows that reach every point from the root's view without forming a loop.
They show that this count does not depend on which root you pick. The claim is the same for every root in the graph. It gathers older facts about spanning trees and acyclic arrow patterns into one roof. The authors push the result further, swapping the no-loop rule for a fixed set of allowed loops.
Catalog record
| CREATOR | Darij Grinberg, Benjamin Liber |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22388
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An equality for balanced digraphs Darij Grinberg, Benjamin Liber Abstract Consider a directed multigraph D D that is balanced (i.e., at each vertex, the indegree equals the outdegree). Let A A be its set of arcs. Fix an integer k k . Let s s be a vertex of D D . We show that the number of k k -element subsets B B of A A that contain no cycles but contain a path from each vertex to s s (we call them “ s s -convergences”) is independent on s s . This generalizes known facts about spanning arborescences, acyclic orientations and maximal acyclic subdigraphs (or, equivalently, minimum feedback arc sets). 1 The theorem In this note, we shall discuss balanced multidigraphs – i.e., directed multigraphs (allowing loops and multiple arcs) in which each vertex satisfies “outdegree = indegree”. We recall the relevant definitions in more detail: A multidigraph (henceforth just digraph ) means a triple (V,A,\psi) , where V and A are two finite sets and \psi:A\rightarrow V\times V is a map. The elements of V are called the vertices of this digraph, and the elements of A are called the arcs of this digraph. The source and target of an arc a\in A are, respectively, the first and second entries of the pair \psi(a) . The indegree \deg^{-}v of a vertex v\in V means the number of arcs a\in A whose target is v . The outdegree \deg^{+}v of a vertex v\in V means the number of arcs a\in A whose source is v . We say that a digraph (V,A,\psi) is balanced if and only if each vertex v\in V satisfies \deg^{+}v=\deg^{-}v . For further terminology on digraphs, we refer to [ 22s ] . 1 1 1 The famous directed Euler–Hierholzer theorem (which will not be used in this note) says that a weakly connected digraph has an Eulerian circuit if and only if it is balanced. Thus, weakly connected balanced digraphs are also known as Eulerian digraphs . A to-root of a digraph D means a vertex s of D such that for each vertex v of D , the digraph D has a path from v to s (equivalently, a walk from v to s ). From now on, we fix a balanced digraph D=(V,A,\psi) . If B is any subset of A , then D\left\langle B\right\rangle will denote the induced subdigraph \left(V,B,\psi\mid_{B}\right) . A subset B of A will be called acyclic if the subdigraph D\left\langle B\right\rangle has no cycles. (“Cycle” always means “directed cycle”, as in [ 22s , Definition 4.5.1] .) Given a vertex s of D , we define an s -convergence to be an acyclic subset B of A such that s is a to-root of the subdigraph D\left\langle B\right\rangle . We can think of an s -convergence as a set B of arcs of D such that by following the B -arcs (i.e. the arcs in B ) from any vertex v\in V , we will always arrive at s (no matter which B -arcs we take), and we will be stuck at s . (This intuition is formalized in Proposition 4.1 .) For any k\in\mathbb{N} and s\in V , we let \gamma_{k}\left(s\right) denote the number of s -convergences of size k (that is, with k arcs). 2 2 2 The symbol \mathbb{N} denotes the set \left\{0,1,2,\ldots\right\} . In this note, we shall prove the following result: Theorem 1.1 . Let k\in\mathbb{N} . Then, the number \gamma_{k}\left(s\right) does not depend on s . That is, \gamma_{k}\left(s\right)=\gamma_{k}\left(t\right) for any s,t\in V . Example 1.2 . Let D be the following balanced multidigraph: 1 2 3 4 a b c d e f g Then, the 1 -convergences are the subsets \left\{b,d,g\right\},\ \ \ \ \ \ \ \ \ \ \left\{b,d,e\right\},\ \ \ \ \ \ \ \ \ \ \left\{c,d,g\right\},\ \ \ \ \ \ \ \ \ \ \left\{b,d,e,g\right\},\ \ \ \ \ \ \ \ \ \ \left\{b,c,d,g\right\}. Hence, \gamma_{3}\left(1\right)=3 , \gamma_{4}\left(1\right)=2 , and \gamma_{k}\left(1\right)=0 for all k\notin\left\{3,4\right\} . As a visual aid, below is the spanning subdigraph D\left\langle B\right\rangle for B=\left\{b,d,e,g\right\} : 1 2 3 4 b d e g Theorem 1.1 says that for all v\in\{1,2,3,4\} , we have \gamma_{3}(v)=3 , \gamma_{4}(v)=2 , and \gamma_{k}(v)=0 for all k\notin\{3,4\} . For example, the 2 -convergences are the subsets \left\{a,d,e\right\},\ \ \ \ \ \ \ \ \ \ \left\{a,d,g\right\},\ \ \ \ \ \ \ \ \ \ \left\{d,e,f\right\},\ \ \ \ \ \ \ \ \ \ \left\{a,d,e,f\right\},\ \ \ \ \ \ \ \ \ \ \left\{a,d,e,g\right\}. Hence, \gamma_{3}(2)=3=\gamma_{3}(1) , \gamma_{4}(2)=2=\gamma_{4}(1) , and \gamma_{k}(2)=0=\gamma_{k}(1) for all k\notin\{3,4\} . The same holds for v\in\left\{3,4\right\} . 2 Particular cases Theorem 1.1 was inspired by a talk of Karla Leipold (NORCOM 2025), which made the first author aware of [ LeiVal24 , Lemma 4.1] and [ PerPha15 , §3.1] . The talk discussed no enumerative questions, yet was haunted by a perceptible aura of identities. The present note follows this aura to its source. Some particular cases of Theorem 1.1 are known: 1. When k=\left|V\right|-1 , the s -convergences B of size k (or, more precisely, the respective subdigraphs D\left\langle B\right\rangle of D ) are precisely the spanning arborescences of D rooted to s (see [ 22s , Definition 5.10.1 (b) ] for the definition of this). Indeed, the condition \left|B\right|=\left|V\right|-1 , combined with the to-rootness of s , forces D\left\langle B\right\rangle to be an arborescence rooted to s (by [ 22s , Theorem 5.10.5] ), and conversely, if D\left\langle B\right\rangle is a spanning arborescence rooted to s , then [ 22s , Theorem 5.10.5] shows that B is acyclic and \left|B\right|=\left|V\right|-1 . Thus, in the case k=\left|V\right|-1 , Theorem 1.1 is just [ 22s , Corollary 5.12.1] . Likewise, if k<\left|V\right|-1 , then Theorem 1.1 is just saying that 0=0 , since a spanning subdigraph D\left\langle B\right\rangle with fewer than \left|V\right|-1 arcs cannot have a to-root. 2. If D=G^{\operatorname*{bidir}} for some undirected multigraph G=\left(V,E,\varphi\right) (this means that D is obtained from G by replacing each edge e with two arcs e^{\rightarrow} and e^{\leftarrow} , going in opposite directions), and if k=\left|E\right|=\left|A\right|/2 , then the s -convergences B of size k are just the acyclic orientations of G with unique sink s (because the acyclicity condition forbids B from containing both e^{\rightarrow} and e^{\leftarrow} for any given edge e\in E , but the size condition \left|B\right|=k=\left|E\right| forces B to contain at least one of these two arcs; see Proposition 4.1 for the uniqueness of the sink). Thus, in this case, Theorem 1.1 is saying that the number of acyclic orientations of a given multigraph G with unique sink s does not depend on s . This is part of a result by Greene and Zaslavsky [ GreZas83 , Theorem 7.3] , proved using hyperplane arrangements, and has recently been reproved combinatorially by Foissy [ Foissy22 , Proposition 4.6] . 3. Up to reversing the directions of the arcs, [ PerPha15 , Proposition 3.7] is Theorem 1.1 for a specific value of k – namely, for the maximum possible that makes \gamma_{k}\left(s\right) nonzero. We note that when D is weakly connected, then this maximum k