The Dimension of the Negative Cycle Vectors of Signed Graphs

A “signed graph” is a graph $\mathrm{\Gamma }$ where the edges are assigned sign labels, either “$+$” or “$-$”. The sign of a cycle is the product of the signs of its edges. Let $\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{C}(\mathrm{\Gamma })$ denote the list of lengths of cycles in $\mathrm{\Gamma }$. We equip each signed graph with a vector whose entries are the numbers of negative $k$-cycles for $k\in \mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{C}(\mathrm{\Gamma })$. These vectors generate a subspace of ${\mathbb{R}}^{\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{C}(\mathrm{\Gamma })}$. Using matchings with a strong permutability property, we provide lower bounds on the dimension of this space; in particular, we show for complete graphs, complete bipartite graphs, and a few other graphs that this space is all of $\mathbb R^{$\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{C}$(\Gamma)}$.