ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 625-639 https://doi.org/10.26493/1855-3974.1605.43f (Also available at http://amc-journal.eu) The dimension of the negative cycle vectors of signed graphs Alex Schaefer *, Thomas Zaslavsky Binghamton University (SUNY), Department of Mathematical Sciences, Binghamton, NY 13902-6000, U.S.A. Received 16 February 2018, accepted 7 March 2019, published online 6 June 2019 A signed graph is a graph r with edges labeled "+" and "—". The sign of a cycle is the product of its edge signs. Let SpecC(T) denote the list of lengths of cycles in r. We equip each signed graph with a vector whose entries are the numbers of negative k-cycles for k € SpecC(r). These vectors generate a subspace of R1 SPecG(r)1. 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 R1 SpecG(r)|. Keywords: Signed graph, negative cycle vector, permutable matching. Math. Subj. Class.: 05C22, 05C38 1 Introduction A signed graph E is a graph r whose edges have sign labels, either "+" or "-". The sign of a cycle in the graph is the product of the signs of its edges. Write c-(E) for the number of negative cycles of length l in E and collect these numbers in the negative cycle vector c-(E) = (c-, c-,..., c€ Rn-2, where n is the order of E. We are interested in the structure of the collection NCV(r) of all negative cycle vectors of signings of a fixed underlying simple graph r. The negative cycle numbers are of interest for several reasons. Ours is that, while the structure of a signed graph is more complex than that of an unsigned graph, much of that complexity is traceable to the distribution of negative cycles. We think negative cycle vectors are a step towards better understanding of those cycles. Beyond this, negative cycle numbers have been an object of interest since the first days of signed graph theory. When * Present address: University of Kansas, Department of Mathematics, Lawrence, KS 66045-7594, U.S.A. E-mail addresses: alex.scha4@ku.edu (Alex Schaefer), zaslav@math.binghamton.edu (Thomas Zaslavsky) Abstract ©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/ 625 Ars Math. Contemp. 16 (2019) 445-463 signed graphs were introduced by Harary [2] to be applied to a problem in social psychology by Cartwright and Harary [1], one of their concerns was to measure how unbalanced a signed graph is. One measure they proposed was the proportion of negative cycles, i.e., [ J2i cr (£)] / [J21 ci (T)], where c; denotes the total number of l-cycles in the graph. This proportion is hard to calculate even for signed complete graphs, since the number of cycles can be exponential in the order n and the negative cycle numbers are also complicated. There are at least three natural questions raised by the existence of the collections NCV(r). Most simply, since any set of points in M"r2 lies in a smallest subspace, what subspace do they span? That is the question we address here. The cycle spectrum SpecC(r) is the list of lengths of cycles in r. The finite set NCV(r) generates a subspace of M"r2 that is contained in the subspace RNCv(T) consisting of all vectors that are 0 in the coordinates that correspond to cycle lengths not in the cycle spectrum of r. We develop a general approach to the dimension question in terms of "permutable matchings" (see Section 2.3) that allows us to prove that, for r = Kn, Km,n, and the Petersen graph, NCV(r) spans RSpecC(n; it also gives us a lower bound on dimension for the Heawood graph and one other graph family. We also solve a few examples with an ad hoc method. Knowing the span of the negative cycle vectors, what is their convex hull? In [5] and [8] Popescu and Tomescu gave inequalities bounding the numbers of negative cycles in a signed complete graph, which may be a step towards the answer for Kn (see Section 5). A related question: Do the facets of the convex cone generated by NCV(r) have combinatorial meaning? The ultimate question: Which vectors in the convex hull are actually the vectors of signed graphs? Kittipassorn and Meszaros [3], inspired by the theory of two-graphs from finite group theory and geometry (see [7]) gave strong restrictions on the number of negative triangles in a signed Kn. This is a step towards the answer for Kn. We discuss these questions further in Section 5. Our work was originally focused on complete graphs and complete bipartite graphs. Those cases and others led the first author to the following conjecture, to which we do not know any counterexample. Conjecture 1.1 (Schaefer, 2015). For any graph r, dimNCV(T) = | SpecC(T)|, the number of different lengths of cycles in r. 2 Background 2.1 Graphs A graph is a pair r = ( V, E), where V = [v\,... ,vn} is a finite set of vertices and E is a finite set of unordered pairs of vertices, called edges. Our graphs are all unlabeled, simple, and undirected. Thus, all cycle lengths are between 3 and n. The cycle spectrum SpecC(r) is the set of cycle lengths that appear in r. The number of cycles of length l in r is c; = c; (r). The cycle vector of r is c(r) = (c3, c4,..., cn); sometimes we omit the components that correspond to lengths l not in the cycle spectrum. The number of cycle lengths in r, | SpecC(r)|, is clearly fundamental since dimNCV(r) < | SpecC(r)|. A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 627 2.2 Signed graphs A signed graph is a triple E = (V, E, a) where r = (V, E) is a graph, called the underlying graph of E, and a: E ^ {+, -} is the sign function. Two signed graphs are isomorphic if there is an isomorphism of underlying graphs that preserves edge signs. The sign of a cycle is the product of the signs of its edges; a signed graph in which every cycle is positive is called balanced. The negative edge set E- is the set of negative edges of E and the negative subgraph is E- = (V, E-), the spanning subgraph of negative edges. We sometimes write rN for r signed so that N is its set of negative edges. Switching E means choosing a vertex subset X C V and negating all the edges between X and its complement. Switching yields an equivalence relation on the set of all signings of a fixed underlying graph. If E2 is isomorphic to a switching of Ei, we say that Ei and E2 are switching isomorphic. This relation is an equivalence relation on signed graphs; we denote the equivalence class of E by [E]. A signed graph is balanced if and only if it is switching isomorphic to the all-positive graph. Signed graphs that are switching isomorphic, like those in Figure 1, have the same negative cycle vector. The negative cycle vector of E is c-(E) = (c-(E), c-(E),..., c-(E)), where c- = c- (E) is the number of negative cycles of length l. As with c(r), we may omit the components of c- (E) that correspond to lengths l not in the cycle spectrum. Also, we may write either c- (E) or c- (a), the latter when only the signature a is varying. Figure 1: Two switching equivalent signings of K6, with the same negative cycle vector (10,18, 36, 36). Solid lines are positive, dashed lines are negative. The negation of E is —E = (V, E, —a), in which the sign of every edge is negated. Sometimes E and — E are switching isomorphic, e.g., when E is bipartite or when it is a signed complete graph whose negative subgraph is self-complementary. 2.3 Permutable matchings A matching in r is a set M of pairwise nonadjacent edges; it is perfect if V(M) = V. A matching M—or any other edge set—is permutable if some subgroup of the automorphism group of r acts on the edges of M as the symmetric group S|M |. We base our results largely on permutable matchings, having noticed their utility for complete and complete bipartite graphs. The advantage of permutability is that, in counting negative cycles using a permutable matching, any two equicardinal subsets belong to the same number of negative cycles of each length. That makes it feasible to calculate the numbers in the vectors we use to estimate the dimension of NCV(r). Our introduction of permutable matchings led to the question: Which graphs have per- 628 Ars Math. Contemp. 16(2019)609-623 mutable matchings? That has been investigated by Schaefer and Swartz in [6]; they find large families of examples. On the other hand, there are only a few kinds of graph with permutable perfect matchings; Schaefer and Swartz determine them all. 3 Rank and dimension The dimension of NCV(T) is the rank of the matrix whose rows are the negative cycle vectors of all signatures of r. The columns of this matrix that correspond to lengths k e {3,4,..., n} \ SpecC(r) are all zero; thus, we may ignore them. Since the rank cannot be greater than | SpecC(r)|, if we produce a submatrix of that rank we have proved that dimNCV(r) = | SpecC(r)|. That is what we now endeavor to do with the aid of a permutable matching. Even if permutable matchings fail to reach the spectral upper bound, they imply a lower bound. However, we are happy to say that in our three main examples, permutable matchings solve the dimension problem. The rank of a matrix A is written rk(A). 3.1 Any negative edge set We begin with the most general calculation. Given a signed graph rN with an arbitrary negative edge set N C E, how many negative cycles are there of each length? For X C N let fi(X) = the number of l-cycles that intersect N precisely in X. We get a formula for f by Mobius inversion from gl (X) = the number of l-cycles that contain X, since gi(X )= £ fi(Y), xcy c N which implies that fl(X )= £ (-1)|YHX|g(Y). X cY cN The number of negative l-cycles is the number of l-cycles that intersect N in an odd number of edges; therefore, c-(rN )= £ fi(X )= ££ (-i)|Y|-|X|gi(Y) XcN, |X | odd XcY cN, |X| odd = £ gi(Y) £ (-i)|Y|-|X| YcN XcY, |X| odd = £ (—2)|y |-1gi(Y). (3.1) 0=Y cN This applies to every underlying graph r. 3.2 A matrix calculation Now assume we have a graph r of order n together with m unbalanced sign functions a1,..., am in addition to the all-positive function a0 = +. To avoid redundancy we want the associated signed graphs to be switching nonisomorphic. For instance, choosing more than half the edges at a vertex to be negative is switching equivalent to choosing fewer than A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 629 half, so we would not want the negative edge set to contain more than 1 deg(v) of the edges incident with any vertex v. We construct the matrix of the negative cycle vectors of all signings as and their negatives, with columns segregated by parity. The rows are one for +r (i.e., a0 = +), then m rows for the unbalanced signatures s ) C5 (am) C5 C3 — c-(ai) C5 — c—(ai) c5 (am) c3 \ c3 — c- (am) c5 — c- (am) if l is even. 00 c55 (ai) c5(ai) c5 (am) c5 (am) 0 0 c- (ai) c- (ai) (am) c- (am) (3.2) / The last column in the left half is that of n — 1 or n depending on whether n is even or odd; in the right half it is that of n or n — 1, respectively. Row operations reduce this matrix to 0 c3 (ai) 0 c55 (ai) c5 (am) c5 (am) c3 c5 00 \ 0 0 c- (ai) c- (ai) (am) c- (am) \ (3.3) Ignoring the first row of zeros, this is a block matrix A U O codd(r) o O R) The middle row codd(r), consisting of the odd-cycle numbers of r, corresponds to —r. The upper left block U is the matrix of negative odd-cycle vectors of the unbalanced signatures as, and the lower right block R is the matrix of negative even-cycle vectors of the same signatures. We infer the fundamental fact that: Lemma 3.1. The rank of the negative cycle matrix (3.2) equals the sum of the ranks of U and R. O and codd = 0, so only R needs to be considered. codd (r), For a bipartite graph U c c 0 630 Ars Math. Contemp. 16(2019)609-623 3.3 Permutable negative matchings Henceforth we assume we have chosen a fixed permutable matching Mm of m edges in r. For each s = 1,2,..., m we choose a submatching Ms C Mm of s edges and we define the signature as as that of the signed graph rMs. (It does not matter which Ms we use, because Mm is permutable.) This generates a matrix of negative cycle vectors as in (3.2). Permutability implies that gl (Y) depends only on |Y| so we may define Gl (k) = gl (Y) for any one k-edge subset Y C Mm. Then (3.1) becomes -(Fm, ) = ¿ (-2)k-1 (¡W) = ¿ (—2)k-1 Gkk)(s)fc, (3.4) kk! where (x)k denotes the falling factorial, (x)k = x(x -1) • • • (x - [k -1]). We may let k run up to n in the second summation because if k > s, the falling factorial equals 0. Formula (3.4) gives c-(rMs) as a polynomial function p;(s) without constant term, of degree d; where d; is the largest integer k for which G;(k) > 0; that is, d; is the largest size of a submatching of Mm that is contained in some cycle of length l. We leave d; undefined if no l-cycle intersects Mm. Clearly, d; < m. (This method works equally well for subsets of any permutable edge set N in any graph. It is easy to see that there are only three possible kinds of permutable set: a matching, a subset of the edges incident to a vertex, and the three edges of a triangle. In Kn a permutable set of edges at a vertex is useless since then the entire matrix (3.2) has rank 1. We have not seen a graph where a triangle's edges might help find the dimension.) A column of U or R is not all zero if and only if it corresponds to a cycle length l for which there exists an l-cycle in r that intersects Mm. Such a column contains m values of the polynomial p; (s). Since p; has degree at most m and no constant term, these values determine p; completely. Now a nonzero column in U or R for cycle length l looks like this: /pi(1)\ Pi(2) Wm)Z f a¡1dl + ai2dl + • • • \aimdl + —J (3.5) since pi is a polynomial of degree d;; here = (-2)dl 1G;(d;)/d;!. Moreover, d; = ^(l) > 0 for a nonzero column, where we define ^(l) = max |C; n Mm|, (3.6) Ci maximized over all l-cycles Cl. Define ¿odd to be the number of distinct degrees d; for odd lengths l whose column in U is not zero, and let 4ven be the number of distinct degrees d; for even lengths whose column in R is not zero. If some values of d; for, e.g., odd lengths l happen to be equal, they are counted only once. Thus, ¿odd may be less than the number of nonzero columns. The number of distinct polynomial degrees represented in the columns of U is ¿odd, and similarly for R the number is ¿even. Let Aodd be the set of distinct degrees d; counted by ¿odd, and similarly for Aeven. c A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 631 Lemma 3.2. The rank of U is at least ¿odd and that of R is at least 4ven. The rank of ( U ) is rk(U) + 1 if there is an odd length l such that an l-cycle exists \Codd J in r but no l-cycle intersects Mm. Proof. In U choose one column of each different degree dl. Divide by the leading coefficient ai, which is necessarily nonzero; this does not affect the rank. Now add columns of the form (s^)^ for every d = 1,2,..., m that is not in Aodd. Column operations allow us to eliminate the lower-degree terms of the column (3.5), leaving a Vandermonde matrix with 1d in the top row and md in the bottom row of column d for each d = 1,2,..., m, the rank of which is m. Now reverse the column operations; the rank remains the same, so the columns of U must have full column rank. The same reasoning applies to R. The extra 1 in the rank of | U | arises from the fact that, under the assumption, it has \Codd J a column that is zero in U but is nonzero in codd. □ 3.4 Theorems Lemma 3.2 yields our principal general theorem. Given a matching Mm and a cycle length l € SpecC(r), define ^(l) by Equation (3.6). Theorem 3.3. Let Mm be a permutable m-matching in r. Then |{m(1) : odd l € SpecC(r)}| + |{^(l) > 0 : even l € SpecC(r)}| < dim NCV(r) < | SpecC(r) |. ^ Suppose that all values ^(l) for even lengths l € SpecC(r) are distinct and positive, and all values ^(l) for odd lengths l € SpecC(r) are distinct. Then NCV(r) spans RSpecC(r). Proof. The first part follows directly from Lemma 3.2 since dim NCV(r) > rk(A) = rk ( U\ + rk(R) > ¿odd + ¿even. Vcodd ) Moreover, if there is an odd length l such that ^(l) = 0, then rk ( U ) = rk(U) + 1 > \Codd ) ¿even + 1; that explains why we do not exclude ^(l) = 0 from being counted in the odd-length part of (3.7). In the second part, ¿even = the number of even cycle lengths in r and ¿odd or (if some odd l € SpecC(r) has ^(l) = 0) ¿odd + 1 = the number of odd cycle lengths in r. Then the left-hand side of Formula (3.7) equals | SpecC(r) |. □ There is a simpler statement that applies to graphs with a permutable matching that is sufficiently omnipresent, i.e., meeting the condition of Theorem 3.4. Given m, define Vodd(m) = the number of odd lengths l < 2m in SpecC(r), +1 if there is an odd cycle length l > 2m, and define veven(m) = the number of even lengths l < 2m in SpecC(r), +1 if there is an even cycle length l > 2m. 632 Ars Math. Contemp. 16(2019)609-623 Theorem 3.4. Suppose Mm is a permutable m-matching in r and for every length l G SpecC(r) there exists a cycle C; such that |C; n Mm| = min(m, |l/2j). Then dimNCV(r) > Vodd(m) + Veven(m). The hypothesis can be lessened since, if there is any cycle length l > 2m, it suffices to have one length l > 2m for which there is a C; with |C; n Mm | = m. Proof. The hypotheses imply that '|_l/2j if l < 2m, if l > 2m. We count the number of distinct values for odd and even cycle lengths. For odd l we get (l - 1)/2 if l G SpecC(r) and l < 2m, and we get m if and only if there exists a cycle length l > 2m. The total is vodd(m). The computation of veven(m) is similar. The values of ^(l) in Theorem 3.3 are the same as those of unless there is a cycle length for which no l-cycle intersects Mm; but that is ruled out by our hypotheses. Theorem 3.4 follows. □ A connected graph is bipancyclic if it is bipartite with vertex classes of size p and q and has a cycle of every even length from 4 to 2 min(p, q). (This extends the usual definition, which assumes p = q.) This is the bipartite analog of pancyclicity, in which the graph has a cycle of every length from 3 to n, the order of the graph. Corollary 3.5. Assume r is pancyclic and has a permutable m-matching Mm, and for every l with 3 < l < n there is an l-cycle C; with |C; n Mm| = min(m, |_l/2j). Then dim NCV(r) = n - 2 if 2m > n - 1, n - 2 > dim NCV(r) > 2m - 1 if 2m < n - 2. Assume r is bipancyclic and has vertex class sizes p, q with p < q, and it has a permutable m-matching Mm such that for every k with 2 < k < p there is a 2k-cycle C2k with |C2k n Mm| = min(m, k). Then dim NCV(r) = p - 1 if m = p, p - 1 > dimNCV(r) > m - 1 if m < p - 1. The hypotheses can be lessened in the same way as those of Theorem 3.4. Proof. If r is pancyclic, vodd counts all the numbers 3, 5,..., 2m - 1 plus 1 for 2m +1 if n > 2m, and veven counts the numbers 4, 6,..., 2m - 2 plus 1 for 2m since n > 2m. Thus {(m) + (m - 1) = 2m - 1 if n > 2m, (m - 1) + (m - 1) = 2m - 2 if n = 2m. The conclusion follows easily. If r is bipancyclic, then veven = m - 1 and the conclusion follows easily. □ A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 633 The two most complete graphs are easy consequences of any of the preceding results, but especially of Corollary 3.5. Corollary 3.6. For a complete graph Kn with n > 3, dimNCV(Kn) = n - 2. For a complete bipartite graph Kp,q with p, q > 2, dimNCV(Kp,q) = min(p,q) - 1. 4 Examples 4.1 The complete graph Our original example was Kn. The biggest permutable edge set is a perfect or near-perfect matching. This turns out to be "perfect" for our purposes. But first, let us see the negative cycle vectors of all signings of small complete graphs. The vectors for K3 are (0), (1) (from the balanced and unbalanced triangle). The vectors for K4 are (0,0), (2, 2), (4,0) (the all-positive graph, one negative edge, and two nonadjacent negative edges). Here are the vectors for K5: (0, 0, 0), (3, 6, 6), (4, 8, 8), (5,10, 6), (6, 8, 4), (7, 6, 6), (10, 0,12); and for K6: (0, 0, 0, 0), (10,18, 36, 36), (10, 26, 36, 28), (12, 20,40, 24), (4,12, 24, 24), (8, 24,40, 32), (8, 24,48, 32), (10, 30, 36, 20), (6,18, 36, 36), (10, 22, 36, 28), (14, 18, 36, 36), (16,12, 48, 24), (8, 20, 32, 24), (12, 24, 24, 32), (12, 24, 32, 32), (20,0, 72, 0). The number of switching isomorphism classes of complete graphs grows super-expo-nentially [4]. Since two signed graphs which yield different vectors must belong to different classes, one naturally wonders about the converse property, that the vector uniquely identifies a switching class. This is true up through K7 but false for K8: see Figure ?? below (found by Gary Greaves, whose assistance we greatly appreciate). Thus when n = 8 there are fewer vectors than classes; for n > 8 see Question 5.5. Now we compute the function Gi of Section 3.3. Consider the signed Kn's whose negative edges are s nonadjacent edges, for 0 < s < |_n/2j. It is straightforward to compute gi. For a fixed k > 1 and set Y with |Y| = k, we need to form an l-cycle using Y and l - k other edges. (Since Y is a matching, we know that l > 2k.) So we choose l - 2k of the remaining n - 2k vertices, and then create our cycle as follows: imagine contracting the edges in Y; the resultant vertices, together with the other l - 2k vertices, will form an l - k-cycle in the contracted graph (which will eventually give an l-cycle in Kn). Cyclically order these l - k "vertices"; this orders the vertices in our actual cycle while ensuring the 634 Ars Math. Contemp. 16(2019)609-623 Figure 2: Two switching inequivalent signings of K8 with the same negative cycle vector (28,108, 336, 848,1440,1248). edges from Y remain. There are (l k2 1)! ways to do this. Then, we expand the contracted edges to regain them; there are 2 ways to do this for each edge. So we have «!-2k-' whence G<(k>=(n:»)(' -k - i)!2k-1 By Equation (3.4), c- (s) is a polynomial in s of degree d = |_l/2j and the general formula is c W= ^ (0 (:4)k-^ n : ^ C : k : ^ For example, c-(s) = s(n — 2) and c-(s) = s(n2 + 5n + 8) — 2s2. This formula for c-(s) demonstrates that the degrees d of the odd polynomials are all distinct, and the same for the even polynomials; consequently our main Theorem 3.3 itself implies that the matrix of negative cycle vectors c- (s) has full rank n — 2. Alternatively, in Kn with a maximum matching, Aodd = {3, 5,...} (odd numbers up to n) and Aeven = {4,6,...} (even numbers up to n). So, by Lemma 3.2, for Kn the ranks of U and R are [n/2] — 1 and |_n/2j — 1, respectively, which sum to n — 2. 4.2 Complete bipartite graphs We now examine Kp,q, which always has p < q. We use a maximum matching Mp, i.e., we set m = p. To get c- (Kp,q) we compute g21, where the subscript is now 2l because all cycles have even length. Call the two independent vertex sets A = {a 1,..., ap} and B = {b1,..., bq}. For a fixed k-edge set Y = {a4l bj1,..., aikbjk} C Mp, where k < l, we need to form a 2l-cycle using Y and 2l — 2k other vertices. Fix one edge y1 G Y, say y1 = ail bj1. Choose l — k of the remaining p — k vertices from A, in order, in one of (p — k)_k ways; l — k of the remaining q — k vertices from B, also in order, in one of (q — k)_k ways; and shuffle the sequences together as (aifc+1, bjfc+1,..., ail, bjz). Insert Y into this 2(l — k)-sequence A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 635 by inserting yi before aifc+1, which we may do because each Y edge must be between an A vertex and a B vertex; treating the resulting sequence as cyclically ordered, which can be done in only one way since the A neighbor of yi appears after y1; then ordering Y \ jyi} in one of (k - 1)! ways as (y2,..., yk); and finally inserting y2,..., yk anywhere into the cycle in one of '[2(Z - k) + 1] + [k - 1] - - k - T [2(Z - k) + 1] - 1 ) \ k - 1 ways. Note that when those edges are inserted into the cycle, there is only one way to orient each edge. The net result is that /2Z — k — 1 Gi(k) = 921 (Y) = (p - k),_fc(q - k),_fc • (k - 1)! i jfc- -Then by Equation (3.4), for 2 < Z < p, c-(s) = m(s)k(—2k— (p-k)i-k(q-k)i-k(2Z-^. This explicit formula for the negative cycle vectors c-(s), with Theorem 3.3, implies that dim NCV(Kp,q) = p = min(p, q). 4.3 The Petersen graph Next we consider the Petersen graph P, which has four cycle lengths, 5, 6, 8, and 9, so dim NCV(P) < 4. It lacks a permutable 4-matching. In fact: Theorem 4.1. A 3-regular graph that is arc transitive cannot have a permutable 4-matching. Proof. By [6, Theorem 1.1] an arc-transitive graph with a permutable m-matching, where m > 4, must have degree at least m. □ The Petersen graph does have a permutable 3-matching, in fact, two kinds. The first kind consists of alternate edges of a C6. In the language of Theorem 3.3, we must compute ^(Z) = | maxjC; n M3}| for each cycle length. We find with little difficulty that ^(5) = 2, ^(6) = 3, ^(8) = 2, and ^(9) = 3. Therefore |Aodd| = 2 and |Aeven| = 2, whence, despite only having a 3-matching, we can deduce that dim NCV(P) = 4. We even know the negative cycle vectors corresponding to negative 0-, 1-, 2-, and 3-submatchings and the negated signatures; they are (in order of matching size) (0,0,0, 0), (4,4, 8,12), (6, 6, 8,10), (6,10,0,10) (12,0,0, 20), (8,4, 8, 8), (6, 8, 8,10), (6,10,0,10). The bottom vector in each column corresponds to the negated signing. The second kind of permutable 3-matching consists of three edges at distance 3. The first matching type also is three equally spaced edges in a C9, but not every such subset of a C9 is also a set of alternating edges of a C6; the other such subsets are 3-matchings of the second kind. This second kind generates negative cycle vectors from negated submatchings and the corresponding negated sign functions whose dimension is only 3, not 4, since with this matching the negated signatures are switching isomorphic to unnegated signatures. This shows that not all permutable m-matchings in a graph are equally useful. 636 Ars Math. Contemp. 16 (2019) 445-463 4.4 The Heawood graph The Heawood graph H is bipartite and has five cycle lengths, 6, 8, 10, 12, and 14, so dimNCV(H) < 5. It has a permutable 3-matching, indeed three different kinds, for instance alternate edges of a 6-cycle. Using that 3-matching we find that p(6) = 3, p(8) = 2, p(10) = 3, p(12) = 3, and p(14) = 3. These are two different values, thus dimNCV(H) > 2. The results for the other two kinds of permutable 3-matching are the same except that p(6) = 2. In every case p has two values. Our matching method, in principle, cannot prove more because H has no permutable 4-matching (see Theorem 4.1). Nonetheless we suspect the dimension equals | SpecC(H) |. 4.5 Other graphs with permutable perfect matchings, and the cube Schaefer and Swartz found all graphs that have a permutable perfect matching. Besides Kn and Kp,p they are the hexagon C6, the octahedron graph O3, and three general examples: the join Kp V Kp of a complete graph with its complement, the matching join Kp Y Kp obtained from two copies of Kp by inserting a perfect matching between the two copies, and the matching join Kp Y Kp, obtained by hanging a pendant edge from each vertex of Kp. Our treatment of them leads us to one other family, the cyclic prisms Cp □ K2. 4.5.1 The simple four Trivially, dimNCV(C6) = 1 = | SpecC(C6)|. It is easy to verify by hand that O3 satisfies the conditions of Corollary 3.5, so dimNCV(O3) = | SpecC(O3)| = 4. As for Kp Y Kp, since the pendant edges contribute nothing to cycles, SpecC(Kp Y Kp) = SpecC(Kp) and NCV(Kp Y Kp) = NCV(Kp); thence dimNCV(Kp Y Kp) = | SpecC(Kp Y Kp)| = p. It is also easy to show that Kp V Kp satisfies the conditions of Corollary 3.5. Thus, dimNCV(Kp V Kp) = | SpecC(Kp V )| = 2p. 4.5.2 The matching join of two complete graphs This graph, Y Kp, is pancyclic, but its permutable matchings are peculiar. One kind is any matching in a Kp. A maximum matching M^p/2j in has p(l) = min(p, |_l/2_|), hence dimNCV(Kp Y Kp) > p by reasoning similar to that for Kp. The matching Mp that joins the copies of prevents a permutable matching from having edges in both copies. The only other permutable matchings are subsets of Mp . This matching only generates |_p/2j switching nonisomorphic signatures since negating a subset of M^ switches to negating the complementary subset. By itself, therefore, choosing our grand matching Mm to be M^ does not give a better lower bound than p. Nonetheless we feel the dimension is likely to be n — 2 = 2p — 2. A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 637 The smallest case, K3 Y K3, is the triangular prism. There are four cycle lengths; the cycle count vector is (c3, c4, c5, c6) = (2,3,6,3). The required dimension can be found directly. There are four unbalanced signatures; see Figure 3. The negative cycle vectors are linearly independent so dim NCV(K3 Y K3) = | SpecC(v) |, in agreement with Conjecture 1.1. (a) (0, 2,4, 2) (b) (1,1, 3, 2) (c) (2, 0, 6, 0) (d) (2, 2, 2, 2) Figure 3: The four unbalanced switching classes of the prism K3 Y K3 and their negative cycle vectors. As for permutable matchings in the triangular prism, gives ^(3) = 0, ^(4) = ^(5) = ^(6) = 2, thus dim NCV(K3 Y K3) > 3, less than the true value. A strange permutable matching gives the right dimension. Choose M2 to consist of one edge from each triangle, not both in a C4. Then ^(3) = ^(4) = 1 and ^(5) = ^(6) = 2, so by Theorem 3.3, dimNCV(K3 Y K3) = 4, the exact value. This example and the Petersen graph demonstrate that useful permutable matchings need not be perfect matchings. 4.5.3 Prisms, with cube The triangular prism lends support to our belief that dimNCV(Kp Y Kp) = 2p - 2. However, it is atypical since it is also a prism, the Cartesian product Cp □ K2 with p = 3. Prisms with p > 3 do not have permutable perfect matchings but they make good examples, especially the next case, the cube Q3 = C4 □ K2. It is bipartite and has only three cycle lengths: 4, 6, and 8. Three unbalanced signatures whose negative cycle vectors are linearly independent are a1, with one negative edge, e. It has c- (a1) = (2,8,4); o2, with a second negative edge, parallel to e and sharing a quadrilateral with it. It has c-fo) = (2,12,4); 8 there are pairs of switching nonisomorphic signed Kn 's that have the same negative cycle vector. In a related question, we ask whether the number In of switching isomorphism types of signed complete graphs [4] is asymptotic to the number | NCV (Kn)| of negative cycle vectors of those graphs; that is, whether |NCV (Kn)|/In ^ 1. If not, does it approach 0? 5.6 Conclusion Evidently, there is much to discover before we can say the negative cycles in signed graphs are well understood. A. Schaefer and T. Zaslavsky: The dimension of the negative cycle vectors of signed graphs 639 References [1] D. Cartwright and F. Harary, Structural balance: a generalization of Heider's theory, Psychol. Rev. 63 (1956), 277-293, doi:10.1037/h0046049. [2] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953-54), 143-146, doi:10.1307/mmj/1028989917. [3] T. Kittipassorn and G. Meszaros, Frustrated triangles, Discrete Math. 338 (2015), 2363-2373, doi:10.1016/j.disc.2015.06.006. [4] C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math 28 (1975), 876-880, doi:10.1137/0128070. [5] D. R. Popescu and I. Tomescu, Negative cycles in complete signed graphs, Discrete Appl. Math. 68 (1996), 145-152, doi:10.1016/0166-218x(95)00010-o. [6] A. Schaefer and E. Swartz, Graphs that contain multiply transitive matchings, submitted, arXiv:1706.08964 [math.CO]. [7] J. J. Seidel, A survey of two-graphs, in: Colloquio Internazionale sulle Teorie Combinatorie, Tomo I, Accademia Nazionale dei Lincei, Rome, pp. 481-511, 1976, proceedings of the Con-vegni Lincei, No. 17, held in Rome, September 3 - 15, 1973. [8] I. Tomescu, Sur le nombre des cycles negatifs d'un graphe complet signe, Math. Sci. Humaines 53 (1976), 63-67, http://www.numdam.org/item/MSH_197 6_5 3_6 3_0.