The dimension of the negative cycle vectors of signed graphs

A signed graph is a graph Γ with edges labeled "+" and "-". The sign of a cycle is the product of its edge signs. Let SpecC(Γ) denote the list of lengths of cycles in Γ. We equip each signed graph with a vector whose entries are the numbers of negative k-cycles for k ∈ SpecC(Γ). These vectors generate a subspace of ℝ|^SpecC(Γ)|. 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 R|^SpecC(Γ)|.