Which Exterior Powers are Balanced? Devlin Mallory Abigail Raz Christino Tamon ∗ † ‡ Thomas Zaslavsky § 3 1 December 11, 2013 0 2 n a J Abstract 6 A signed graph is a graph whose edges are given 1 weights. In such a graph, ] ± O the sign of a cycle is the product of the signs of its edges. A signed graph is called C balanced if its adjacency matrix is similar to the adjacency matrix of an unsigned . graph via conjugation by a diagonal 1 matrix. For a signed graph Σ on n vertices, h t its exterior kth power, wherek = 1,..±.,n 1, is a graph kΣ whose adjacency matrix a − m is given by V A( kΣ) = P†A(Σ(cid:3)k)P , [ ∧ ∧ V 1 whereP istheprojectorontotheanti-symmetricsubspaceofthek-foldtensorproduct ∧ v space (Cn)⊗k and Σ(cid:3)k is the k-fold Cartesian product of Σ with itself. The exterior 3 7 power creates a signed graph from any graph, even unsigned. We prove sufficient and 9 necessary conditions so that kΣ is balanced. For k = 1,...,n 2, the condition is 0 − that either Σ is a signed pathVor Σ is a signed cycle that is balanced for odd k or is . 1 unbalanced for even k; for k = n 1, the condition is that each even cycle in Σ is 0 − positive and each odd cycle in Σ is negative. 3 1 : Keyword: signed graphs, exterior powers, quotient graphs. v i X 1 Introduction r a We are interested in graph operators which arise from taking the quotient of a Cartesian product of an underlying graph with itself. More specifically, such operators are defined on a graphG = (V,E) after applying thefollowing three steps. First, we take the k-foldCartesian product of G with itself, namely G(cid:3)k. Note that the vertex set of G(cid:3)k is the set of k-tuples Vk. For the second (possibly optional) step, we remove from Vk (via vertex deletions) the set consisting of all k-tuples of vertices which contain a repeated vertex. We denote the D ∗Department of Mathematics, University of California at Berkeley. †Department of Mathematics, Wellesley College. ‡Department of Computer Science, ClarksonUniversity. Contact author: [email protected] §Department of Mathematics, Binghamton University. 1 resulting graph as G(cid:3)k . Finally, we conjugate the adjacency matrix of G(cid:3)k with an \D \D invertible operator . If we call the resulting graph , then Q G A( ) = †A(G(cid:3)k ) . (1) G Q \D Q For cases of interest, will either be the symmetrizer P or the anti-symmetrizer P which ∨ ∧ Q are projection operators onto the symmetric and anti-symmetric subspaces of the k-fold tensor product space V⊗k (see Bhatia [3]). For example, Audenaert, Godsil, Royle and Rudolph [2] studied the symmetric powers G{k} of a graph G which is defined as A(G{k}) = P˜†A(G(cid:3)k )P˜, (2) \D where P˜ is a “hybrid” of P and P . These graphs were studied in the context of the ∨ ∧ graph isomorphism problem on strongly regular graphs. They are equivalent to the so-called k-tuple vertex graphs, introduced by Zhu, Liu, Dick and Alavi [10], which generalizes the well-known double vertex graphs (see Alavi, Behzad, Erd¨os, and Lick [1]). Subsequently, these k-tuple vertex graphs were studied by Osborne [8] in the framework of spin networks in quantum information. k The main focus of this work is on the exterior powers G of a graph G defined as V A( kG) = P†A(G(cid:3)k)P . (3) ∧ ∧ V k We will show that G is a signed graph whose edges have 1 weights. Moreover, this ± also holds if the undVerlying graph is a signed graph Σ = (G,σ) where σ is the 1-valued ± edge-signing function. Our main observation is the following characterization of balanced exterior powers. Theorem 1. Let Σ be a signed graph on n vertices. Then, kΣ is balanced if and only if: V for k = 2,...,n 2: • − Either (i) Σ is a signed path; or (ii) Σ is a signed cycle that is balanced when k is odd k and unbalanced when k is even. for k = n 1: • − Each even cycle in Σ is positive and each odd cycle is negative. Theproofofthefirstpartoftheabovetheoremisbasedonaforbiddensubgraphproperty. k Namely, if the exterior kth power Σ is balanced, then Σ may not contain the claw K as 1,3 a subgraph, for k = 1,...,n 2. IVn this case, Σ is either a signed path or it is a signed cycle − which is balanced for odd k and unbalanced for even k. The case when k = n 1 requires a − separate argument. As a corollary, we also obtain a characterization of unsigned graphs G whose exterior kth k power is balanced. For 2 k n 2, G is balanced if and only if G is a path or G is a cycle and k is odd. For th≤e bo≤unda−ry caVse of k = n 1, n−1G is balanced if and only if G − is bipartite. V We remark that both the symmetric and exterior powers are closely related to the study of many-particle quantum walk on graphs in quantum information (see [4]). 2 2 Preliminaries We state some notation which we use in the remainder of this paper. For a logical statement S, we let [[S]] be 1 if S is true, and 0 otherwise. Given a positive integer n, we use [n] to denote the set 1,2,...,n . For two sets A and B, we let A B denote the symmetric { } △ difference of A and B; that is, A B = (A B) (B A). △ \ ∪ \ The graphs G we study here are finite, mostly simple, undirected and connected. The vertex set of G will be denoted V(G) and its edge set E(G). The adjacency matrix A(G) of G is defined as A(G) = [[(u,v) E(G)]]. For two graphs G and H with adjacency u,v matrices A(G) and A(H), respectively∈, their Cartesian product G (cid:3) H is a graph defined on the vertex set V(G) V(H) where (g ,h ) is adjacent to (g ,h ) if either g = g and 1 1 2 2 1 2 × (h ,h ) E , or (g ,g ) E and h = h . The adjacency matrix of this Cartesian product 1 2 H 1 2 G 1 2 is given∈by A(G (cid:3) H) =∈A(G) I +I A(H). Here, A B denotes the tensor product of ⊗ ⊗ ⊗ matrices A and B. Standard graphs we consider include the complete graphs K , paths P , cycles C , bi- n n n partite graphs, and the hypercubes Q . n m Avertex partitionπ ofagraphG = (V,E)givenbyV = V isequitableifeachvertex j=1 j u in Vj is adjacent to dj,k vertices in Vk, where this constanUt is independent of the choice of vertex u (see Godsil [5]). Each component V is called a cell of the equitable partition π. j Here, π = m is the size of π – which is the number of cells in π. The (normalized) partition | | matrix Q of π is a V π matrix whose entries are Q[i,j] = [[i V ]]/ V . The quotient j j | |×| | ∈ | | graph G/π of G modulo the equitable partition π is an undirected wepighted graph whose vertices are the cells of π and whose edges (V ,V ) are given the weights d d . j k j,k k,j p Fact 2. (Godsil [5]) Let G = (V,E) be a graph and let π be an equitable partition with partition matrix Q. The following properties hold: 1. QTQ = I. 2. QQT commutes with A(G). 3. A(G/π) = QTA(G)Q. More background on algebraic graph theory may be found in Godsil and Royle [6]. 2.1 Signed graphs A signed graph Σ = (G,σ) is a pair consisting of a graph G = (V,E) and a signing map σ : E(G) 1,+1 over the edges of G. We call G the underlying (unsigned) graph of Σ; → {− } we also use Σ to denote this underlying graph. | | The sign of a cycle in a signed graph is the product of all the signs of its edges. A signed graph is called balanced if all of its cycles are positive. Similarly, it is called anti-balanced if all of its odd cycles are negative and all of its even cycles are positive. Fact 3. (Harary [7]) A signed graph is balanced if and only if there is a bipartition in which all crossing edges are negative and all non-crossing edges are positive. 3 Given a signed graph Σ, switching around a vertex u V(Σ) means flipping the signs of ∈ all edges adjacent to u. Similarly, switching around a subset U V(Σ) means flipping the ⊆ signs of all edges crossing the cut (U,Uc), that is, edges of the form (v,w), where v U and ∈ w Uc. ∈ Fact 4. A signed graph is balanced (respectively, anti-balanced) if and only if there is a subset U for which switching around U results in all edges being positive (respectively, negative). Switching has a nice algebraic description as conjugation by a diagonal matrix with 1 ± entries. Two signed graphs Σ and Σ are called switching equivalent, denoted Σ Σ , if 1 2 1 2 ∼ A(Σ ) = D−1A(Σ )D for some diagonal matrix D with 1 entries. Thus, a signed graph Σ 1 2 ± is balanced if Σ Σ and it is anti-balanced if Σ Σ (that is, Σ is balanced). ∼ | | − ∼ | | − More basic facts about signed graphs may be found in Zaslavsky [9]. 3 Exterior Powers k LetGbeagraphonnvertices. Wefirstdefinetheexteriorkthpower G, for1 k n 1, ≤ ≤ − in a combinatorial fashion. An equivalent algebraic formulation willVfollow thereafter. Our treatment follows closely the description given by Osborne [8] (see also [2]). We fix an arbitrary total ordering on the vertex set V of G. Consider a k-tuple u Vk, ≺ ∈ say u = (u ,...,u ), whose elements are distinct and are ordered with respect to , that is, 1 k ≺ u ... u . We adopt the somewhat standard “wedge” product notation to denote such 1 k ≺ ≺ an ordered k-tuple as u = u ... u . Let V denote the set of all such ordered k-tuples. 1∧ ∧ k k That is: (cid:0) (cid:1) V = u ... u : u ,...,u V,u ... u . (4) 1 k 1 k 1 k (cid:18)k(cid:19) { ∧ ∧ ∈ ≺ ≺ } Again, we stress that u u ... u is notation for the k-tuple (u ,...,u ) whose elements 1 2 k 1 k ∧ ∧ ∧ are distinct and are given in ascending order (with respect to ). The vertex set of kG is V and its edges are defined so≺two vertices u = k u and k j=1 j v = k v areadjaceVnt ifthe(cid:0)re(cid:1)isabijectionπ over [k] whereu = v forallj V 1,...,k j=1 j π(j) j ∈ { } excepVt at one index i where (u ,v ) E(G). Thus, for u,v V , we have π(i) i ∈ ∈ k (cid:0) (cid:1) k (u,v) E( G) iff ( i)[(u ,v ) E(G) and ( j = i)[u = v ]]. (5) π(i) i π(j) j ∈ ∃ ∈ ∀ 6 V k Here, we say that the permutation π connects the vertices u and v. We make G into a signed graph by assigning the value sgn(π) to the above edge (u,v). V Example: Consider a 4-cycle on V = a,b,c,d with edges E = (a,b),(b,c),(c,d),(a,d) . { } { } With the ordering a b c d, we have V = a b,a c,a d,b c,b d,c d . Then, ≺ ≺ ≺ 2 { ∧ ∧ ∧ ∧ ∧ ∧ } 2C isthesignedbipartitegraphK wit(cid:0)hp(cid:1)artition a d,b c and a b,a c,b d,c d . 4 2,4 { ∧ ∧ } { ∧ ∧ ∧ ∧ } AVll edges are positive except for the ones connecting b c with both a b and c d. See ∧ ∧ ∧ Figure 1. k Our further interest will be on the exterior power Σ of a signed graph Σ = (G,σ). This is a strict generalization of the case for unsigned gVraphs. In this general case, the sign 4 d b c ∧ − + + − b c a b a c b d c d ∧ ∧ ∧ ∧ + + + + a a d ∧ Figure 1: The 4-cycle and its exterior square 2C . 4 V k of the edge connecting u,v in Σ is the product of the sign of the permutation π that connects u and v, and the sign Vof the only adjacent pair (uπ(i),vi) in Σ, for i which satisfies k Equation (5); that is, the sign of the edge (u,v) in Σ is V σ′(u,v) = sgn(π) σ(u ,v ), (6) π(i) i × where (u ,v ) E(G) and u = v for all j = i. Here, we have used σ′ to denote the π(i) i π(j) j ∈ 6 k signing function for the exterior power Σ. V Remark: A gain graph Φ = (G,X,ϕ) is a triple consisting of a graph G = (V,E), a group X, and a gain function ϕ over the edges of G, that is, ϕ : E(G) X. In our case, we may k k → treat G as a gain graph Φ( G,S ,ϕ) over the symmetric group S , where ϕ assigns the k k permuVtation π that connects uVand v to the edge (u,v). Algebraic framework Next, we describe an algebraic framework for the exterior kth k power G. Much of the machinery below will be familiar from multilinear algebra (see BhatiaV[3]). LetG = (V,E)beagraphonnverticesandletk beapositiveintegerwhere1 k n 1. ≤ ≤ − We consider the vector space W = CV of dimension n where we use the vertex set V to index the n-dimensional space. For each vertex u V, we let e(u) represent the unit vector ∈ that is 1 at position u and 0 elsewhere. So, the vertex set of G gives us a basis for the vector space W via the set e(u) : u V . Next, we consider the k-fold tensor product space kW and index this n{k-dimensi∈onal}space using the k-tuples of Vk. To this end, for a k-tupNle u = (u1,...,uk) Vk, we define the unit vector e(u) (this time in kW) as ∈ N e(u) = e(u ) e(u ) ... e(u ). (7) 1 2 k ⊗ ⊗ ⊗ k Moreover, the k-fold tensor product space W is spanned by all such unit vectors. For a permutation π Sk and a k-tuple u = N(u1,...,uk), the action of π on u is defined as ∈ π(u) = (u ,...,u ). In a natural way, we may extend this to define the action of π on π(1) π(k) the unit vector e(u) as π(e(u)) = e(π(u)) = e(u ) e(u ) ... e(u ). (8) π(1) π(2) π(k) ⊗ ⊗ ⊗ As before, we fix an arbitrary total ordering on the vertex set V, say v v ... v . 1 2 n ≺ ≺ ≺ Then, we consider the set of ordered k-tuple of distinct elements of V, which is usually 5 written as “wedge” products: V = u u ... u : u u ... u , where u ,...,u V . (9) 1 2 k 1 2 k 1 k (cid:18)k(cid:19) { ∧ ∧ ∧ ≺ ≺ ≺ ∈ } Here, u u ... u is notation for the k-tuple (u ,u ,...,u ) where u u ... u . 1 2 k 1 2 k 1 2 k The e∧xteri∧or po∧wer kW is a vector subspace of kW and we will use ≺V to≺index≺this k n -dimensional space.VThus, we may identify kWNwith C(Vk) in the same(cid:0)w(cid:1)ay we identify k (cid:0) (cid:1)kW with CVk. The exterior power kW isVspanned by the “wedge” vectors N V e(u u ... u ) = [[u u ... u ]] e(u ) e(u ) ... e(u ). (10) 1 2 k 1 2 k 1 2 k ∧ ∧ ∧ ≺ ≺ ≺ ⊗ ⊗ ⊗ k k A nice way to view the connection between W and W is via the anti-symmetrizer An,k defined as the following nk × nk matrix:N V (cid:0) (cid:1) 1 A = sgn(π)e(π(v))e(v)†. (11) n,k √k! v∈(VXk),π∈Sk In what follows, we show the role of A in defining the exterior kth power kG, for a n,k k graph G. As a consequence, we note that G is a signed quotient of the k-foldVCartesian product of G modulo a natural equitable pVartition. Lemma 5. Let G be a graph on n vertices and k be an integer where 1 k n 1. The ≤ ≤ − following properties hold: 1. AT A = I . n,k n,k (n) k 2. A AT commutes with A(G(cid:3)k). n,k n,k 3. A( kG) = AT A(G(cid:3)k)A . n,k n,k V Proof. See [4]. k We note that Lemma 5 is similar to Fact 2. So from the third property above, G may be viewed as the “quotient” of G(cid:3)k modulo an equitable partition π induced by VAn,k; that is, kG = G(cid:3)k/π. V 4 Basic Properties We start with the simplest fact about the exterior kth power: cases when k = 1 and k = n. Fact 6. For any n-vertex signed graph Σ, we have 1Σ = Σ, and nΣ = K . 1 V V Proof. Follows immediately from the definitions. 6 k Next, we show that the exterior power G is well-defined up to switching equivalence; k that is, the signed graph G we obtainVis independent of the choice of ordering on the k vertex set V of G. This alVlows us to simply state G without fear of ambiguity. To this k end, let G denote the signed graph obtained froVm ordering V according to . ≺ ≺ V Fact 7. Let G = (V,E) be a graph. For any two total orderings and ′ over V, we have k k ≺ ≺ G G. ≺ ∼ ≺′ V V Proof. The total ordering determines the map A≺ . Let ′ be a total ordering which ≺ n,k ≺ differs from by a transposition on two vertices u and v. In a similar manner, the total ordering ′ d≺etermines its own anti-symmetrizer A≺′ . Define a diagonal matrix D with ≺ n,k uv 1 entries where, for each a V , its (a,a)-entry is ± ∈ k (cid:0) (cid:1) 1 if u a and v a e(a)†D e(a) = − ∈ ∈ (12) uv (cid:26) +1 otherwise The two anti-symmetrizers of and ′ are connected by D as follows: uv ≺ ≺ A≺′ = A≺ D . (13) n,k n,k uv k k This shows that G are switching equivalent to G since ≺ ≺′ V V A( k G) = (A≺′ )TA(G(cid:3)k)A≺′ (14) ≺′ n,k n,k V = DT (A≺ )TA(G(cid:3)k)A≺ D , by Equation (13) (15) uv n,k n,k uv = D−1A( k G)D , since DT = D−1. (16) uv ≺ uv uv uv V In general, if and ′ are related by a permutation σ, we may apply induction on the ≺ ≺ number of transpositions that form σ. The next fact shows that there is a mirror-symmetric isomorphism in the sequence of k exterior powers G. V Fact 8. Let G be a graph on n vertices and let 1 k n 1. Then, kG = n−kG . ∼ ≤ ≤ − | | | | V V Proof. The map τ from V to V defined as τ(u) = V(G) u is the claimed isomorphism. k n−k \ Ifuisadjacenttov in (cid:0)kG(cid:1) ,th(cid:0)enu(cid:1) v = a,b forsomeverticesaandbwith(a,b) E(G). Since (V(G) u) (V(|GV) v|) = u v△, this {impl}ies τ(u) is adjacent to τ(v) in n−k∈G . The \ △ \ △ | | converse follows in a similar fashion. V Remark: Fact 8 was also described in Osborne [8]; we provide its proof for completeness. A similar mirror-symmetry condition is also known for Johnson graphs (see Godsil and Royle [6]). Next, we show that the exterior power, as a graph operator on signed graphs, preserves switching equivalence. Fact 9. Let Σ and Σ be two signed graphs on n vertices satisfying Σ Σ . Then, 1 2 1 2 k k ∼ Σ Σ for each positive integer k with 1 k n 1. 1 2 ∼ ≤ ≤ − V V 7 Proof. If Σ Σ , then there is a diagonal n n matrix D with 1 entries so that A(Σ ) = 1 2 2 DA(Σ )D. T∼his implies A(Σ(cid:3)k) = D⊗kA(Σ(cid:3)×k)D⊗k. Let Dˆ be a±diagonal matrix with 1 1 2 1 ± entries of dimension n where, for each u V , its (u,u)-entry is defined as k ∈ k (cid:0) (cid:1) (cid:0) (cid:1) k e(u)†Dˆe(u) = e(u )†De(u ), (17) j j Yj=1 which depends on the product of the diagonal entries of D. We note that A Dˆ = D⊗kA . (18) n,k n,k Therefore, we have A( kΣ ) = AT A(Σ(cid:3)k)A (19) 2 n,k 2 n,k V = AT D⊗kA(Σ(cid:3)k)D⊗kA (20) n,k 1 n,k = Dˆ AT A(Σ(cid:3)k)A Dˆ (21) n,k 1 n,k = DˆA( kΣ )Dˆ, (22) 1 V which proves the claim. Inthefollowing, weconsider thek-foldCartesianproductgraphG(cid:3)k minus its“diagonal” (which are the k-tuples containing a repeated element), but without the conjugation (or quotient) action. We relate this to the gain graphs and signed graphs corresponding to k G. Note that there is a natural way to convert a gain graph over the symmetric group iVnto a signed graph – simply take the sign of the permutations which label the edges of the gain graph. But, first we recall some definitions about covers of gain graphs. Let Φ = (G,X,ϕ) be a gain graph on a graph G = (V,E) and a group X with the group-valued edge-signing function ϕ : E X. The graph is called a X -cover of Φ if the adjacency matrix of is → C | | C given by A( ) = A(Gg) P . (23) g C ⊗ gX∈X Here, Gg is the subgraph of G induced by edges which are signed with g X; that is, ∈ Gg = (V,Eg) where Eg = e E : ϕ(e) = g . Also, P is the X -dimensional permutation g { ∈ } | | matrix induced by g; its entries are given by P [a,b] = [[a = gb]], for group elements a,b X. g ∈ Fact 10. Let G = (V,E) be a graph on n vertices and let k be a positive integer 1 k < n. Then, G(cid:3)k ker(AT ) is a S -cover of the gain graph Φ( kG,S ,ϕ). ≤ \ n,k | k| k V k Proof. Let be the S -cover of Φ( G,S ,ϕ). Each vertex of is of the form (u,π) where k k uφ(∈u,(cid:0)πVk)(cid:1)=anπdC(uπ).∈WSek|c.laLi|emt Dtha=t φkeirs(AVanTn,kis)oamnodrpchoinssmidebrettwheeemnapaφCnd: CG(cid:3)→k GD(cid:3).k \SuDppdoesfien(eud,πas) C \ and (v,τ) is adjacent in . This implies u and v are adjacent in G∧k and τ = π ϕ(u,v). Therefore, π(u) is adjacenCt to τ(v) = ϕ(u,v)(π(v)) in G(cid:3)k D from the definition of◦the gain k \ graph Φ( G,S ,ϕ). k V 8 Corollary 11. Let G be a graph with at least three vertices and let D = a a : a V(G) . Then, G(cid:3)2 D is a double-cover of the signed graph 2G. { ⊗ ∈ } \ V 5 Unsigned Graphs To provide an illustration of upcoming techniques we used for signed graphs, we examine the exterior powers of some well-known unsigned families of graphs, such as, cliques, paths, cycles, and hypercubes. 5.1 Cliques Given positive integers n k ℓ 1, the graph J(n,k,ℓ) has vertices which are k-element ≥ ≥ ≥ subsets of [n] and edges between two subsets if their intersection is of size ℓ (see Godsil and Royle [6]). The family of graphs J(n,k,k 1) is known as the Johnson graphs. − Fact 12. Forpositive integers n and k where 1 k n 1, we have kK = J(n,k,k 1). n ∼ ≤ ≤ − | | − V k Proof. Since any two distinct vertices of K are adjacent, the exterior power K has each n n k-subset A of V adjacent to every other k-subset B of V provided A BV= 2. This is | △ | exactly the definition of the Johnson graphs J(n,k,k 1). − The above fact also appeared in [8]; we include its proof for completeness. 5.2 Paths Fact 13. For positive integers n and k where 1 k n 1, the exterior power of a path k ≤ ≤ − P is always balanced. n V Proof. Let the vertex set of P be V = a ,...,a with a is adjacent to a whenever n 0 n−1 i j { } i j = 1 except that a is only connected to a and a is only connected to a . By Fact 0 1 n−1 n−2 − ± 7, we may use the ordering a a whenever i < j. Consider an arbitrary cycle of length ℓ in i j ≺ kP that is given by the sequence of vertices w ,...,w , where w V . The permutation n 1 ℓ i ∈ k tVhat connects wi and wi+1 is always the identity permutation since wi (cid:0)w(cid:1)i+1 = aj,aj+1 for △ { } k some j. Thus, the sign of all edges in P is always positive. n V 5.3 Cycles Fact 14. For positive integers n and k where 1 k n 1, the exterior power of a cycle k ≤ ≤ − C is balanced if and only if k is odd. n V Proof. Let the vertex set of C be V = a ,...,a with a is adjacent to a whenever n 0 n−1 i j { } i j 1 (mod n). ByFact7, wemayusetheorderinga a whenever i < j. Consider an i j − ≡ ± ≺ k arbitrarycycle oflength ℓ in C that isgiven by thesequence ofvertices w ,...,w , where n 1 ℓ wi ∈ Vk . The permutation tVhat connects wi and wi+1 is a k-cycle if wi△wi+1 = {a0,an−1}, other(cid:0)wis(cid:1)e it is the identity permutation. Since a k-cycle has a negative sign whenever k is k even, this shows C is balanced if and only if k is odd. n V 9 We will later generalize Facts 13 and 14 for signed graphs in Section 6. 5.4 Hypercubes Fact 15. Let n 3 be a positive integer and let k be an integer where 1 k N 1 and N = 2n. Th≥en, kQ is a signed bipartite graph and kQ is unbalan≤ced e≤xcept−for n n k = 1,N 1. V V − k Proof. To see that Q is bipartite, note that we may identify the vertices of Q with n n | | the set V = 0,1 n Vof binary strings of length n. There is a natural bipartition of V into { } V = W W according to the Hamming weight of the strings, where W and W are the 0 1 0 1 ⊎ binary strings with even and odd Hamming weight, respectively. Let V be the collection of ℓ k-subsets of V which contain ℓ elements from W and k ℓ elements from W . Then, we 0 1 k − have a bipartition Q = V V where V = V : ℓ even and V = V : ℓ odd . n 0 1 0 ℓ 1 ℓ ⊎ { } { } Note, each vertex inVV0 is connected to only verticUes from V1, and vice versa.U k By Lemma 16, Q is unbalanced, for k = 1,N 1, since Q contains the claw K n n 1,3 6 − as a subgraph wheVnever n 3. Note 1Q = Q is trivially balanced and N−1Q is n n n ≥ balanced since Qn is bipartite (see CorolVlary 20). V 6 Balanced Characterization k In this section, we characterize those signed graphs Σ for which Σ is balanced; that is, k k signed graphs Σ which satisfy Σ Σ . Our main result isVTheorem 1, but first we ∼ | | k prove several preliminary lemmVas. TheVnext lemma shows that if Σ is balanced, then Σ does not contain the claw K1,3 as a subgraph; this holds if k iVs strictly smaller than | | V(Σ) 1. | |− Lemma 16. Let Σ be a signed graph on n vertices. If K is a subgraph of Σ , then kΣ 1,3 | | is not balanced, for 2 k n 2. V ≤ ≤ − Proof. Let Σ = (G,σ) be a signed graph where G = (V,E) contains K as a subgraph. 1,3 By switching around the center of the claw, we may assume that the subgraph K is all 1,3 positive. Suppose the vertices of the claw is V = a,b,c,d , where a is the center of the 1 { } claw, and that V = V V , where V is the set of vertices of G that is not part of the claw. 1 2 2 ⊎ By Fact 7, we may assume a total ordering on V which starts with the vertices of V followed 1 by the vertices of V (in some arbitrary order): 2 a b c d ... (24) ≺ ≺ ≺ ≺ k Consider the cycle on six vertices in K defined by the following sequence: 1,3 V a b Ω, b c Ω, a c Ω, c d Ω, a d Ω, b d Ω, (25) ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ where Ω is the wedge product of some arbitrary k 2 elements from V . Note the above 2 − sequence induces a negative C (see Figure 2). 6 10