Classification of Label-Regular Directed Trees up to Almost Isomorphism

NEW

Problem: The source supports the following formal reconstruction. Let $G$ be the finite directed multigraph on vertices $\{x,y\}$ with adjacency matrix

where entries count directed edges, and let

be its commutative graph monoid. The paper’s explicit conjecture is:

If $A\ge D$, $A,B,C,D>0$, and $(A-C)(B-D)<0$, then

The surrounding paragraph, however, says the graph is being assumed non-redundant, i.e. $A+B\ne C+D$. The literal displayed conjecture omits this hypothesis.

Result: The literal conjecture is false. Take

Then $A\ge D$, all entries are positive, and

The monoid has relations

Now

while

Hence $x=y$, but $D=3\ne2$. Thus the literal statement fails.

The natural repair is to add the contextual non-redundancy hypothesis $A+B\ne C+D$. With that repair, the conjecture is true.

Proof of repaired statement. Assume $A+B\ne C+D$ and $x=y$ in $\mathcal M(G)$. Passing to the universal abelian group gives integers $m,n$ such that

so

The case $A<C,\ B>D$ is impossible by sign comparison in (1). Therefore $A>C,\ B<D$. In this case $m<0<n$ is also impossible, so $m=k>0$ and $n=-\ell<0$. Then

Let $a=A-C>0$, $d=D-B>0$, and $s=k-\ell$. These become

If $s=0$, then $a=d=2$, giving $A+B=C+D$, contradiction.
If $s>0$, (2) forces $s=C=1$ and $a=1$; then $A=2$, and $A\ge D>B$ forces $B=1,D=2$, contradicting the second equation of (2).
Hence $s<0$. Then the second equation of (2) forces

so $D=2$. The first equation gives

Let $N=A-C-1$. Then $N>0$, and

so $N\mid A$.

Conversely, suppose $B=1$, $D=2$, and $N=A-C-1\mid A$. Write $A=(k+1)N$, so $C=kN-1$. Starting from $x$, expand $x$ once and then expand $y$ $k+2$ times:

Starting from $y$, expand $y$ once and then expand $x$ $k+1$ times:

The $x$-coefficients agree because

Thus $x=y$ in $\mathcal M(G)$.

So the repaired non-redundant conjecture is proved exactly. The counterexample above is excluded precisely because $A+B=C+D$.

Citation: Conjecture source: Roman Gorazd, “Classification of Label-Regular Directed Trees up to Almost Isomorphism,” arXiv:2303.05673, §Example. The proof and counterexample above are not taken from a cited resolution.