On converse invariant trees of diameter four
Fernando Afonso · 2026
Read On converse invariant trees of diameter four by Fernando Afonso (2026) 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-2606-24739.txt.
Introduction
Fernando Afonso disproves a conjecture about converse invariant orientations of trees. Count copies of an oriented graph inside every tournament, where each edge of a complete graph gets a direction. An orientation is converse invariant if reversing all its arcs never changes that count. Ai and colleagues had conjectured a full description of such tree orientations. They claimed every example is self converse or built by recursive bridge mirroring from a path.
Afonso classifies the converse invariant orientations of trees of diameter four. The classification turns up examples that are not self converse and do not arise from bridge mirroring, refuting the conjecture. His main tool is a new polynomial. It encodes the difference between copy counts for an orientation and its converse. A formula writes it as a signed sum over subgraphs. The method also yields parity obstructions and fresh proofs that oriented paths and cycles are converse invariant.
Catalog record
| CREATOR | Fernando Afonso |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24739
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On converse invariant trees of diameter four Fernando Afonso Abstract Let D D be an oriented graph, and let f T ( D ) f_{T}(D) denote the number of copies of D D in a tournament T T . We say that D D is converse invariant if f T ( D ) = f T ( D ¯ ) f_{T}(D)=f_{T}(\overline{D}) for every tournament T T , where D ¯ \overline{D} is obtained from D D by reversing all arcs. Ai, Gutin, Lei, Yeo, and Zhou introduced a digraph polynomial for studying this property and conjectured that an orientation of a tree of maximum degree at least 3 3 is converse invariant if and only if it is self-converse or can be obtained recursively by bridge-mirroring from an orientation of a path. We disprove this conjecture. More precisely, we characterize converse-invariant orientations of trees of diameter four and exhibit non-self-converse examples that do not arise from the recursive bridge-mirroring construction. To prove the classification, we introduce a multilinear polynomial P D P_{D} encoding the difference f T ( D ) − f T ( D ¯ ) f_{T}(D)-f_{T}(\overline{D}) over all tournaments T T , and we give a coefficient formula for P D P_{D} as a signed sum over copies of subgraphs of the underlying graph of D D . This polynomial method yields parity obstructions, gives new proofs that oriented paths and cycles are converse invariant, and provides the main tool for the diameter-four classification. theorem]Lemma theorem]Proposition theorem]Claim theorem]Example theorem]Corollary theorem]Fact theorem]Question theorem]Problem theorem]Conjecture theorem]Definition theorem]Remark theorem]Hole 1 Introduction Let D be an oriented graph, i.e., a simple digraph without loops and having no opposite pairs of directed edges, and T be a tournament. We denote by f_{T}(D) the number of copies of D in T , i.e., the number of subdigraphs of T isomorphic to D , and by \overline{D} the converse oriented graph of D , i.e., the oriented graph obtained from D by changing the direction of every arc of D . In this paper, we are interested in studying oriented graphs D that satisfy f_{T}(D)=f_{\overline{T}}(D) , or, equivalently, f_{T}(D)=f_{T}({\overline{D}}) , for every tournament T . We say that the oriented graph is converse invariant if this condition holds. An oriented graph D is called self-converse if D and \overline{D} are isomorphic oriented graphs. Clearly, every self-converse oriented graph is converse invariant. In 2023, El Sahili and Hanna [ 2 ] asked whether it is possible to characterize the converse invariant digraphs, and found the first family of converse invariant digraphs that are not necessarily self-converse: {theorem} [ (El Sahili, Hanna) [ 2 ] ] Every oriented path and cycle is converse invariant. More recently, in 2025, Ai, Gutin, Lei, Yeo, and Zhou [ 1 ] classified converse invariant oriented trees of diameter at most 3: {theorem} [ (Ai, Gutin, Lei, Yeo, Zhou) [ 1 ] ] Let D be an orientation of a tree with diameter at most three that is not a path. Then D is converse invariant if and only if it is self-converse, or D or its converse is isomorphic to the digraph shown in Figure 1 . Figure 1: A converse invariant tree of diameter 3 For a digraph D and u\in V(D) , the bridge-mirroring of D at the vertex u is the digraph obtained by taking two copies of D and adding an arc between the two vertices corresponding to u . This operation was introduced by Zhao and Zhou [ 3 ] . In [ 1 ] , it was proved that the bridge-mirroring preserves the converse invariance property. Furthermore, the authors conjecture that this is essentially the only way to produce converse invariant trees: {conjecture} [ (Ai, Gutin, Lei, Yeo, Zhou) [ 1 ] ] Let T be an orientation of a tree with maximum degree at least 3. Then T is converse invariant if and only if it is self-converse or T can be obtained by the bridge-mirroring operation recursively from an orientation of a path. In this paper, we disprove Conjecture 1 , and introduce a new polynomial that encodes the orientations of a tournament that allow us to find new obstructions for a digraph to be converse invariant (Theorem 3 ), give new proofs of Theorems 1 and 1 and characterize the converse invariant diameter-four trees as follows: {definition} Let h\geqslant 1 . An oriented tree T belongs to the family \mathcal{E}_{4} if it is constructed as follows. Start with a path x-u-y and attach 2h leaves to each of the three vertices x,u,y . Orient the 2h pendant edges incident with each of x,u,y so that exactly h of them point away from the center and exactly h point towards the center. Finally, orient the two edges xu and uy either both towards u , or both away from u . Equivalently, T is obtained from three copies of the same balanced oriented star by identifying their centers with the vertices of a path of length two, and orienting the two edges of this path so that the middle vertex is either a source or a sink. Our main result, proved in Section 4.3 , is the following classification of diameter-four converse invariant trees: {theorem} Let T be an orientation of a tree of diameter four which is not a path. Then T is converse invariant if and only if either T is self-converse or T\in\mathcal{E}_{4} . 2 Preliminaries It is enough to test converse invariance on tournaments with exactly |V(D)| vertices. Indeed, if the equality holds for every tournament on |V(D)| vertices and T is a larger tournament, then summing the equality over all |V(D)| -vertex subtournaments of T gives f_{T}(D)=f_{T}(\overline{D}) , since each copy of D uses exactly |V(D)| vertices. Throughout the paper, \textrm{UG}(D) denotes the underlying graph of D , obtained from D by ignoring the orientations of the edges. Let D be an oriented graph on n vertices and put e(D)=|E(D)| . We shall associate to D a multilinear polynomial P_{D} whose non-vanishing on a point of \{\pm 1\}^{\binom{n}{2}} is equivalent to the existence of a tournament T with f_{T}(D)\neq f_{T}(\overline{D}) . Index the vertices of both D and a tournament T by [n]=\{1,\dots,n\} . For each unordered pair ij , let x_{ij}=x_{ji} be 1 if the edge of T is directed from \min(i,j) to \max(i,j) , and -1 otherwise. Similarly, for each edge ij\in E(D) , let y_{ij}=y_{ji} be 1 if the arc of D is directed from \min(i,j) to \max(i,j) , and -1 otherwise. When D is acyclic, we shall always choose a topological labeling of D , so that y_{ij}=1 for every edge ij\in E(D) . For a permutation \pi\in S_{n} , we embed vertex i of D into vertex \pi(i) of T . This embedding is a copy of D if and only if x_{\pi(i)\pi(j)}y_{ij}(-1)^{(ij)_{\pi}}=1 for every ij\in E(D) , where (ij)_{\pi}=0 if \pi(i)<\pi(j) and (ij)_{\pi}=1 otherwise. Therefore f_{T}(D)=\frac{1}{|\text{Aut}(D)|}\sum_{\pi\in S_{n}}\prod_{ij\in E(D)}\frac{1+x_{\pi(i)\pi(j)}y_{ij}(-1)^{(ij)_{\pi}}}{2}. We write \mathop{\text{\rm emb}}\nolimits_{T}(D) for the number of labeled embeddings of D into T . Thus f_{T}(D)=\frac{\mathop{\text{\rm emb}}\nolimits_{T}(D)}{|\text{Aut}(D)|}. We define \displaystyle P_{D}(\underline{x}) \displaystyle\coloneqq 2^{e(D)}|\text{Aut}(D)|\bigl(f_{T}(D)-f_{T}(\overline{D})\bigr) \displaystyle=\sum_{\pi\in S_{n}}\left(\prod_{ij\in E(D)}\bigl(1+x_{\pi(i)\pi(j)}y_{ij}(-1)^{(ij)_{\pi}}\bigr)-\prod_{ij\in E(D)}\bigl(1-x_{\pi(i)\pi(j)}y_{ij}(-1)^{(ij)_{\pi}}\bigr)\right). Thus D is not converse invariant if and only if P_{D}