- Series
- Graph Theory Seminar
- Time
- Thursday, November 8, 2012 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Hein van der Holst – Georgia State University
- Organizer
- Robin Thomas
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.