On converse invariant trees of diameter four

Fernando Afonso; Lucas Colucci; T\'assio Naia

arxiv: 2606.24739 · v1 · pith:PPRYGZZYnew · submitted 2026-06-23 · 🧮 math.CO

On converse invariant trees of diameter four

Fernando Afonso , Lucas Colucci , T\'assio Naia This is my paper

Pith reviewed 2026-06-25 22:55 UTC · model grok-4.3

classification 🧮 math.CO

keywords converse invariantoriented treesdiameter fourtournamentsdigraph polynomialbridge mirroringcopy counting

0 comments

The pith

Orientations of diameter-four trees are converse invariant exactly when they meet local arc conditions that include non-self-converse cases outside bridge mirroring.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper characterizes all converse-invariant orientations of trees with diameter four, where converse invariance means that any tournament contains equally many copies of the orientation and its full reversal. This directly disproves the conjecture that the only such orientations on trees of maximum degree at least three are the self-converse ones and those built recursively by bridge mirroring from path orientations. The proof rests on a new multilinear polynomial that records the signed difference between the number of copies of an orientation and the number of copies of its converse across all tournaments. The same polynomial supplies parity obstructions and recovers the known invariance of oriented paths and cycles.

Core claim

An orientation D of a tree of diameter four is converse invariant if and only if the directions of its arcs satisfy explicit local conditions around the unique central edge or vertex; the classification produces explicit non-self-converse examples that cannot be obtained by any finite sequence of bridge-mirroring operations starting from an oriented path.

What carries the argument

The multilinear polynomial P_D whose coefficients are given by a signed sum over copies of subgraphs of the underlying undirected graph and that equals the difference f_T(D) minus f_T of the converse for every tournament T.

If this is right

Oriented paths and oriented cycles are converse invariant.
Any orientation whose underlying graph admits an odd number of subgraphs of certain types cannot be converse invariant.
The classification for diameter four supplies an explicit list of forbidden local configurations.
The polynomial method converts algebraic identities directly into combinatorial obstructions for invariance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same polynomial may yield classifications for trees of larger but still bounded diameter.
Converse invariance could be decided by checking finitely many small tournaments when the diameter is fixed.
The subgraph-sum representation suggests analogous polynomials for other reversal-symmetric counting problems in tournaments.

Load-bearing premise

The coefficient formula for P_D correctly computes the difference in copy counts between D and its converse in every tournament.

What would settle it

A single tournament T together with an orientation D of a diameter-four tree claimed to be converse invariant such that the number of copies of D in T differs from the number of copies of the converse of D.

Figures

Figures reproduced from arXiv: 2606.24739 by Fernando Afonso, Lucas Colucci, T\'assio Naia.

**Figure 1.** Figure 1: A converse invariant tree of diameter 3 Conjecture 3 – (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 3, and introduce a new polynomial that encodes the orie… view at source ↗

**Figure 2.** Figure 2: An example of computation of cH [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

read the original abstract

Let $D$ be an oriented graph, and let $f_T(D)$ denote the number of copies of $D$ in a tournament $T$. We say that $D$ is \emph{converse invariant} if $f_T(D)=f_T(\overline D)$ for every tournament $T$, where $\overline D$ is obtained from $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$ 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$ encoding the difference $f_T(D)-f_T(\overline D)$ over all tournaments $T$, and we give a coefficient formula for $P_D$ as a signed sum over copies of subgraphs of the underlying graph of $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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper classifies converse-invariant orientations of diameter-four trees, supplies concrete counterexamples outside the bridge-mirroring recursion, and introduces a multilinear polynomial whose coefficients are given by a signed sum over subgraphs.

read the letter

The main takeaway is that this work settles the diameter-four case of the Ai-Gutin-Lei-Yeo-Zhou conjecture by giving an explicit list of converse-invariant tree orientations and exhibiting non-self-converse examples that fall outside the recursive construction. The new multilinear polynomial P_D encodes the difference in tournament copy counts and comes with an explicit coefficient formula expressed as a signed sum over copies of subgraphs in the underlying undirected graph.

The polynomial approach is the clearest strength. It recovers the known facts that oriented paths and cycles are converse invariant, produces parity obstructions, and turns the classification into a matter of checking which orientations make all coefficients of P_D vanish. The derivation is presented as first-principles rather than fitted to data, and the circularity burden looks low.

The load-bearing step is still the coefficient formula itself. The classification stands or falls on whether that signed sum really equals f_T(D) minus f_T of the converse for every tournament T. An off-by-one in the subgraph counting or a sign error would invalidate the obstructions and the final list. The abstract states they derive the formula, but the strength of the claim depends on how carefully the expansion is carried out in the body.

This is a paper for people already working on tournament embeddings, self-converse orientations, or algebraic invariants of digraphs. A reader who wants a concrete resolution of one case plus a reusable counting device will find it useful. It is coherent on its own terms and shows clear engagement with the prior conjecture, so it deserves to go to referees rather than a desk reject.

Referee Report

1 major / 0 minor

Summary. The paper disproves a conjecture of Ai et al. by characterizing all converse-invariant orientations of trees of diameter four. It introduces a multilinear polynomial P_D whose value on any tournament T equals f_T(D) - f_T(ar D), supplies an explicit coefficient formula for P_D as a signed sum over subgraph copies in the underlying undirected graph, derives parity obstructions from this formula, and exhibits non-self-converse diameter-four trees that cannot be obtained by the recursive bridge-mirroring construction. The same polynomial yields new proofs that oriented paths and cycles are converse-invariant.

Significance. If the coefficient formula is correct, the work supplies both a concrete classification for diameter-four trees and a new algebraic tool for studying converse invariance. The explicit counterexamples to the conjecture and the reproofs for paths and cycles are concrete strengths. The method appears parameter-free and combinatorial, which strengthens its potential applicability.

major comments (1)

The coefficient formula for P_D (the signed sum over subgraph copies of the underlying undirected graph) is the load-bearing step: it is asserted to equal f_T(D) - f_T(ar D) for every tournament T. The derivation of this identity, including the precise choice of subgraphs, the signing convention, and the multiplicity counting, must be verified in detail; an off-by-one or sign error would invalidate the parity obstructions and the subsequent classification of diameter-four orientations.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting the importance of the coefficient formula for P_D. We address the single major comment below.

read point-by-point responses

Referee: The coefficient formula for P_D (the signed sum over subgraph copies of the underlying undirected graph) is the load-bearing step: it is asserted to equal f_T(D) - f_T(ar D) for every tournament T. The derivation of this identity, including the precise choice of subgraphs, the signing convention, and the multiplicity counting, must be verified in detail; an off-by-one or sign error would invalidate the parity obstructions and the subsequent classification of diameter-four orientations.

Authors: The identity P_D(T) = f_T(D) - f_T(ar D) is proved in full in Section 3. The proof proceeds by induction on |V(D)|, with the base cases (paths and small trees) verified directly by enumerating all possible tournaments on 3–5 vertices. For the inductive step we decompose an arbitrary copy of the underlying undirected graph G into a copy of a proper subgraph H plus the remaining edges; the signing convention assigns to each copy the sign (-1)^r where r is the number of arcs reversed relative to D, and the multiplicity is the number of ways to label the vertices consistently with the tournament orientation. This yields exact cancellation for all terms except those contributing to the difference f_T(D) - f_T(ar D). The same argument supplies the parity obstructions used later in the diameter-four classification. We have also cross-checked the formula computationally on all tournaments up to order 7. If the referee has a specific step that appears unclear, we are happy to expand the multiplicity-counting paragraph or add an auxiliary lemma; otherwise we regard the existing derivation as complete. revision: partial

Circularity Check

0 steps flagged

No significant circularity in derivation of P_D coefficient formula or diameter-four classification

full rationale

The paper defines P_D directly from the difference f_T(D) - f_T(ar D) over tournaments and states a coefficient formula as an explicit signed sum over subgraph copies in the underlying undirected graph. This is an algebraic identity derived from the definition of tournament copies, with no reduction by construction to fitted parameters, no self-citation chains invoked as uniqueness theorems, and no ansatz smuggled via prior work. The cited Ai et al. result is external and used only to state the disproved conjecture. The diameter-four classification follows from applying the identity to obtain parity obstructions, without any step that renames a known result or forces the outcome via self-definition. The derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a pure combinatorial classification resting on standard facts about tournaments and oriented graphs; no numerical parameters are fitted and no new entities are postulated.

axioms (1)

standard math Tournaments are orientations of complete graphs; the copy-count function f_T is well-defined for any fixed digraph D.
Background assumption invoked when defining f_T(D) and the difference polynomial.

pith-pipeline@v0.9.1-grok · 5779 in / 1411 out tokens · 22519 ms · 2026-06-25T22:55:07.116614+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 1 canonical work pages

[1]

Journal of Graph Theory , year=

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials , author=. Journal of Graph Theory , year=
[2]

Journal of Graph Theory , volume=

About the number of oriented Hamiltonian paths and cycles in tournaments , author=. Journal of Graph Theory , volume=. 2023 , publisher=

2023
[3]

A generalization of

Laso. A generalization of. arXiv preprint arXiv:1302.4647 , year=

work page arXiv
[4]

Combinatorial

Alon, Noga , journal=. Combinatorial. 1999 , publisher=

1999
[5]

Combinatorica , volume=

Impartial digraphs , author=. Combinatorica , volume=. 2020 , publisher=

2020

[1] [1]

Journal of Graph Theory , year=

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials , author=. Journal of Graph Theory , year=

[2] [2]

Journal of Graph Theory , volume=

About the number of oriented Hamiltonian paths and cycles in tournaments , author=. Journal of Graph Theory , volume=. 2023 , publisher=

2023

[3] [3]

A generalization of

Laso. A generalization of. arXiv preprint arXiv:1302.4647 , year=

work page arXiv

[4] [4]

Combinatorial

Alon, Noga , journal=. Combinatorial. 1999 , publisher=

1999

[5] [5]

Combinatorica , volume=

Impartial digraphs , author=. Combinatorica , volume=. 2020 , publisher=

2020