Georgia Institute of Technology College of Sciences

A signed graph is a pair $(G,\Sigma)$ where $G$ is an undirected graph (in which parallel edges are permitted, but loops are not) and $\Sigma \subseteq E(G)$. The edges in $\Sigma$ are called odd and the other edges are called even. A cycle of $G$ is called odd if it has an odd number of odd edges. If $U\subseteq V(G)$, then re-signing $(G,\Sigma)$ on $U$ gives the signed graph $(G,\Sigma\Delta \delta(U))$. A signed graph is a minor of $(G,\Sigma)$ if it comes from $(G,\Sigma)$ by a series of re-signing, deletions of edges and isolated vertices, and contractions of even edges. If $(G,\Sigma)$ is a signed graph with $n$ vertices, $S(G,\Sigma)$ is the set of all symmetric $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j} > 0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j} < 0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}\in \mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i$ and $j$ are not connected by any edges, and $a_{i,i} \in \mathbb{R}$ for all vertices $i$. The stable inertia set, $I_s(G,\Sigma)$, of a signed graph $(G,\Sigma)$ is the set of all pairs $(p,q)$ such that there exists a matrix $A\in S(G,\Sigma)$ that has the Strong Arnold Hypothesis, and $p$ positive and $q$ negative eigenvalues. The stable inertia set of a signed graph forms a generalization of $\mu(G)$, $\nu(G)$ (introduced by Colin de Verdi\`ere), and $\xi(G)$ (introduced by Barioli, Fallat, and Hogben). A specialization of $I_s(G,\Sigma)$ is $\nu(G,\Sigma)$, which is defined as the maximum of the nullities of positive definite matrices $A\in S(G,\Sigma)$ that have the Strong Arnold Hypothesis. This invariant is closed under taking minors, and characterizes signed graphs with no odd cycles as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 1$, and signed graphs with no odd-$K_4$- and no odd-$K^2_3$-minor as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 2$. In this talk we will discuss $I_s(G,\Sigma)$, $\nu(G,\Sigma)$ and these characterizations. Joint work with Marina Arav, Frank Hall, and Zhongshan Li.