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.
From: Lucas Colucci [view email]
[v1]
Tue, 23 Jun 2026 16:01:43 UTC (362 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。