Which exterior powers are balanced?

Devlin Mallory¹ ; Abigail Raz² ; Christino Tamon³ ; Thomas Zaslavsky⁴

¹University of California at Berkeley
²Wellesley College
³Clarkson University
⁴Binghamton University

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

A signed graph is a graph whose edges are given $\pm 1$ weights. In such a graph, the sign of a cycle is the product of the signs of its edges. A signed graph is called balanced if its adjacency matrix is similar to the adjacency matrix of an unsigned graph via conjugation by a diagonal $\pm 1$ matrix. For a signed graph $\Sigma$ on $n$ vertices, its exterior $k$th power, where $k=1,\ldots,n-1$, is a graph $\bigwedge^{k} \Sigma$ whose adjacency matrix is given by\[ A(\mbox{$\bigwedge^{k} \Sigma$}) = P_{\wedge}^{\dagger} A(\Sigma^{\Box k}) P_{\wedge}, \]where $P_{\wedge}$ is the projector onto the anti-symmetric subspace of the $k$-fold tensor product space $(\mathbb{C}^{n})^{\otimes k}$ and $\Sigma^{\Box k}$ is the $k$-fold Cartesian product of $\Sigma$ with itself. The exterior power creates a signed graph from any graph, even unsigned. We prove sufficient and necessary conditions so that $\bigwedge^{k} \Sigma$ is balanced. For $k=1,\ldots,n-2$, the condition is that either $\Sigma$ is a signed path or $\Sigma$ is a signed cycle that is balanced for odd $k$ or is unbalanced for even $k$; for $k=n-1$, the condition is that each even cycle in $\Sigma$ is positive and each odd cycle in $\Sigma$ is negative.

Détail

DOI : 10.37236/3033

Classification : 05C22, 05C50
Mots-clés : signed graph, exterior power, quotient graph