ars mathematica contemporanea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 12 (2017) 183-203 Cycle bases of reduced powers of graphs Richard H. Hammack Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, Virginia, USA Gregory D. Smith Department ofApplied Science, The College ofWilliam and Mary, Williamsburg, VA, USA Received 22 May 2015, accepted 13 September 2016, published online 26 November 2016 We define what appears to be a new construction. Given a graph G and a positive integer k, the reduced kth power of G, denoted G(k), is the configuration space in which k indistinguishable tokens are placed on the vertices of G, so that any vertex can hold up to k tokens. Two configurations are adjacent if one can be transformed to the other by moving a single token along an edge to an adjacent vertex. We present propositions related to the structural properties of reduced graph powers and, most significantly, provide a construction of minimum cycle bases of G(k). The minimum cycle basis construction is an interesting combinatorial problem that is also useful in applications involving configuration spaces. For example, if G is the state-transition graph of a Markov chain model of a stochastic automaton, the reduced power G(k) is the state-transition graph for k identical (but not necessarily independent) automata. We show how the minimum cycle basis construction of G(k) may be used to confirm that state-dependent coupling of automata does not violate the principle of microscopic reversibility, as required in physical and chemical applications. Keywords: Graph products, Markov chains, cycle spaces. Math. Subj. Class.: 05C76, 60J27 1 Introduction Time-homogenous Markov chains [19] are used as a mathematical formalism in applications as diverse as computer systems performance analysis [21], queuing theory in operations research [18], simulation and analysis of stochastic chemical kinetics [12], and biophysical modeling of ion channel gating [10]. E-mail addresses: rhammack@vcu.edu (Richard H. Hammack), greg@wm.edu (Gregory D. Smith) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 184 Ars Math. Contemp. 12 (2017) 111-126 Many properties of a Markov chain, such its rate of mixing and its steady-state probability distribution, can be numerically calculated using its transition matrix [24]. A continuous-time Markov chain X(t) (t > 0) with a finite number of states {1,..., n} is defined by an initial probability distribution, ^¿(0) = Pr{X(0) = i}, and a transition matrix Q = (qij) where 1 < i, j < n, qij > 0 for i = j and qu = - J2j=i qij, so called because, for i = j, qij = limdi^0 Pr{X(t + dt) = j |X(t) = i}/dt. The requirement that Q has zero row sums, J2 j qij = 0, corresponds to conservation of probability, J2i ni(t) = 1, in the ordinary differential equation initial value problem, dn/dt = nQ with initial condition n(0), solved by the time-dependent discrete probability distribution n(t) = (ni(t),..., (t)) where ni(t) = Pr{X (t) = i}. A CTMC with a single communicating class of n < ro states is irreducible, positive recurrent, and has a unique steady-state probability distribution that solves nQ = 0 subject to J2i ni = 1 (by the Perron-Frobenius theorem). The Perron vector and steady-state distribution n is the limiting probability distribution of the Markov chain, ||n(t) - n || = 0, for any initial condition satisfying conservation of probability, J2i n (0) = 1. In general, the calculation of steady-state distributions and other properties for Markov chains with n states requires algorithms of O(n3) complexity. Many open questions in the physical and biological sciences involve the analysis of systems that are naturally modeled as a collection of interacting stochastic automata [3,17,23]. Unfortunately, representing a stochastic automata network as a single master Markov chain suffers from the computational limitation that the aggregate number of states is exponential in the number of components. For example, the transition matrix for k coupled stochastic automata, each of which can be represented by an v-state Markov chain, has n = vk states and requires algorithms of O(v3k) complexity. Many results are relevant to overcoming combinatorial state-space explosions of coupled stochastic automata. For example, memory-efficient numerical methods may use ordinary Kronecker representations of the master transition matrix Q = J2^ R^« where the R£n are size v, and many are identity matrices, eliminating the need to generate and store the size vk transition matrix [9]. Kronecker representations may be generalized to allow for matrix operands whose entries are functions that describe state-dependent transition rates, i.e., Q = 0«=1 Fn and Fn(i, j) : x«=1Xn ^ R where Xn(t) is the state of the nth automata [5]. Hierarchical Markovian models may be derived in an automated manner and leveraged by multi-level numerical methods [7]. Redundancy in master Markov chains for interacting stochastic automata can often be eliminated without approximation. Both lumpability at the level of individual automata and model composition have been extensively researched, though the latter reduces the state space in a manner that eliminates Kronecker structure [4,6,13]. To see this, consider k identical and indistinguishable stochastic automata, each with v states, that interact via transition rates that are functions of the global state, that is, Q = 0k F where F(i, j) : x i=1 n ^ R where n,(t) = £«=11{X„ (t) = ¿} is the number of automata in state £ As defined Q, is size vk, however, states may be lumped using symmetry in the model specification to yield an equivalent master Markov chain of size n = (k+k-1). Although model reduction in this spirit is intuitive and widely used in applications, the mathematical structure of the transition graphs resulting from such contractions does not appear to have been extensively studied. More concretely, let G represent the transition graph for an v-state automaton with transition matrix Q = (qij). As required in many applications, we assume that Q is irreducible R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 185 and that state transitions are reversible (qj > 0 ^ j > 0, i = j). Thus, the transition graph G corresponding to Q is simple (unweighted, undirected, no loops or multiple edges) and connected (by the irreducibility of Q). The transition graph G has adjacency matrix A(G) = (aj) where an = 0, and for i = j, aj = 0 when qj = 0 and aj = 1 when qij > 0. The transition graph for the master Markov chain for k automata with transition graphs Gn is the Cartesian graph product Gi DG2 □ • • • nGk. If these k automata are identical, the transition graph for the master Markov chain is the kth Cartesian power of G, that is, the k-fold product Gk = G^G^ • • • □G. The focus of this paper is the k-th reduced power of G, i.e., the transition graph of the contracted master Markov chain for k indistinguishable (but not necessarily independent) v-state automata with isomorphic transition graphs. The remainder of this paper is organized as follows. In Sections 2-3 we formally define the reduced power of a graph and interpret it as particular configuration space. Sections 46 present our primary result, the construction of minimal cycle bases of reduced graph powers. Section 7 explicates the relevance of these minimal cycle bases to applications that do not allow state-dependent coupling of automata to introduce nonequilibrium steady states. 2 Reduced Cartesian powers of a graph There are several equivalent formulations of the reduced power of a graph. For the first formulation, recall that given graphs G and H, their Cartesian product is the graph G^H whose vertex set is the Cartesian product V(G) x V(H) of the vertex sets of G and H, and whose edge set is E(G^H) = {(x,u)(y,v) | xy G E(G) and u = v, or x = y and uv G E(H)}. This product is commutative and associative [14]. For typographical efficiency we may abbreviate a vertex (x, y) of G^H as xy if there is no danger of confusion. The kth Cartesian power of a graph G is the k-fold product Gk = G^G^ • • • □G. The symmetric group Sk acts on Gk by permuting the factors. Specifically, for a permutation n G Sk the map (xi, x2, . . . , xk ) ^ (xn(1), xn(2), . . . , xw(k}) is an automorphism of Gk. The kth reduced power of G is the graph that has as vertices the orbits of this action, with two orbits being adjacent if Gk has an edge joining one orbit to the other. Said more succinctly, the reduced kth power is the quotient Gk/Sk of Gk by its Sk action. Figure 1 shows a graph G next to G2 = G^G. The S2 action on G2 has as orbits the singletons {aa}, {bb}, {cc}, {dd}, along with the pairs {ab, 6a}, {ac, ca}, {ad, da}, {bc, cb}, {bd, db}, and {cd, dc}. Let us identify a singleton orbit such as {aa} with the monomial aa = a2, and a paired orbit such as {ab, ba} with the monomial ab (with ab = ba). The reduced power G(2) appears on the right of Figure 1. Note that two monomials xy and uv are adjacent in G(2) provided that xy and uv have a common factor, and the remaining two factors are adjacent vertices of G. As each monomial xy corresponds uniquely to the 2-multiset {x, y} of vertices of G, we can also define the reduced power G(2) as follows. Its vertices are the 2-multisets of vertices of G, with two multisets being adjacent precisely if they agree in one element, and the other elements are adjacent in G. 186 Ars Math. Contemp. 12 (2017) 111-126 Qd 0 c G ad bd i cd dd ad bd ac bc 1 cc dc ac bc c2 Ob < >- 1 >— ---C > < >- i ab bb cb db ab b2 G(2) i i GOG oa S- -¿— — 3— - 3 aa ba ca da a2 cd -o d2 Figure 1: A graph G, the Cartesian square G2 = GOG, and the reduced power For each x e V(G), the vertices {xv | v e V(G)} induce a subgraph Gx = G of G(2). These subgraphs are shown dashed, dotted and solid in G(2) . Note Gx and Gy intersect precisely at vertex xy if x = y. In general, higher reduced powers G(k) can be understood as follows. Suppose V(G) = {ai, a2,..., av}. Any vertex of G(k) is the Sk-orbit of some x = (xi; x2,..., xk) G V(Gk). For each index 1 < i < v, say x has n > 0 coordinates equal to a^ Then 5^V=1 n® = k, and the Sk-orbit of x consists precisely of those k-tuples in V(Gk) having Hi coordinates equal to a®, for 1 < i < v. This orbit - this vertex of G(k) - can then be identified with either the degree-k monomial an a>2 • • • a^, , or with the k-multiset { ai, ai,. .., ai | a2, a2,. .., a2 |......| av, av, ..., av }, (2.1) where v -1 dividing bars are inserted for clarity. We will mostly use the monomial notation for V (G(k)), but will also employ the multiset phrasing when convenient. Let us denote the set of monic monomials of degree k, with indeterminates V(G), as Mk(G), with M0(G) = {1}. The above, together with the definition of the Cartesian product, yields the following. Definition 2.1. For a graph G with vertex set {ai; a2,..., av}, the reduced fcth power G(k) is the graph whose vertices are the monomials an1 a22 • • • a2v G Mk (G). For edges, if aiaj is an edge of G, and f (ai; a2,... av) G Mk-i(G), then aif (ai; a2,..., av) is adjacent to ajf (ai; a2,..., av). Figure 2 shows the three-cycle G = C3 and its reduced second and third powers. Figure 3 shows the five-cycle and its reduced second and third powers. The reduced power G(k) is not to be confused with the symmetric power of G, for which each vertex represents a k-subset of V(G), and two k-subsets are joined if and only if their symmetric difference is an edge of G [1,2]. The multiset notation (2.1) gives a quick formula for the number of vertices of reduced kth powers. This presentation describes the multiset as a list of length k + v -1 involving k symbols ai, 1 < i < k, and v -1 separating bars. We can count the multisets by choosing k slots for the ai's and filling in the remaining slots with bars. Therefore, when |V(G)| = v, V (G(fc)) k + v - 1 k (2.2) R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 187 The number of vertices in Gk that are identified with vertex a^1 a^2 • • • a^" G V(G(k)) in the quotient G(k) = Gk/Sk is given by the multinomial coefficient (n n k n ) . Definition 2.1 says that for each edge a^j of G, and for each monomial f G Mk-1 (G), there is an edge of G(k) from af to aj f. Because there are ( k+m-2\ k-1 such monomials f, E(G(k)) = |E (G)| k + v - 2 k- 1 (2.3) 3 Reduced graph powers as configuration spaces The reduced power G(k) is the transition graph of the contracted master Markov chain for k identical and indistinguishable v-state automata, each with transition graph G. Consequently, an intuitive way of envisioning G(k) is to imagine it as a configuration space in which k indistinguishable tokens are placed on the vertices of G, so that any vertex can hold up to k tokens. The monomial an1 an2 • • • an" then represents the configuration in which n tokens are placed on each vertex a^ Two configurations are adjacent if one can be transformed to the other by moving a single token along an edge of G to an adjacent vertex. In this way G(k) is interpreted as the space of all such configurations. See [11] for a related construction in which no vertex can hold more than one token. The reduced power G(k) may also be interpreted as the reachability graph for a fundamental class of stochastic Petri nets with k tokens, v = |V(G)| places, and 2|E(G)| flow relations (directed arcs) between places [8,22]. The arc from place aj (origin) to place aj (destination) has firing rate n^ given by the product of transition rate qj and the number n of tokens in the origin place. That is, the aj ^ aj firing time is the minimum of n exponentially distributed random variables with expectation 1 /qj. The aj ^ aj firing rate per token will be denoted qjj [an1 an2 • • • an" ] when it is a function of the global state (token configuration) of the stochastic Petri net. The token interpretation can be helpful in deducing properties of reduced powers, such as the following. 188 Ars Math. Contemp. 12 (2017) 111-126 Proposition 3.1. The vertex a?1 a?2 • • • a?" of has degree deg (a?1 a?2 ••• a?») = (a11 a2 2 • • • aV") = > degG(ai). E i Proof. The configuration a?1 a?2 • • • can be transformed to an adjacent configuration only by moving a token on some vertex ai (with ni > 1) to an adjacent vertex. □ cd2 c d Figure 3: The five-cycle C5 and its second and third reduced powers C(2) and C(3). 2 a 3 3 b e 3 3 d c R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 189 4 Cycle bases and minimum cycle bases Here we quickly review the fundamentals of cycle spaces and bases. The following is condensed from Chapter 29 of [14]. For a graph G, its edge space E(G) is the power set of E(G) viewed as a vector space over the two-element field F2 = {0,1}, where the zero vector is 0 = 0 and addition is symmetric difference. Any vector X G E(G) is viewed as the subgraph of G induced on X, so E(G) is the set of all subgraphs of G without isolated vertices. Thus E(G) is a basis for E(G), and dim(E(G)) = |E(G)|. The vertex space V(G) of G is the power set of V(G) as a vector space over F2. It is the set of all edgeless subgraphs of G and its dimension is |V(G)|. We define a linear boundary map SG : E(G) ^ V(G) by declaring that SG(xy) = x+y on the basis E(G). The subspace C(G) = ker(SG) is called the cycle space of G. It contains precisely the subgraphs in E(G) whose vertices all have even degree (that is, the Eulerian subgraphs). Because every such subgraph can be decomposed into edge-disjoint cycles, each in C(G), we see that C(G) C E(G) is spanned by the cycles in G. The dimension of C(G), denoted ^(G), is called the (first) Betti number of G. If G is connected, the rank theorem applied to SG yields P(G) = |E(G)|-|V (G)| + 1. (4.1) A basis for the cycle space is called a cycle basis. To make a cycle basis of a connected graph G, take a spanning tree T, so the set S = E(G) - E(T) has |E(G) | - |V(G) | +1 = P(G) edges. For each e G S, let Ce be the unique cycle in T + e. Then the set B = {Ce | e G S} is linearly independent. As B has cardinality P(G), it is abasis (see Figure 4). The elements of a cycle basis are naturally weighted by their number of edges. The total length of a cycle basis B is the number ¿(B) = J2cess |C|. A cycle basis with the smallest possible total length is called a minimum cycle basis, or MCB. cd 2 a 2 2 b e 2 2 d c Figure 4: A spanning tree T of G = G^2). The set S = E(G) - E(T) has P(G) = 25 - 15 + 1 = 11 edges. For each e G S, let Ce be the unique cycle in T + e. The set {Ce | e G S} is a cycle basis for G, but not a minimum cycle basis (see Figure 5). 190 Ars Math. Contemp. 12 (2017) 111-126 The cycle space is a weighted matroid where each element C has weight | C |. Hence the Greedy Algorithm [20] always terminates with an MCB: Begin with M = 0; then append shortest cycles to it, maintaining independence of M, until no further shortest cycles can be appended; then append next-shortest cycles, maintaining independence, until no further such cycles can be appended; and so on, until M is a maximal independent set. Then M is an MCB. Here is our primary criterion for determining if a cycle basis is an MCB. (See Exercise 29.4 of [14].) Proposition 4.1. A cycle basis B = {Bi; B2,..., for a graph G is an MCB if and only if every C G C (G) is a sum of basis elements whose lengths do not exceed |C |. For graphs G and H, a weak homomorphism p : G ^ H is a map p : V(G) ^ V(H) having the property that for each xy of G, either p(x)p(y) is an edge of H, or p(x) = p(y). Such a map induces a linear map p* : E(G) ^ E(H) defined on the basis E(G) as p*(xy) = p(x)p(y) provided p(x) = p(y), and p*(xy) = 0 otherwise. Similarly we define pV : V(g) ^ V(H) as pV(x) = p(x) on the basis V(G). Thus we have the following commutative diagram. (Check it on the basis E(G).) p* E(G)---> E(H) ¿G ¿H V(G)-—-> V(H) From this, p* restricts to a map C(G) ^ C(H) on cycle spaces, because if C g C(G), then ¿G (C) = 0, whence ¿Hp*(C) = pV¿G(C) = 0, meaning p*(C) G ker(£H) = C(H). Certainly if p is a graph isomorphism, then p* is a vector space isomorphism. Of special interest will be the projections pj : Gk ^ G, wherepi(xi, x2,..., xk) = x4. These are weak homomorphisms and hence induce linear maps p* : C(Gk) ^ C(G). Another important map is the natural projection n : Gk ^ G(k) sending each k-tuple x = (x i, x2,..., xk) to the monomial representing the -orbit containing x. This map n* also is a weak homomorphism, inducing a linear map n* : C(Gk) ^ C(G(k)). Lemma 4.2. If G is connected, the map n* : C(Gk) ^ C(G(k)) is surjective. Proof. Because any element of C(G(k)) is an edge-disjoint union of cycles, it suffices to show that any cycle C = /o/i • • • /„/o G C(G(k)) equals n*(C') for some C G C(Gk). For each index i, let xjyi+i G E(Gk) be an edge for which n*(xjyi+i) = n(xj)n(yi+i) = /j/i+i. (Each xj, yj is a k-tuple, and index arithmetic is modulo n.) Note that n(xj) = n(yj), meaning xj and yj are in the same -orbit, that is, yj equals xj with its coordinates permuted. We will argue that each pair yj, xj can be joined by a path Pj in Gk, with n* (Pj) = 0. This will prove the lemma because then C' = Po + xoyi + Pi + xiy2 + P2 + ... + P„ + x„yo G C(Gk) satisfies n*(C') = C. R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 191 Consider two vertices (.. .a.. .b...) and (.. .b... a...) of Gk that are identical except for the transposition of two coordinates a and b. Take a path a = v0v\ • • • vq = b from a to b in G. Now form the following two paths in Gk Q = (... a .. .b ...)(.. .vi ... b ...)(... V2 ...b...) ... (. . .b . . .b . ..) R = (...b...a...)(...b...v1 ...)(...b...v2 ...)... (...b...b...). Concatenation of Q with the reverse of R is a path from (.. .a.. .b...) to (.. .b.. .a...). Moreover n*(Q+R) = 0 because the images of the jth edges of Q and R are always equal; hence the edges cancel in pairs. As yi and xi differ only by a sequence of transpositions of their coordinates, the above construction can be used to build up a path Pi from yi to xi with n(Pi) = 0. □ We have seen that the projections pi : Gk ^ G induce linear maps C(Gk) ^ C(G). But there seems to be no obvious way of defining a projection G(k) ^ G. Still, it is possible to construct a natural linear map p* : C(G(k)) ^ C(G). To do this, recall that any edge of G(k) has form af bf where ab G E(G) and f G Mk-1(G). We begin by defining p* on the edge space. Put p*(af bf) = ab for each edge af bf in the basis E(G(k)) and extend linearly to a map p* : E(G(k)) ^ E(G). Note that J]k=1 P* = P* ◦ n*. (Confirm it by checking it on the basis E(Gk) of E(Gk).) Now, if X G C(G(k)), then Lemma 4.2 guarantees X = n*(Y) for some Y in the cycle space of Gk. Then p*(X) = p* (n* (Y)) = Ek=ip**(Y) G C(G). We now have a linear map p* : C(G(k)) ^ C(G) for which p*(af bf) = ab. ab C5? ae_.-y ''■■.jab ¿bey- ad d2 cd b2e2 ae y'' '■■. ab be ",bc de\" o cd c2 be bd ?bc cd a 2 a Figure 5: The union {G^a} U B is an MCB for C(c(2)) = C(C5 a) Q S(c(2)). 192 Ars Math. Contemp. 12 (2017) 111-126 5 Decomposing the cycle space of a reduced power This section explains how to decompose the cycle space of a reduced power into the direct sum of particularly simple subspaces. To begin, notice that if f is a fixed monomial in Mk-1 (G), then there is an embedding G ^ G(k) defined as x ^ xf. Let us call the image of this map Gf. Notice that Gf is an induced subgraph of G(k) and is isomorphic to G. Proposition 5.1. For any fixed f e Mk-i(G), we have C (G(k)) = C (Gf) 0 ker(p*). Proof. Consider the map p* : C(G(k)) ^ C(G). Its restriction C(Gf) ^ C(G) is a vector space isomorphism. The proof now follows from elementary linear algebra. □ Next we define a special type of cycle in a reduced power. Given distinct edges ab and cd of G and any f e Mk-2 (G), we have a square in G(k) with vertices acf, bcf, bdf, adf. Let us call such a square a Cartesian square, and denote it as (abUcd)f. See Figure 6. We regard this as a cycle in the cycle space; it is the subgraph of G(k) that is precisely the sum of edges acf bcf + bcf bdf + bdf adf + adf acf. (Observe that this sum is zero if and only if ab = cd.) We remark that although a subgraph Gf may have squares, they are not Cartesian squares because they do not have the form specified above. Define the square space S(G(k)) to be the subspace of C(G(k)) that is spanned by the Cartesian squares. If S is a Cartesian square, then p*(S) = 0, so S(G(k)) C ker(p*). In the remainder of the paper we will show that in fact S(G(k)) = ker(p*), so that Proposition 5.1 gives C(G(k)) = C(Gf) 0 S(G(k)). Simultaneously we will craft a simple MCB for G(k) by concatenating MCBs of C(Gf) and S(G(k)). See Figure 5 for an example. 6 Cycle bases for reduced powers This section describes a simple cycle basis for the reduced kth power of a graph G. If G has no triangles, this cycle basis will be an MCB. (We do not consider MCBs in the cases that G has triangles because the applications we have in mind do not involve such situations. Constructing MCBs when G has triangles would be an interesting research problem.) Let G be a connected graph with v vertices and e edges. Recall that by Equations (2.2) and (2.3), the graph G(k) has (k+v-1) vertices, identified with the monomials Mk (G), and e(k+V-2) edges. Thus any cycle basis has dimension We first examine the square space. Any pair of distinct edges ab and cd of G corresponds to a Cartesian square (abDcd)f, where f e Mfc_2(G), so there are (2)(fc+V23) adf q- 2. (6.1) R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 193 such squares. But this set of squares may not be independent. Our first task will be to construct a linearly independent set of Cartesian squares. To begin, put V(G) = {a1, a2,..., av}. Let T be a rooted spanning tree of G with root a1, and arrange the indexing so its order respects a breadth-first traversal of T, that is, for each i the vertex ai is not closer to the root than any aj for which j < i (see Figure 7). 05 Figure 7: A rooted spanning tree T of G with V(G) = {a1, a2,..., av}, root a1, and indexing that respects a breadth-first traversal of T. With this labeling, any edge of T is uniquely determined by its endpoint aj that is furthest from the root. For each 2 < i < v, let ej be the edge of T that has endpoints aj and aj, with aj further from the root than ai. Let Mk-2(a1, a2,.. .aj) denote the monic monomials of degree k — 2 in indeterminates a1,a2,... ,aj, with 1 < j < v. Define the following sets of Cartesian squares in G(k). T = {(ejUej )f | 2 < i 3 and take three distinct edges aiaj-, a^am and apaq in G, and let f € Mk-3(G). Figure 8 indicates that these edges result in a cube in the kth reduced power. Each of the six square faces of this cube is in the square space. But the faces are dependent because any one of them is a sum of the others. Call a square face such as (aiaj Dagam)aq f a "top square" of a cube if the monomial aq f involves an indeterminate at with t > max{i, j, i, m}. Sets T and Q are constructed so as to contain no top squares. 194 Ars Math. Contemp. 12 (2017) 111-126 (A configuration of the type illustrated in Figure 8 may not always be a cube in the combinatorial sense. The reader is cautioned that if a»aj, a£am and apaq are the edges of a triangle in G, then two of the diagonally opposite vertices of the "cube" are the same, as (3) in K3 , shown in Figure 2. Here there is only one cube, which takes the form of a central vertex connected to the six vertices of a hexagon. This will cause no difficulties in what follows, even if we entertain the possibility that G does indeed have triangles.) There is another kind of dependency that is ruled out in the definition of T and Q, and we now sketch it. First, imagine G2. Consider two cycles A and B in G each having exactly one edge not in T, say a»aj and a^am, respectively. Envision AdB is as a torus in G2 with square faces, each edge shared by two faces. In adding up all the faces, the edges cancel in pairs, giving 0, so the squares are dependent. Removing the face a»aj da^am removes the dependency. Such squares a^ajOaeam show up in G(2)/ C G(k) as squares (ajajDajam)/ with a»aj, apaq G E(G) - E(T). Sets T and Q contain no such squares. Proposition 6.1. The set B = T U Q is linearly independent. Proof. We first show that T is linearly independent. Let X = J2(eiaej)/« be a sum of elements of T. Form the forest F C T consisting of all edges e» and ej that appear as edges of a squares in this sum, and let ab be an edge of F for which b is a leaf. Then any term (a^am Dab)/n of the sum is the unique square in the sum containing the edge a^b/n amb/n. Because no term can cancel this edge, we get X = 0, so T is linearly independent. To see that Q is linearly independent, consider a sum X = J2(aeamdej)/n of squares in Q. Again form a forest F C T of the edges ej and let ab be as before. Then any term (a£amDab)/„ is the unique square in the sum containing the edge a^b/« amb/n. Then X = 0 because no other term in the sum can cancel this edge; hence Q is linearly independent. Now we argue that the spans of T and Q have zero intersection. By the previous paragraph, any nonzero linear combination of squares in Q has edges of form (a£amDab)/„, with a^am G E(G) - E(T). But no linear combination of squares in T has such edges. Hence the spans have zero intersection, so B is linearly independent. □ Our next task is to show that B is actually a basis for the square space. In fact, we will show more: it is also a basis for ker(p*), and S(G(k)) = ker(p*). Our dimension counts will involve finding |T| and |Q|, and for this we use the following formulas. The first is standard; both are easily verified with induction. c) + c:') + c:2) + ••• + (D = ('+;+') («.2) oQ + i(r:')+2(rf) +... + <:■) = c::1)-r:::1) («.3) Take an edge ej of T with 3 < j. From its definition, T has (j - 2) (k+j_-23) squares of form (ejdej)/. We reckon as follows, using Equations (6.2) and (6.3) as appropriate. R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 195 |Y| = P - + --3) E(k + --2) - (k + V - 1) +1 + «< + --2) -fi(G) = e(k + -- 2) - (k + k - 1) +1 - ^(G) = fi(G(2)) - fi(G) = dimker(p*). Therefore B is a basis for both S(G(k) ) and ker(p* ). □ If k = 2, then B = {abOcd | ab, cd e E(G)} - [abUcd | ab, cd e E(G) - E(T)}, so |B| = (2) - (W2g)). It is interesting to note that if fi(G) < 1, then (^2G)) =0 and B consists of all squares in the square space; in all other cases it has fewer squares. 196 Ars Math. Contemp. 12 (2017) 111-126 a\ Figure 9: With T as indicated, the sets of squares Y and Q form a basis B = Y U Q of the square space of C5;3). Here Y = {(abdbc)f | / G {a, b, c}} U {(abdcd)f, (bcdcd)f | / G {a, b, c, d}} U{(abmde)f, (bcdde)f, (cddde)f | / G {a, b, c, d, e}}. Also Q = {(aeDab)f | / G {a, b}} U {(aeDbc)f | / G {a, b, c}} U {(aeDcd)f | / G {a, b, c, d}} U {(aeDde)f | / G {a, b, c, d, e}}. Note |Y| = 24 and |Q| = 14. The square (abDcd)e G B is the "top square" of the Cartesian cube abDcdnde. We now can establish the main result of this section, namely a construction of an MCB for the reduced kth power. Take an / G Mfc_i (G). Propositions 5.1 and 6.2 say C(G(k)) = C(Gf) 0 S(G(k)). (6.6) To any cycle C = c1 c2... cn in G, there corresponds cycle Cf = c1f c2f ... cnf in G(k). Theorem 6.3. Take a cycle basis C = {C1, C2,..., C^(G)} for G, and let B be the basis for S (G(k)) constructed above. Fix / G Mk-1(G) and put Cf = {C1f, C2f,..., c^(g)/}. Then C/ U B is a cycle basis for If C is an MCB for G, and G has no triangles, then this basis is an MCB for G(k). Proof. That this is a cycle basis follows immediately from Equation (6.6). R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 197 Now suppose C is an MCB for G, and that G has no triangles. It is immediate that G(k) has no triangles either. The proof is finished by applying Proposition 4.1. Take any C e C(G(k)), and write it as C = E Gi + E Bj, iei jeJ where the Gi are from Cf and the Bj are from B. According to Proposition 4.1, it suffices to show that C has at least as many edges as any term in this sum. Certainly C is not shorter than any square Bj (by the triangle-free assumption). To see that it is not shorter than any Gi in the sum, apply p* to the above equation to get P*(C) = EP*(Gi) • iei Because p* : C(Gf) ^ C(G) is an isomorphism, the terms p*(Gi) are part of an MCB for G, and thus |p*(C)| > |p*(Gi)| = |Gi| for each i, by Proposition 4.1. Also |C| > |p*(C)| (as some edges may cancel in the projection) so |C| > |Gi|. □ Although Theorem 6.3 gives a simple MCB for reduced powers of a graph that has no triangles, the constructed basis is definitely not minimum if triangles are present. Several different phenomena account for this. Consider the case k = 2. First, if G has triangles, then for each vertex x of G, the second reduced power contains a copy Gx of G. These copies are pairwise edge-disjoint; an MCB would have to capitalize on triangles in each of these copies at the expense of squares in the square space. Moreover, as Figure 2 demonstrates, some of the squares in the square space will actually be sums of two triangles. The figure also shows that for a triangle A = abc in G, we do not get just the three triangles Aa, Ab and Ac, but also a fourth triangle ab bc ca not belonging to any Gx. We do not delve into this problem here. 7 Discussion We have defined what appears to be a new construction, the kth reduced power of a graph, G(k), and have presented a theorem for construction of minimal cycle bases of G(k). When G is the transition graph for a Markov chain, G(k) is the transition graph for the configuration space of k identical and indistinguishable v-state automata with transition graph G. Symmetry of model composition allows for interactions among stochastic automata, so long as the transition rates qij for i, j e {1, 2, • • • , v}, i = j are constant or functions of the number of automata n(t) in each state, 0 < n^(t) < k, 1 < I < v. G(k) does not pertain if transition rates depend on the state of any particular automaton, Xn(t) e {1, 2, ••• , v}, n e {1,2, ••• ,k},as this violates indistinguishability. For concreteness, consider a stochastic automata network composed of three identical automata, each with transition graph C5 and generator matrix, ( o qab [•] 0 0 qae \ Q = qba o qbc 0 0 0 qcb o qcd 0 0 0 qdc o qde V qea 0 0 qed o (7.1) 198 Ars Math. Contemp. 12 (2017) 111-126 where o's indicate the values required for zero row sum, qu = — J2j=i qj < 0, and qab[• ] indicates a functional transition rate that depends on the global state of the three automata. Assume constant transition rates qbc = qcd = qde = qea = ^ > 0 and qba = qcb = qdc = qed = qae = v > 0. Further assume that the automata may influence one another through the state-dependent transition rate, qab[ • ] = A + a (na[• ] - 1) + pub[• ] + 7«c[• ] + Jnd[• ] + ene[ • ], (7.2) where a, P, 7, J, e > 0 and [ • ] denotes the global state a11 a??2 • • • aV" that is the functional transition rate's argument. The transition rate qab : Mk(a1; a2,•• • , av) ^ R is a function of the global state via n : Mk(a1; a2,•• • , av) ^ N defined by n[ap a^2 • • • aV"] = The three automata are uncoupled when a, P, 7, J, e = 0 because this eliminates the dependence of qab[ • ] on the global state. (In this model specification, coupling an isolated component automaton to itself is equivalent to absence of coupling. Because qab[ • ] is the rate of an a ^ b transition, qab[ • ] is only relevant when the isolated automaton is in state a. This functional transition rate has the property that qab[a] = A when a, P, 7, J, e > 0 because nx[y] = 1 for x = y and 0 otherwise.) The transition matrix for the master Markov chain Q(3) is defined by the model specification in the previous paragraph. For example, the transition rate from global state ad2 to global state abd is q(3)[ad2, abd] = because nd[ad2] = 2 and qdb = ^ is not a function of the global state. Other examples are q(3)[c3, c2d] = nc[c3]qcd = 3v, q[a2c, a2d] = nc[a2c]qcd = v, q(3) [abe, b2e] = na[abe]qab[abe] = A + a (na [abe] — 1) + P n [abe] + 7 nc [abe] + J n^ [abe] + e ne [abe] = A + P + e q(3)[a3,a2b] = na[a3]qab[a3 ] = 3 (A + a (na[a3] — 1) + Pnb[a3] + 7n^a3] + Jnd[a3] + ene[a3]) = 3(A + 2a) q(3) [a2c, abc] = na[a2c]qab[a2 c] = 2 (A + a (na[a2c] — 1) + Pnb[a2c] + 7nc[a2c] + Jn^[a2c] + ene[a2c]) = 2 (A + a + 7) . This process of unpacking the model specification yields a master Markov chain with n = (fc+V-1) = (3+53-1) = 35 states. The master Markov chain has 210 transition rates qij > 0 corresponding (in pairs) to the 5(3+5-2) = 105 edges of the master transition graph C^3). The construction of minimal cycle bases of G(k) provided by Theorem 6.3 is especially relevant to stochastic automata networks that arise in physical chemistry and biophysics [15]. For many applications in these domains, the principle of microscopic reversibility requires that the stationary distribution of uncoupled automata satisfying global balance, nQ = 0 subject to J2i n = 1, also satisfies a stronger condition known as detailed balance, qij = E qjinj. i=j j=i R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 199 ni[imf ]qij [imf ] imf n[Uf ]qe [if ] nj [jmf ]qji[jmf ] nm [imf] qmi [imf] n [jtf] qim [jtf ] n:\itf ]qij [i£f ] jmf nm [jmf ]qmi[jmf ] if jtf nj jtf ]qji[j£f ] Figure 10: Many cycles of the directed, weighted transition graph for a master Markov chain for k coupled v-state automata correspond to Cartesian squares (ijD£m)f of the minimal cycle basis for the undirected, unweighted transition graph G(k), where i, j, £,m e {ai, a,2, ••• , av } and f e Mk~2(ai,a,2, ••• , av). In other words, nonequilibrium steady states are forbidden. Markov chains have this property when the transition rates satisfy the Kolmogorov criterion, namely, equality of the product of rate constants in both directions around any cycle in the transition matrix Q [16]. For an isolated automaton with transition graph C5 and transition matrix (7.1), the Komol-ogorov criterion is qab[a] qbc qcd qde qea = qae qed qdc Qcb qba■ (7.3) Substituting the transition rates of the model specification, both those that are constant as well as qab [a] = A (7.2), yields the following condition on model parameters, X,pA = v5, (7.4) that ensures the stationary distribution of an isolated automaton will satisfy detailed balance. (3) By constructing the minimal cycle basis of C5 , we may verify that the master Markov chain for three uncoupled automata, each with transition graph C5, also exhibits microscopic reversibility under the same parameter constraints. To see this, recall that the minimal cycle basis of C53) has 39 linearly independent cycles. Microscopic reversibility for the master Markov chain for three uncoupled automata requires that, given (7.4) and a, /3, = 0, 39 Komolgorov criteria are satisfied, each corresponding to a Cj in the MCB for c(3). One cycle in the MCB for C(3) takes the form C5 f for fixed f e M2(a, b, c, d, e). The Kolmogorov criterion for this cycle is na[af]qab[af] • nb[bf]qbc[bf] • nc[cf]qcd[cf] • nd[df]qde[df] • ne[ef]qea[ef] = na[af]qae[af] • ne[ef]qed[ef] • nd[df]qdc[df] • nc[cf]qcb[cf] • m[bf]qba[bf], where, for typographical efficiency, here and below, we drop the superscripted (3) on the 200 Ars Math. Contemp. 12 (2017) 111-126 transition rates q(3) [•, •] of Q(3). Canceling identical terms of the form nx[xf] gives qab[af] • qbc[bf] • qcd[cf] • qde[df] • qea[ef] = qae[af] • qed[ef] • qdc[df] • qcb[cf] • qba[bf}. When this expression is evaluated, the result is another instance of (7.4), which is satisfied by assumption. (3) The remaining 38 Ci in the MCB for Cg ' are Cartesian squares (see Figure 10) that yield Kolmogorov criteria of the form, nj [imf ]qjj [imf] • nm[jmf]qm£[jmf] • nj [j£f\qji[j£f\ • ne[i£f]qem[i£f] = nm[imf]qm£[imf] • nj [i£f]qij [i£f] • ne[j£f]qem[j£f] • nj [jmf]qji[jmf], where f e Mi(a, b, c, d, e). For x = y, nx[xyf] = nx[x] + nx[y] + nx[f] = 1 + nx[f], so this criterion simplifies to (1 + nj[f])qjj [imf] • (1 + nm[f])qm£[jmf] • (1 + nj [f])qji[j£f] • (1 + ne[f])qem[i£f] = (1 + nm[f])qm£[imf] • (1 + ni[f])qj [i£f] • (1 + ne [f])qem[j£f] • (1 + nj [f])qji[jmf]. Canceling identical terms of the form (1 + nx[f ]) gives qij [imf ] qm [jmf] qji [j£f ] qim [i£f ] = qmi [imf ] qj [i£f ] qim [j£f ] qji [jmf ] (7.5) for (ijD£m)f e B = Y U Q with f e Ml(al,a2,... ,av). When the automata are not coupled, a, /3, = 0, the transition rates are not functions of the global state, and every factor on the left hand side has an equal partner on the right. Consequently, the 38 squares of B correspond to cycles in Q(3) that satisfy Komolgorov criteria. (3) We have shown that every cycle in the MCB for Cg ', given by Cg a U B, corresponds to a cycle in Q(3) that satisfies a Komolgorov criterion. For every cycle in Q(3), there is a representative in the cycle space C(C(3)) that is a linear combination (over the field F2) of elements of the MCB. It follows that every cycle in the master Markov chain satisfies the Komolgorov criterion. Thus, we conclude that the master Markov chain for three uncoupled automata exhibits microscopic reversibility provided an isolated automaton has this property. This property is expected, and yet important for model verification. In many applications, it is important to establish whether or not model composition (i.e., the process of coupling the automata) results in a master Markov chain with nonequilibrium steady states, in spite of the fact that an isolated component automaton satisfies detailed balance. Such nonequilibrium steady states may be objects of study or, alternatively, the question may be relevant because the master Markov chain is not physically meaningful when model composition introduces the possibility of nonequilibrium steady states [15]. Our construction of minimal cycle bases of reduced graph powers provides conditions sufficient to ensure that model composition does not introduce nonequilibrium steady states. In general, it is sufficient that (7.5) hold of every Cartesian square (ijU£m)f of the MCB for the undirected, unweighted transition graph G(k). In the example under discussion, many of these Komolgorov criteria do not involve the functional transition rate qab[}\ these conditions are satisfied without placing any constraints on the coupling parameters a,y,S,c. The remaining constraints take the form qab[amf ] qm£ [bmf ] qba [b£f ] qem [a£f ] = qm£ [amf ] qab[a£f ] qem [b£f ] qba [bmf ] (7.6) R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 201 for £m € {bc, cd, de, ae}. The Cartesian squares of concern are elements of the set {(abn^m)/ | £m € {bc, cd, de}} C T and (aedab)/ € Q. Note that £m = ab and, consequently, qm£ [bm/ ] = qm£ [am/], q*m[a/] = q£m[b/] and q6o[b£/] = q6o[bm/] = v. Thus, (7.6) simplifies to qab[a£/] = qab[am/] £m € {bc, cd, de, ae}. (7.7) To see how this requirement constrains the coupling parameters a, 7, S, e, we expand both sides of (7.7) using (7.2), for example, qab[a/] = A + a(na[a/] - 1) + ^n6[a£/] + Ync[a/] + Snd[a/] + ene[af/] = A + ana / ] + ] + 7nc[/] + Sn^/] + ene[/] where we used na[a£/] = 1 + na[£/]. Subtracting both sides of (7.7) by A + ana[/] + £n6[/] + Ync[/] + Snd[/] + ene[/] and using n-J/] = nx[£] + nx[/] we obtain ana [£] + [£]+7nc [£] + [£]+ene [£] = ana [m] + [m] + ■7nc [m] + Snd [m] + ene [m] for £m € {bc, cd, de, ae}. These four equations yield four parameter constraints that ensure detailed balance in the master Markov chain for the three coupled stochastic automata, for example, £m = bc gives ana [b] + [b] + Ync [b] + Snd [b] + ene [b] = ana [c] + [c] + 7nc [c] + Snd [c] + ene [c], which implies that ft = 7. Substituting £m = cd, de and ae, we find 7 = J, S = e and a = e, respectively. We conclude that a = ft = 7 = S = e. In our example, the three automata are coupled when one or more of a, 7, S, e is (3) positive. The analysis of Cartesian squares in the MCB for Cg shows that coupling the three automata in the manner specified by (7.2) will introduce nonequilibrium steady states unless the coupling parameters are equal. This result is intuitive because J2i ni [•] = k = 3 and, consequently, equal coupling parameters a = ft = 7 = S = e correspond to a functional transition rate that, for every global state, evaluates to the constant qab[ ] = A + a(k - 1) = A + 2a. The simplicity of this parameter constraint is a consequence of evaluating (7.5) in the context of the example model specification. In general, the resulting constraints may be more complex and less restrictive. Any choice of model parameters that simultaneously satisfies qij[im/] qm£[jm/] qji[j/] q*m[i/] = qmi[im/] qj [i/] q*m[j/] qji[jm/] for (ijD£m)/ € B = Y U Q with / € Mk-2(a1, a2,..., av) are conditions sufficient to ensure that the process of model composition (i.e., coupling k identical and indistinguishable v-state automata) does not introduce a violation of microscopic reversibility. Acknowledgments The work was supported by National Science Foundation Grant DMS 1121606. GDS acknowledges a number of stimulating conversations with William & Mary students enrolled in Spring 2015 Mathematical Physiology and Professor Peter Kemper. Thanks also to the referee for many helpful suggestions. 202 Ars Math. Contemp. 12 (2017) 111-126 References [1] A. Alzaga, R. Iglesias and R. Pignol, Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, J. Combin. Theory Ser. B 100 (2010), 671-682. [2] K. Audenaert, C. Godsil, G. Royle and T. Rudolph, Symmetric squares of graphs, J. Combin. Theory Ser. B 97 (2007), 74-90. [3] F. Ball, R. Milne and G. Yeo, Stochastic models for systems of interacting ion channels, IMA J. Math. Appl. Med. Biol. 17 (2000), 263-293. [4] A. Benoit, L. Brenner, P. Fernandes and B. Plateau, Aggregation of stochastic automata networks with replicas, Linear Algebra Appl. 386 (2004), 111-136. [5] A. Benoit, P. Fernandes, B. Plateau and W. Stewart, On the benefits of using functional transitions and Kronecker algebra, Perform. Eval. 58 (2004), 367-390. [6] P. Buchholz, Exact and ordinary lumpability in finite Markov chains, J. Appl. Probab. 31 (1994), 59-75. [7] P. Buchholz, Hierarchical Markovian models: Symmetries and reduction., Perform. Eval. 22 (1995), 93-110. [8] P. Buchholz and P. Kemper, Hierarchical reachability graph generation for Petri nets, Form. Methods Syst. Des. 21 (2002), 281-315. [9] J. Campos, S. Donatelli and M. Silva, Structured solution of asynchronously communicating stochastic modules, IEEE Trans. Software Eng. 25 (1999), 147-165. [10] D. Colquhoun and A. Hawkes, A Q-matrix cookbook: How to write only one program to calculate the single-channel and macroscopic predictions for any kinetic mechanism, in: B. Sakmann and E. Neher (eds.), Single-Channel Recording, Plenum Press, pp. 589-633, 1995. [11] R. Fabila-Monroy, D. Flores-Penaloza, C. Huemer, F. Hurtado, J. Urrutia and D. R. Wood, Token graphs, Graphs Combin. 28 (2012), 365-380. [12] D. Gillespie, Stochastic simulation of chemical kinetics, Annu. Rev. Phys. Chem. 58 (2007), 35-55. [13] O. Gusak, T. Dayar and J.-M. Fourneau, Lumpable continuous-time stochastic automata networks, European J. Oper. Res. 148 (2003), 436-451. [14] R. Hammack, W. Imrich and S. Klavzar, Handbook of product graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2nd edition, 2011. [15] T. Hill, Free Energy Transduction in Biology and Biochemical Cycle Kinetics, Springer-Verlag, New York, 1989. [16] F. Kelly, Reversibility and Stochastic Networks, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2011. [17] T. Liggett, Stochastic interacting systems: contact, voter and exclusion processes, volume 324 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1999. [18] M. Neuts, Structured stochastic matrices of M/G/1 type and their applications, volume 5 of Probability: Pure and Applied, Marcel Dekker, Inc., New York, 2nd edition, 1989. [19] J. Norris, Markov chains, Cambridge University Press, Cambridge, 1997. [20] J. G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. [21] B. Plateau and J. Fourneau, A methodology for solving markov models of parallel systems, J. Parallel Distrib. Comput. 12 (1991), 370-387. R. H. Hammack and G. D. Smith: Cycle bases of reduced powers of graphs 203 [22] W. Reisig, Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies, Springer-Verlag, Berlin, 2013. [23] W. Richoux and G. Verghese, A generalized influence model for networked stochastic automata, IEEE Trans. Syst., Man, and Cybern. A, Syst., Humans 41 (2011), 10-23. [24] W. Stewart, Introduction to the Numerical Solution of Markov Chains, Princeton University Press, Princeton, 1994.