Refined non-Abelian dominance hypothesis for graph automorphism groups

The refined non-Abelian dominance hypothesis is false, including when both of its spectral conditions hold. We use the definitions in Thornton, Conjecture 33 (Conjecture 23 in the original version).

The unitary maximum

For a finite group $K$ of unitary matrices and a nonzero vector $x$, write

$$F_K(x)=\frac{1}{|K|}\sum_{Q\in K}Qxx^*Q^*,$$ $$\psi(K,x)=\frac{\lambda_{\max}(F_K(x))}{\operatorname{tr}F_K(x)}.$$

These are the source's group-averaged estimator and spectral concentration. Each summand is positive semidefinite and has trace $\|x\|^2$, so $0\leq\psi(K,x)\leq1$.

Let $\mathcal C_n$ be the group of cyclic coordinate shifts, and put $\mathcal C_U=U^*\mathcal C_nU$. Every element of $\mathcal C_n$ fixes the unit vector $e=(1,\ldots,1)^{\mathsf T}/\sqrt n$. Choose a unitary $U$ satisfying $Ux=\|x\|e$. Such a unitary exists by extending the two unit vectors to orthonormal bases. Every element of $\mathcal C_U$ then fixes $x$. Consequently $F_{\mathcal C_U}(x)=xx^*$ and $\psi(\mathcal C_U,x)=1$. Thus, for every nonzero $x$,

$$\max_{U\in\mathrm U(n)}\psi(\mathcal C_U,x)=1. \tag{1}$$

The source explicitly takes this unrestricted maximum inside the expectation. In particular, the optimizing unitary in (1) is allowed to depend on $x$.

A graph satisfying both spectral conditions

Take the complete graph on vertices $0,1,2,3$, and attach the path $0,4,5$, adding the edges $04$ and $45$. This is a connected simple graph on six vertices. Its degrees, in this order, are $4,3,3,3,2,1$. Every automorphism fixes $0,4,5$, while all permutations of $1,2,3$ are automorphisms. Hence

$$G=\operatorname{Aut}(\mathcal G)\cong S_3, \qquad |G|=6.$$

Let $A$ be its adjacency matrix and choose the polynomial graph filter

$$h(t)=1+\frac{t}{5},\qquad H=h(A),\qquad R=H^2.$$

Take independent $w,\eta\sim\mathcal{CN}(0,I_6)$ and set $x=Hw+\eta$. This has exactly the source's adjacency-polynomial signal form, with independent white noise. The signal covariance is $R$, and the observation covariance is $R+I_6$.

Let $W$ be the two-dimensional subspace of vectors vanishing at $0,4,5$ whose coordinates at $1,2,3$ sum to zero. We claim

$$\ker(A+I_6)=W. \tag{2}$$

Indeed, if $(A+I_6)y=0$, the rows at $1,2,3$ give $y_0+y_1+y_2+y_3=0$. The row at $0$ then gives $y_4=0$, the row at $5$ gives $y_5=0$, and the row at $4$ gives $y_0=0$. Conversely, every vector in $W$ satisfies the equations.

The action of $G$ on $W$ is irreducible over $\mathbb C$. To see this directly, take any nonzero vector in a nonzero invariant subspace of $W$. Two of its coordinates among $1,2,3$ differ. Subtracting its image under the transposition of these coordinates gives a nonzero multiple of a coordinate difference. Permuting the coordinates then gives all coordinate differences, which span $W$.

All eigenvalues of $A$ lie in $[-4,4]$, since the maximum degree is four. Therefore $H$ is positive definite, and the function $\lambda\mapsto(1+\lambda/5)^2$ is strictly increasing on the adjacency spectrum. By (2), the eigenspace of $R$ at $16/25$ is exactly $W$. This proves condition (i): it is a two-dimensional eigenspace carrying a two-dimensional irreducible representation of $G$.

The Perron--Frobenius theorem applies because $A$ is nonnegative and the graph is connected, so its largest eigenvalue is simple. Strict monotonicity of the same function shows that the largest eigenvalue of $R$ is simple as well. This proves condition (ii). Adding the white-noise covariance $I_6$ only shifts eigenvalues, so both conditions also hold for $R+I_6$.

The comparison is reversed

The observation is a nondegenerate complex Gaussian. Thus $x_0\neq0$ and $x_1\neq x_2$ with probability one. For such an $x$, the vectors $x$ and $(1\,2)x$ are linearly independent: proportionality would have scalar one by their common nonzero coordinate at $0$, contradicting $x_1\neq x_2$.

Both corresponding rank-one matrices occur with positive coefficient in $F_G(x)$. Hence $F_G(x)$ has rank at least two almost surely, and therefore $\psi(G,x)<1$ almost surely. Together with (1), this gives

$$\mathbb E[\psi(G,x)]<1,$$ $$\mathbb E\!\left[\max_{U\in\mathrm U(6)} \psi(\mathcal C_U,x)\right]=1.$$

Both spectral hypotheses are satisfied, but the conjectured strict dominance fails.