/^creative ^commor ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 27-43 Cycle construction and geodesic cycles with application to the hypercube Paul C. Kainen Department of Mathematics and Statistics Georgetown University, Washington, DC 20057 USA Received 2 March 2013, accepted 23 April 2014, published online 9 June 2014 Abstract Construction of cycles in a graph is investigated, where cycles from particular subsets (such as bases) are added together so that each partial sum is also a cycle or each new cycle intersects the sum of the preceding terms in a nontrivial path. Starting with the geodesic cycles, a hierarchical construction is given. For the hypercube graph, geodesic cycles are characterized, and it is shown how hypercube geodesic cycles can be constructed in two steps from a special basis. Applications are given to inferring commutativity of a diagram in a groupoid from commutativity of some of its cycles. Keywords: Robust cycle basis, well-arranged sequence, geodesic cycle, Cayley graph, hypercube, forcing commutativity, groupoid diagram. Math. Subj. Class.: 05C38, I8B40 1 Introduction Let G be a graph. A cycle-subgraph of G is a connected, 2-regular subgraph. Let Cyc(G) denote the set of all cycle-subgraphs of G. Call S C Cyc(G) "weakly robust" if for every z G Cyc(G), there is an integer k > 1 and z1,... ,zk G S (not necessarily distinct) such that z = Z1 + Z2 +-----+ Zk (1.1) and for 2 < j < k — 1 zi + z2 + ■■■ + zj G Cyc(G); (1.2) that is, S is weakly robust if it spans the cycle space of G in such a way that every cycle-subgraph has all partial sums remaining cycle-subgraphs (not just Eulerian graphs). Call S "robust" if it is weakly robust and if, in addition, for 2 < j < k, zj n (z1 + ■ ■ ■ + zj-]) is anontrivialpath. (1.3) E-mail address: kainen@georgetown.edu (Paul C. Kainen) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 27 Ars Math. Contemp. 9 (2015) 93-107 Of course, S = Cyc(G) has these properties vacuously, taking k = 1. Also, (1.3) (1.2). The problem of finding a cycle basis which is weakly robust seems to have first appeared in print in a paper of Dixon and Goodman [2]. Given a spanning tree in a connected graph, one can construct a basis of cycles using the non-tree edges. In [2], it was conjectured that such bases are weakly robust but this was disproved by Syslo [22]. Later, it was shown by Dogrusoz and Krishnamoorthy [3] that the set of region boundaries of a plane graph, excluding the unbounded region, constitute a weakly robust basis. The problem was rediscovered in [12], including the new question of finding a robust basis, where we showed that for complete graphs, the set of all 3-cycles containing a fixed vertex determines a robust basis. A basis which is not weakly robust (due to A. Vogt) was exhibited. We also found a basis for the bipartite complete graph (the set of all 4-cycles through a fixed edge), which was shown to be weakly robust by Ostermeier et al. [19]. Our motivation was category theory and graph theory, while the work of Stadler and co-authors [9, 11, 15, 16, 19, 8] is also motivated by applications, especially in biochemistry. These latter papers, as well as [12], use notation which is different from that used here. The properties of cycle bases and related sets discussed below were developed to permit the propagation of commutativity from a basis of cycles to all of the diagram; see [13], [14]. In this paper, it is shown that the commutativity of a d-dimensional hypercube diagram in a groupoid can be forced by the commutativity of a carefully chosen subset of the square faces, containing approximately a fraction of 4/d of the square faces. In contrast, [13] showed that commutativity cannot be blocked by any family with fewer than d - 2 squares in a d-cube; that is, if all but d - 2 squares in a d-cube diagram in a groupoid are known to commute, then the entire diagram is commutative. The paper is organized as follows: Section 2 gives some basic graph-theoretic, algebraic, and topological background. The next section reviews the basic types of well-arranged sequences of cycles, providing the machinery used in the remaining sections. Section 4 covers robustness and weak robustness, including the idea of iterating these constructions, and relates them to Cayley color graphs. In section 5 we give a brief proof that the basis of region boundaries in a plane graph is robust. Section 6 shows how geodesic cycles can build all cycles through an iterative process. Sections 7 and 8 apply only to the hypercube. Geodesic cycles in the d-cube are given a simple characterization and then they are constructed from a recursively defined basis. Section 9 derives the application to commutative diagrams in groupoids and shows that a square which is the sum of two commutative squares can be non-commutative if the two squares added do not intersect in a nontrivial path. Finally, in Section 10, other types of cycle bases are considered. 2 Basic concepts In this paper, graphs are finite, undirected, and simple (i.e., no loops or parallel edges). For basic graph theory, see, e.g., [7], [1]. A connected graph is Eulerian if all of its vertex-degrees are even. For G a graph, V(G) and E(G) denote the sets of vertices and edges, respectively, and we also write G = (V, E). Every graph has a representation as a family of points and closed straight-line segments (corresponding to the vertices and edges, resp.) embedded in 3-dimensional Euclidean space; each segment in the representation joins the two points corresponding to the edge which the segment represents. There is a unique topology which induces the usual topology of a closed interval on the straight-line Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 29 segments, and this is called the underlying topology of the graph. A cycle is a graph which is 2-regular and connected. The underlying topology of a cycle is the unique closed connected 1-manifold, i.e., the circle. Let G be a graph and let Cyc(G) denote the set of all subgraphs of G which are cycles. A path is a graph which consists of a single vertex, or a connected graph which contains two vertices of degree 1 with every other vertex of degree 2. A nontrivial path is a path which contains more than one vertex. We write Pr for the path with r vertices. Let Z2 denote the field with 2 elements {0,1}; Z^ denotes the Z2-vector space of all functions from a set A to Z2; dimZ^ = |A|, the cardinality of A. Addition of functions is just coordinate-wise addition (modulo 2), so the zero element is the constant 0 function. To each function in ZA, one can associate the subset of A determined by those elements mapping to 1 and conversely for every subset of A, there is a unique element in ZA to which it is associated (the "characteristic function" of the set). The symmetric difference of two subsets of A corresponds to the vector space sum of the corresponding elements in ZA [1, p. 23]. If U is any subset of a vector space V, then span(U) is defined to be the intersection of all linear subspaces of V which contain U. Over the field Z2, the linear span of U is just the set of all sums of subsets of U; if U is empty, its span is 0. If G = ( V, E ) is a graph, there is a linear map dG : Zfc) ^ ZV2 (G) given by dG(e) = v + w when e = vw G E(G). The members of Z^0^ are called the 1-chains while members of ZV(G) are called 0-chains. The kernel (or "null space") Z(G) of the Z2-linear map dG is the subset of the 1-chains which map to the zero 0-chain. Thus, connected components of subgraphs of G induced by elements of Z(G) correspond to Eulerian subgraphs of G. By a theorem of Euler, H in Z(G) is an edge-disjoint union, hence sum, of cycles [1, p. 24], so Z(G) is the linear span of Cyc(G). So there is a basis for Z(G) consisting entirely of cycles, which is called a cycle basis. Addition in Z(G) is denoted +. One refers to the vector space Z(G) as the "cycle space" of the graph where the word "cycle" is used in the algebraic, rather than geometric, sense. The cyclomatic number b(G) of a graph G is the dimension of Z(G). It is well-known (and straightforward to show) that b(G) = q - p + k, where q,p, k denote the number of edges, vertices, and connected components of G. If G is connected, then for every spanning tree T of G, there is a basis B(G, T) which is the set of cycles ze formed by adding a single element e = vw in E(G) \ E(T). Indeed, as each pair v, w of distinct vertices in G are joined by a unique path in T, T + e has a unique cycle. Each of these cycles has an edge contained by no other cycle, so the set of cycles must be independent. But the cardinality of this independent set is maximal, for T contains p - 1 edges, so |B(G, T) | = q -p +1, and so it is a basis, the spanning tree basis, 3 Well-arranged sequences of cycles If z, z' G Cyc(G), we write z||z' and call z, z' compatible if z n z' = P, where P is a nontrivial path. This relation on the set of cycles is symmetric and irreflexive. For two compatible cycles z, z', the underlying topology of z + z' is the connected sum of the underlying topologies of the components, so z + z' must be a cycle as well. We 30 Ars Math. Contemp. 9 (2015) 93-107 give a direct argument avoiding the reference to connected sum after introducing a useful notation. If z is any cycle and P is a nontrivial path contained in z, then there is a unique nontrivial path P' also contained in z such that z = P U P' and P n P' = 2K (i.e., P and P' intersect in two isolated vertices). We write z - P for P'. Lemma 3.1. The sum of two compatible cycles is a cycle. Proof. Let z, z' be two cycles with z n z' = P a nontrivial path. Then z + z' = (z - P) U (z' - P). The paths z - P and z' - P intersect in the two endpoints of P, so their union is a cycle. □ Let z G Cyc(G); suppose S C Cyc(G) and span(S) = Z(G); e.g., S could be a cycle basis. A z-sequence in S is a sequence a = (s1, s2,..., sk) G Sk such that k z = s 1 + S2 +-----+ Sk = ^2 Si. i= 1 We do not insist that the entries in a need all be distinct. Of course, for every cycle z there are z-sequences in S with all members distinct since S spans every cycle, but in order to achieve further constraints on the sequence, it may be necessary to allow repetitions of members of the sequence. When there are no repetitions, it will be indicated. For a sequence a = (s1, s2,..., sk) G Sk, there are several notions of "well-arranged": a is well-arranged with respect to intersection (wai) if for each j, 2 < j < k, sj intersects the previous partial sum 1 si in a nontrivial path, that is, sj || ^j-1 s^ for 2 < j < k; a is well-arranged with respect to topology (wat) if each partial sum is a cycle; that is, if the partial sums are topologically constant. These are the only variants of well-arrangedness which we shall need below but for completeness we mention two more. a is well-arranged with respect to connectedness (wac) if each partial sum is connected; a is well-arranged with respect to degree (wad) if each partial sum is regular of degree 2. By Lemma 3.1, wai wat. However, the converse is false. Noncompatible cycles may sum to a cycle (see, e.g., the example at the end of section 6), so there can be z-sequences which are well-arranged with respect to topology but not with respect to intersection. Note that wat wac and wat wad trivially. Conversely, if wad holds for the z-sequence a, then a satisfies a weaker intersection condition that for each j, 2 < j < k, sj intersects the partial sum J2j-1 si in a subgraph with no isolated vertices. Further, this weak intersection condition, in turn, implies wad. 4 Robustness and weak robustness Let G be a graph and let S C Cyc(G). We define the robust closure p(S) (or weak robust closure pw (S)) of S with respect to G to be the set of all cycles in G which are the sum of a wai (resp., wat) sequence of elements in S. A set S of cycles is called robust (weakly robust) if p(S) = Cyc(G) (resp. pw (S) = Cyc(G)). Of course, a weakly robust (and Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 31 so also a robust) set of cycles is necessarily spanning: span(S) = Z(G). When S is a basis for Z(G), then every cycle can be written as the sum of a unique subset of the basis, with no element repeated. This non-repetition property of the sequence is not required for the definition of robust and weak robust closure. However, no examples are known where every wai (or wat) sequence which sums to some cycle z has repeated terms. Hierarchical iteration is achieved by taking the robust span of the set of cycles produced by the previous stage. Let p0(S) = S and, for integer a > 1, put pa(S) := p(pa-1(S)). Then pa (S) C pb(S) when a < b, for a, b nonnegative integers. Also, if S C T, then p(S) C p(T). We note the following for use in Section 9. Let T C Cyc(G) for some graph G. Call T cooperative if (z, z' G T and z||z') z + z' G T. According to Lemma 3.1, the set of all cycles is cooperative. From the definition of iterated robust closure and our remarks there, if G is any graph, one has the following. Lemma 4.1. If S C T C Cyc(G), T is cooperative, and k is a nonnegative integer, then pk(S) CT. Hierarchically iterated robust closure and the lemma above are applied in Cor. 9.3 to obtain results on the propagation of commutativity in general groupoid diagrams, especially when the diagram has the scheme of a hypercube. (Definitions are given there.) These results can be expressed in terms of Cayley color graphs [24]; see [16], [19], where the concept is used but not the name. Recall that the Cayley color graph of a group A with respect to a subset SCA is the digraph r(A, S) with A as its vertex-set, where for vertices v, w, there is an arc a = (v, w) if and only if there exists an element u G S such that w = v + u. (We write "+" as we are only considering the Abelian groups underlying vector spaces.) The arc a = (v,w) is colored by assigning to it the unique u satisfying the equation w = v + u, and so the Cayley color graph is the ordered pair consisting of the digraph and the corresponding arc colors. Let A be the abelian group determined by Z(G). Each element has order 2, so the Cayley color graph is symmetric and can be replaced by an undirected graph. To avoid loops, one assumes that the identity element of the group is not in the set S. Plainly, S is spanning if and only if r(A, S) is connected; see, e.g., [19, Lemma 3.3]. Let G be a graph, let S C Cyc(G) with span(S) = Z(G). Let rCyc(G, S) denote the subgraph of r(A, S) induced by Cyc(G) C A. Given two cycles z, z' in G there is a z'-z-path in rCyc(G, S) joining them if and only if there is a wat z-sequence a in S and such that z' = si. It is convenient to take z' to be the null-set of edges which is 0 in the vector space. The set of all cycles z reachable from 0 by such paths is exactly the weak robust span of S. The graph rCyc(A, S) is connected if and only if there is a rCyc(A, S)-path joining 0 to each z G Cyc(G), that is, if and only if S is weakly robust. The robust span of S is the set of all vertices in the connected component of 0 in the edge-induced subgraph r'Cyc(G, S) of rCyc(G, S) determined by those edges zz' where z||z'. In this case, the partial sums are successively modified by replacing a single subpath P with a complementary path P' = z — P, where P C z, for z some member of S. Instead of robustness or weak robustness, given any family S of cycles which spans Z(G), one might investigate the least number of connected components, the least maximum degree, or the least number of distinct topologies which occur along the rCyc(A, S) (or 32 Ars Math. Contemp. 9 (2015) 93-107 r'cyc(A, S)) paths from 0 to z, maximized or totaled over all cycles z in G. One may also focus only on some cycles which need to be built up. See [15] for an application to random networks and also Proposition 10.1 below. 5 Planarity and robustness For plane graphs, we find a robust basis; cf. [3]. In the following, we do not distinguish between subgraphs of a plane graph and the corresponding subsets of the plane. Let G be a 2-connected plane graph. To prevent pathological embeddings, assume that each edge of G is embedded as a piecewise-linear curve (with a finite number of segments). Then R2 \ G is a disjoint union of open disks and, using the 2-connectedness of the graph, the closure of each open disk is a closed disk and the boundary of each closed disk is a cycle. Each plane graph contains exactly one unbounded region, containing points which are arbitrarily far from any point of the graph; all the other regions are called bounded. See, e.g., [1, Chap. 4]. Let R(G) denote the set of all bounded regions. Then B(G) := {dr : r G R(G)} is a basis of the cycle space of G . It is spanning since if z G Cyc(G), then z = J2 dr, summing over all regions r contained within z. By Euler's Formula, the number of all regions is equal to q - p + 2, so |B(G) | = b(G) and hence B(G) is a cycle basis. The interior rnt(P) of a nontrivial path P is the path minus its two endpoints. A topological path is any curve which is homeomorphic to the closed unit interval [0,1]. A subset of the plane is topologically path-connected if any two of its points can be joined by a topological path which is the union of a finite number of straight line segments. Lemma 5.1. For any 2-connected plane graph G and z G Cyc(G), either z = dr for some r G R(G) or there exists r G R(G) such that z n dr is a nontrivial path. Proof. Assume z = dr for all r G R(G). Then dr n z is a disjoint union of paths, some of which can consist of an isolated vertex. Let Ri, R2 denote the sets of regions r in R(G) which are contained within z and for which H = dr n z has at most 1, resp. at least 2, connected components. If R2 is empty, then for each edge e in z, the unique region r whose intersection with z includes e must satisfy dr n z is a nontrivial path. Suppose R2 is nonempty. If P is any path subgraph of z joining two successive components of z n dr, then r separates the interior of P from the interior of z - P in the sense that any topological path in the plane joining apointin int(P) to a point in int(z-P) must intersect dr. See [1, Lemma 4.1.2] for a formal proof. Let P* be a path subgraph of z joining two successive components and of minimum possible length. Then for any edge e in P*, there exists a unique region r' for which e G E(z n dr'). If z n dr' is not contained in P*, then the path-connected set r' would allow a topological path between some point in the interior of P* and some point in the interior of z - P*. But this is impossible by our remark about the separating property of r. Hence, z n dr' C P * .By minimality of P *, r' must intersect z in a single component. Since the intersection contains an edge, it is a nontrivial path. □ Theorem 5.2. The basis R(G) of a 2-connected plane graph G is a robust basis; in fact, each cycle is the sum of a wai sequence with no repeated elements. Proof. Let t be the number of regions contained in z; we prove the result by induction on t. For the basis case, t = 1 and the wai sequence has the single term z. If t > 1, then by Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 33 Lemma 5.1, there is a region r in R(G) contained in z such that dr n z is a nontrivial path. Hence, zZ = z + dr e Cyc(G) and z' contains every region contained in z except for r. By the induction hypothesis, there is an ordering of the regions contained in z' so that z' = dri + dr2 +-----+ drt—1 and the sequence (dri,..., drt—i) is well-arranged w.r.t. intersection. Therefore, concatenating one more term, dr, gives the desired wai sequence of members of R(G). □ 6 Geodesic cycles can build all cycles If z is any cycle (or path), let l(z) := length(z) denote the number of edges. The girth g = g(G) of a graph G is the length of a shortest cycle [1, p. 8]. A subgraph H C G is geodesic (or isometric) if for all v, w vertices of H, distH (v, w) = disto (v, w), where for a,b e V(H), distH(a, b) is the distance from vertex a to vertex b in H - i.e., the length of a shortest a-b-path in H (and similarly for G). In K4, any 3-cycle is geodesic but any 4-cycle is not geodesic. It is clear that a cycle of minimum length is necessarily geodesic, so geodesic cycles always exist in any non-forest. The length of a geodesic cycle can't exceed twice the diameter by more than 1 as is shown in [1, proof of Prop. 1.3.2]. Hence, in a bipartite graph, every geodesic cycle has length at most twice the diameter. Let Geo(G) denote the set of geodesic cycles. We now show that for all graphs G, every cycle belongs to an iterated robust span of the geodesic cycles and bound the number of iterations needed; cf. [4]. Theorem 6.1. For every graph G and every z e Cyc(G), one has z e pe(z^—s(o)(Geo(G)) (6.1) Proof. Suppose G is a fixed arbitrary graph and z is any cycle of G. We write k = k(G, z) = i(z) — g(G). The statement of the theorem holds when k = 0 since then the cycle must be of minimum length, hence geodesic, and so in p0(Geo(G)). Suppose the theorem holds when k(G,z) < n, where n is some positive integer and let z be a cycle of G with length n + g(G) (i.e., so that k(G, z) = n). If z is not a geodesic cycle, there exist non-adjacent vertices v, w in z and a v-w-path P in G, intersecting z in exactly the two vertices v, w (and no edges) such that the length of P is less than the distance between v and w in z. Let P1,P2 be the two disjoint v-w-paths in z and put z4 = P U Pi, i = 1, 2. Since (z1, z2) is a wai sequence with sum z, z e p({z1 ,z2}). But both z1 and z2 are strictly shorter than z so by the inductive hypothesis, z1,z2 e pk (Geo(G)), where k' = max{£(z1), i(z2)} — g(G) < k — 1. Therefore, we have z in p1+k (Geo(G)) C pk (Geo(G)) which completes the induction. □ Let c(G) denote the circumference of G, which is the length of a longest cycle. Corollary 6.2. For every graph G, Cyc(G) C p 2, such that $(w) = a * a, (7.1) where a is a string which is a permutation of the elements of S. Proof. Let z be any geodesic cycle in Qd. Then for any two diametrically opposite vertices v, w of z, the two distinct v-w-paths P, P' contained in z must both be geodesic paths. Let t be the closed walk P' followed by Pop. By the remark above, both P and P' correspond to permutations of sets S, S', resp. But S = S' as the walk is closed. Hence, any r in [d] appears either twice or not at all in the string $(t). If the two appearances of some r G [d] were not at diametrically opposite edges e, e' of z, then there exist diametrically opposite vertices v', w' G V(z) such that both e and e' are contained in one of the two geodesic paths in z which is impossible. Conversely, for a walk of length 2j satisfying the permutation condition, any subpath of length < j corresponds to a permutation and is geodesic so the cycle is also geodesic. □ 8 Building geodesic cycles in the hypercube Since Qd is bipartite, shortest cycles have length > 4. For distinct i, j in [d], the closed walk w = (v, v + Mj, v + ui + uj, v + Uj, v) is a 4-cycle and $(w) = (i, j, i, j). Moreover, any 4-cycle, being geodesic, must be of this form. Call 4-cycles squares and let Sq(Qd) be the set of all squares in Qd. For convenience, during this section we shall write ij for any square s such that $(s) = (i, j, i, j), for distinct i, j G [d]. We will use the notion of a strip of squares in some graph G. This is a sequence a = (si, S2,.. ., sfc), (8.1) where each sj is a distinct 4-cycle subgraph of G, no two squares intersect unless one is the successor of the other, and for 2 < j < k - 1, sj intersects its predecessor sj_1 and its successor sj+1 in disjoint, that is, opposite, edges. The length of a strip of squares is the number of squares in the sequence. If the length of a strip of squares a as in (8.1) is k > 2, then we call the strip nontrivial. For a nontrivial strip there are distinguished start and stop edges for a: the start edge is the edge of s1 opposite to the edge s1 n s2, and the stop edge is the edge of sk opposite to the edge sk-1 n sk. The ties of a nontrivial strip of squares is the set consisting of the start and stop edges, together with all intersection edges sj n sj+1, 1 < j < k - 1. Let G(a) := U k=1 sj denote the graph determined by the strip of squares. A strip of length 1 has graph which is a 4-cycle and so is isomorphic to Q1 x P2. The following results can be easily proved by induction on k. Lemma 8.1. Let a be a strip of squares of length k > 2. Then (i) G(a) is isomorphic to Q1 x Pk+1, (ii) the ties of a correspond to the edges Q1 x v for v G V (Pk+1), and (iii) the squares s1,..., sk are a robust basis of G(a). Lemma 8.2. In a hypercube, all ties of a strip of squares have the same active coordinate. 36 Ars Math. Contemp. 9 (2015) 93-107 In the following, assume that d > 3, else everything is trivial. For 1 < j < d, define strips aj in Qd as follows. Let s2 be the unique 12 square which contains 0, put aj = s2, and let [u2, u2 + u] be the "stop edge" of s2. For 2 < j < d, having defined aj-1 let j j—1 aj := aj * sj, where sj is the unique 1j square through the vertex u2 + • • • + uj-1. Let zj be the sum of the squares in aj. that is, zj := S2 +-----+ sj. We prove by induction on j that $(zj ) = (1,...,j, 1,j,j - 1,..., 2). (8.2) For j = 2 the result holds and for 2 < j < d - 1, adding sj+1 to zj replaces the stop edge of aj with a sequence of three edges active consecutively in coordinates j + 1,1, j + 1. Thus, $(zj+1) = $(zj + Sj+i) = (1,...,j + 1,1,j + 1,j,j - 1,..., 2), establishing the induction. Let a1 = ad and put z1 := zd. Then $(z1) = (1, 2,..., d, 1, d, d - 1,..., 3, 2). Thus, z1 is the union of two paths P, P1 from 0 to I, where $(P) = (1, 2,..., d) and $(P1) = (2,..., d, 1). Hence, z1 is a cycle of length 2d, but it is not geodesic since the intersection edges of a1 join non-adjacent vertices of z1. We now show that every geodesic cycle in Qd is in the robust span of the set of squares by continuing the above construction. Theorem 8.3. Let z be any geodesic cycle of length 2j in Qd, d > 3. Then there exists a wai z-sequence of distinct squares z1, z2,..., zm, where m = j (j - 1)/2. So z G p(Sq(Qd)). Proof. By the homogeneity of Qd, it suffices to show that, for each positive integer d > 3, the unique geodesic cycle z in Qd through 0 with $(z) = (1,2,..., d, 1, 2,..., d) is the sum of a sequence a of squares which is well-arranged w.r.t. intersection. For 1 < j < d - 1, let aj denote a sequence of squares of length d - j of the form aj := (j j + 1 j j + 2,..., j d); put a := a1 * a2 * • • • * ad-1, the concatenation. Each aj is a strip of squares, the strips are disjoint in the sense that no square belongs to more than one, and every square does belong to a strip. We will show that this sequence of squares is wai and has sum z. In the sequel, as we add squares to z1 = P U P^ the path P will be unchanged while the path P1 will be successively transformed, but without changing its length. The sequence a2 = (s23, s24,..., s2d) is defined as follows. Let s23 be the unique 23 square which includes the vertex note that s23 intersects P1 in the path P1,23 = (0,U2,U2 + U3) Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 37 which are the first two edges of Pi. Adding s23 to z1 produces a new cycle z1j23 which is the union of P and the path P1j23 obtained by replacing (0, u2, u2 + u3) by (0, «3, u2 + «3) in P1. Now there is a unique 24 square s24 which includes the vertex u3, and s24 intersects P1j23 in the path P1,24 = («3, «2 + «3, «2 + «3 + «4) which constitutes the second and third edges of P1j23. Put z1j24 = z1j23 + s24. Then z1j24 = P U P1j24, where 4 5 d d P1,24 = (0, «3, «3 + «4, ^ «j , . . . , ). j=2 j = 2 j=2 j=1 Now there is a unique 25 square through the vertex «3 + «4 intersecting P1j24 in its third and fourth edges, and so forth up to 2d. Adding the sum z'2 of the squares in a2 to z1 produces $(z2) = $(z1 + z2) = (1, 2, .. ., d, 1, 2, d, d - 1, .. ., 3). Proceeding in this fashion, z = zd, $(z) = (1,..., d, 1,..., d), and a is a wai z-sequence as each square after those in the initial subsequence a1 intersects the sum of the preceding squares in a path of length 2. □ Thus, the set Sq(Qd) of all squares in Qd robustly spans the set Geo(Qd) of all geodesic cycles in Qd, Geo(Qd) C p(Sq(Qd)). But Sq(Qd) contains d(d - 1)2d-3 squares, which is asymptotically d/4 times the size of a cycle basis. Indeed, b(Qd) = 1 + d2d-1 - 2d = 1 + (d - 2)2d-1; e.g., [7, pp 22-23, 38-39]. In the graph Q1 x G, as V(Q1) = {0,1}, G is isomorphic to 0 x G under the mapping v ^ (0, v), and we write 0 x H for the image under this isomorphism of a subgraph H of G in 0 x G and similarly for 1 x H. Also, if e G E(G), we write e for the corresponding subgraph (which is isomorphic to Q1), and for e G E(G), each subgraph Q1 x e in Q1 x G is a 4-cycle. We shall use the decomposition E(Qd) = E(Qd) U E(Qd) U Ed, (8.3) where Q0 = 0 x Qd-1 and Qd = 1 x Qd-1 denote the "bottom" and "top" subgraphs of the d-cube, Ed := E(Qd) \ (E(Q0) U E(Qd)) denotes the "side" edges of the d-cube. Similarly, there is a decomposition of the squares Sq(Qd) = S0 U S1 U Sqd, (8.4) 38 Ars Math. Contemp. 9 (2015) 93-107 where Sj := Sq(Qd) for j = 0,1 and Sqd = Sq(Qd) \ (So U Si) (the set of all "side" squares of Qd). Each element s in Sqd is the product of Q1 with the unique edge e in E(Qd-1) corresponding to the intersection of s with Qd. Now we can define the Kainen basis of Qd [12]. Let BK (Qd) be the following recursively given collection of squares in Qd. For d = 0 and d = 1, the set is empty, and Bk(Q2) = {Q2}. Having defined Bk(Qd-1) for d > 3, put Bk(Qd):= Bk(Qd) U Sqd, (8.5) where BK(Qd) is the cycle basis of Qd corresponding to BK(Qd-1) under the natural isomorphism. For example, BK (Q4) consists of five squares in one of the 3-cube faces and all twelve side-squares. Lemma 8.4. The set BK (Qd) is a cycle basis for Qd for d > 2. Proof. By induction on d; trivial for d = 2. Now let d > 3. Then BK (Qd) is independent since by induction the squares in BK(Qd) in the decomposition (8.5) are independent, while the squares in the sides, Sqd, are independent of those in the bottom and also of each other as each contains a unique edge in Qd-1. But BK (Qd) has the cardinality of a basis (and so is a basis). Indeed, using (8.5), we have |Bk (Qd)| = |Bk (Qd-1))| + |E (Qd-1)| = 1 + (d-3)2d-2 + (d-1)2d-2 = 1+(d-2)2d-1, where the second equality again uses the inductive assumption that BK(Qd-1) is a basis. □ We now show that this basis is sufficient to robustly span every square in Qd. Theorem 8.5. For d > 2, Sq(Qd) C p(Bk(Qd)). Proof. As before, the basis case d = 2 is trivial. Every square in Qd which is on the bottom is in p(BK(Qd-1)) by the induction hypothesis and p(BK(Qd-1)) C p(BK(Qd)) and the side-squares are in BK (Qd) by definition. Thus, we only need to take care of the squares s on the top; that is, s G S1 = Sq(Qd). Each such square is contained in a unique subgraph Q3 of Qd such that s = Q1,. Let s' = Q3. Then s' G Sq(Qd) so by induction there exists a' a wai s'-sequence in BK (Qd-1) C BK (Qd), and we may append to this sequence the 4 side-squares of Q3 (in any order) to produce a wai sequence in BK(Qd) which sums to s. □ Using Theorem 6.1, we see that for hypercubes every cycle is in the iterated robust closure of BK (Qd). Corollary 8.6. For d > 2 and z any cycle in Qd, z G p£(z)-2(BK(Qd)). 9 Application to commutativity in groupoids The original motivation for building up cycles using wai sequences was to show that the commutativity of certain diagrams in a groupoid category can be inferred from the commutativity of a small minority of the faces of the diagram [13]. After defining these terms, we use the results of the previous sections of this paper to prove the above claim and we show that a similar inference cannot be made using only wat sequences. Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 39 For a full discussion of the concept of a category, see, e.g., Mac Lane [17]. Briefly, a (small) category C consists of a set Obj(C) of objects, a set Mor(C) of morphisms, and two functions ("domain" and "co-domain") dom, cod : Mor(C) ^ Obj(C). (A morphism thus models the notion of a structure-preserving function between two mathematical objects.) An ordered pair (a, b) of morphisms is called composable if dom(b) = cod(a). In addition, C is required to have a law of composition which is a function from the set of composable morphism pairs to the set of morphisms denoted by (a, b) ^ ab, where dom(ab) = dom(a) and cod(ab) = cod(b). Often the notation for composition is in reverse order, emulating composition of functions. It is convenient to write C(x, y) for the set of all morphisms in C with domain x and co-domain y, and a : x ^ y is another notation for a G C(x,y) Typically, the set of morphisms between a given pair of objects has many elements but this set can also be empty or a singleton. For any triple x, y, z of objects of C the law of composition gives a function C(x, y) x C(y, z) ^ C(x, z). Composition in a category C must be associative: if (a, b) and (b, c) are composable pairs of morphisms in C, then (ab, c) and (a, bc) are both composable pairs and we require (ab)c = a(bc). It follows by induction that one can define a unique composition a\a2 • • • ak for any finite sequence (a1,a2,... ,ak) of morphisms for which each successive pair (ai, ai+i) is composable. The final condition in the definition of a category C is that for each object x, there is an identity morphism lx G C(x, x) such that if x, y are any two objects in C, then for any morphism a in C(x, y), aly = a = lxa. Typical examples of a category are a set of topological spaces and continuous maps, or a set of vector spaces and linear maps, etc., provided that the composition of any two morphisms remains in the set, and of course that the identity morphisms are included. A directed multigraph D = (V, A, is a set V of vertices, a set A of arcs, and a mapping ^ : A ^ V x V which associates to each arc an ordered pair (v, w), where v is its source and w its target. Arc-pairs (a, a') are composable if the target of a is the source of a' and an arc sequence is a dipath if each successive pair is composable. A v-w-dipath is a dipath where the first arc has source v and the last arc has target w. A diagram S in a category C is a directed multigraph D = (V, A, (called the scheme) and functions fv, fA such that fv : V ^ obj(C), ¡a : A ^ mor(C) such that if ^(a) = (v,w) and fv(v) = x,fv(w) = y, then fA(a) G C(x,y). Unless necessary, we shall not distinguish between vertices of the diagram and objects of the category, nor between arcs and morphisms. A dipath in the diagram corresponds to a composable sequence of morphisms in the category. A face of the diagram is a distinct pair of v-w-dipaths, for some objects v, w, and this face is commutative if the two paths give rise to the same v-w-morphism, using the law of composition in the category. The face is said to "commute." The diagram is commutative if all of its faces commute. 40 Ars Math. Contemp. 9 (2015) 93-107 The importance of commutative diagrams is that they can be used to define certain algebraic properties, such as co-associativity, and a basic theory of algebraic syntax can be built up from commutative diagrams - see, e.g., [18] and [5]. For an explicit recent example from computer science, see [21, p. 13, diagram for Remark 1.2.6]. A groupoid is a category G in which every morphism is invertible; i.e., for every mor-phism a, there is a unique morphism a-1 such that composition in either order gives 1. Groupoids are generalizations of ordinary groups and they have become of some interest in a number of fields recently, spreading far from initial applications in topology; see, e.g., [23]. A diagram in a groupoid G can be extended by including for every arc a in the diagram a reverse arc aop and if the morphism a is assigned to a then in the extended diagram, the inverse morphism a-1 is assigned to aop. If the original diagram commutes, then so does the extended diagram and the reverse implication is trivial. Hence, we shall assume that all diagrams in a groupoid category are symmetric. Any undirected cycle in a groupoid diagram can be parsed into a closed walk by choosing one of the vertices and then proceeding either clockwise or counterclockwise. The cycle is said to g-commute if the composition along the walk is the identity; this does not depend on how the cycle is parsed; e.g., if abc = 1, then 1 = a-11a = bca, etc. A diagram in a groupoid category will be called g-commutative if and only if all of its cycles g-commute. Lemma 9.1. If a groupoid diagram is g-commutative, then it is commutative. Proof. Suppose we have a g-commutative diagram. Let P, Q be two directed paths from v to w in the diagram and let a, ft be the morphisms induced by P and Q, resp. It suffices to assume P and Q intersect only in v and w. Let z be the cycle formed by the union of P and Q, parsed to begin at v, follow P, and then Q (in reverse order). Then z induces aft-1. So the morphism induced by z is 1 if and only if a = ft. Thus, g-commutativity implies ordinary commutativity. □ The converse is false. For example, one can have four objects w, x, y, z with morphisms f : w ^ x, g : y ^ x, h : y ^ z, i : w ^ z. The corresponding diagram is automatically commutative because it has no faces but if it is in a groupoid it is g-commutative only if fg~1hi~1 = 1, i.e., fg-1 = ih-1. Proposition 9.2. The g-commutative cycles in a groupoid diagram form a cooperative set. Proof. Let z, z' be commutative cycles in a groupoid diagram, with P = z n z' a nontrivial path from v to w. Let a be composition along P, ß along z — P, and ß' along z' — P. Then aß = 1v and aß ' = 1v But also ß-1a-1 = 1v. Hence, 1v = ß-1a-1aß' = ß-1ß'. Thus, z + z', which is the cycle (z — P) U (z' — P) is commutative. □ Using Lemma 4.1 and Proposition 9.2, by Theorem 6.1 and Corollary 8.6, we get: Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 41 Corollary 9.3. A diagram in a groupoid is g-commutative if its geodesic cycles g-commute. A Qd-diagram in a groupoid is g-commutative if each z G BK (Qd) g-commutes. The sum of two commutative cycles can be a noncommutative cycle when the cycles intersect in more than one nontrivial path. Label the vertices of a complete graph on 4 vertices A, B, C, D in clockwise order, where all vertices correspond to a single object X in the groupoid, and take all morphisms to be 1X, except for the two diagonal arcs from C to A and from D to B, respectively, which represent some morphism x : X ^ X, where x2 = 1X. (This is a mild condition on the groupoid, satisfied for instance by the symmetric group Sn for n > 3.) Consider the two squares A, B, C, D and A, B, D, C; going around the first square gives a 4-fold composition of identities, while the second square gives x O 1x O x-1 O 1x = 1x . The two squares intersect in edges AB and CD and the sum of the two squares is the square A, D, B, C which induces the morphism x2 = 1X. Thus, propagation of commutativity to the sum can fail when cycles intersect in two disjoint paths. 10 Remarks This section is essentially an appendix which compares other types of cycle basis to the one we have constructed. We thank one of the referees for suggesting some of the references given here and for other helpful comments. A general method for generating cycle bases for Cartesian product graphs, was described by Hammack [6]. It constructs a cycle basis for G x G' for each pair of graphs G, G' with given spanning trees T, T' and cycle bases B, B' for G, G', resp. Then there is a Hammack basis Bh(G, B, T, G', B', T') := F U G U G', where F := {e x e' : e G E(T), e' G E(T')}, G := {z x y : z G B, y G V(G')}, G' := {x x z' : x G V(G),z' G B'}. For the hypercube Qd, it is reasonable to take G = Qd-1 and G' = Q1. So T' = Q1 but T could be an arbitrary spanning tree of Qd-1. There is a natural recursive choice for T a spanning tree of Qd-1 when d > 3: just keep adding in all of the "side" edges. For example, the spanning tree constructed for Q3 looks like a "U" standing on 4 legs. If d > 4, the Hammack bases (allowing all possible spanning trees) do not include the Kainen basis since the latter uses only bottom squares, but all (d - 1)2d-2 side-squares, while the former type use both top and bottom squares but only 2d-1 - 1 side squares. For example, Bh (Q4) will have 5 squares in both Q4 and Q4 but only 7 side-squares (cf. supra Lemma 8.4). Other iterated Cartesian product graphs have been explicitly studied, e.g., in [9]. Minimum cycle bases (in the sense of having minimum total sum of the lengths of their members) for Cartesian product graphs were constructed by Imrich and Stadler [11]. Like the Hammack bases, these depend on a spanning tree and a cycle basis, and also a vertex, for each factor of a Cartesian product. The Imrich-Stadler basis for G x G' has the form Bis(G, B, T, x, G', B', T', y) := Bn U Gy U GX, 42 Ars Math. Contemp. 9 (2015) 93-107 where B, T, x (B', T', y) are cycle basis, spanning tree, and vertex for G (and for G', resp.), and Bn := {e x e' : e G E(T), e' G E(G')} U {e x e' : e G E(G), e' G E(T')}, Gy := {z x y : z G B}, GX := {x x z' : z' G B'}. If G' = T', then Bn = {e x e' : e G E(G),e' G E(T')} and GX is empty. So BIS(G x T') doesn't depend on T or x. When G = Qd-1 and T = Q1, this is just Bk (Qd) so BIS is a generalization of BK. When the cycle bases of G and G' are minimal and both G and G' have girth at least 4, [11, Thm. 8] shows that BIS(G x G') is minimal as well. When G' is a tree, we can get a robustness-related result. In the graph G x T, T a tree, a cycle z contained in a subgraph G x v' for some v' G V(T) is called a level cycle. Proposition 10.1. Let G be a graph with spanning tree T, cycle-basis B, and v0 G V(G). If B is robust, then every level-cycle in T x G is in the robust span of the basis B' B' := {v0 x z : z G B} U {e' x e : e' G E(T), e G E(G)}. Proof. Suppose that T has t vertices and G has p vertices and q edges. Then it is easy to calculate that b(T x G) = qt - p + 1 = |B'| and B' is a basis by [11, Thm. 4]. We prove the robustness claim by induction on the number t of vertices of T. When t =1, B' = B so the result holds. Let T be any tree with t vertices, t > 1. Then there is a vertex v in T such that v has degree 1. Let T' = T - v. Now consider any level cycle z' in T x G. If z' is in w x G for some w G V(T'), then by the induction hypothesis, there is a z'-sequence from B' which is wai. Otherwise, if z' is contained in v x G, then z' = v x z for some z G Cyc(G). Let v' be the unique vertex of T which is adjacent to v. For the cycle z'' = v' x z, there is a z''-sequence a' from B' which is wai. If the edges in z are followed in a closed walk, say e1 , . . . , ek and if e = vv', then a = a' * (e x e1, .. ., e x ek) is a wai sequence from B' which sums to z'. □ Recently, convex cycle bases were studied in [8]. A subgraph H of G is convex if for every minimal-length G-path P between vertices v,w G V(H), P is a subgraph of H. In a hypercube, squares are convex subgraphs. The Imrich-Stadler basis for G x H is convex when the bases for G and H are convex. They note that the only convex cycles in a hypercube are the squares. Geodesic cycles in the hypercubes are a special case of planar partial cube and the latter have been characterized in [20]. References [1] R. Diestel, Graph Theory, Springer, Berlin, 2005. [2] E. T. Dixon and S. E. Goodman, An algorithm for the longest cycle problem, Networks 6(2) (1976), 139-149. [3] U. Dogrusoz and N. Krishnamoorthy, Enumerating all cycles of a planar graph, Parallel Algorithms and Applications 10 (1996), 21-36. Paul C. Kainen: Cycle construction and geodesic cycles with application to the hypercube 43 [4] A. Georgakopoulos and P. Sprüssel, Geodetic topological cycles in locally finite graphs, The Electronic Journal of Combinatorics 16 (2009), #R144 (18 pages). [5] J. A. Goguen, A categorical manifesto, in Mathematical Structures in Computer Science 1 (1991), 49-67; http://www.cs.ox.ac.uk/files/3395/PRG72.pdf [6] R. Hammack, Cyclicity of graphs, Journal of Graph Theory 32(2) (1999), 160-170. [7] F. Harary, F., Graph Theory, Addison-Wesley, Reading, MA, 1970. [8] M. Hellmuth, J. Leydold and P. F. Stadler, Convex cycle bases, Ars Math. Contem. 7(2014), 123-140. [9] W. Imrich and S. Klavzar, Product Graphs: Structure and Recognition, Wiley, New York, 2000. [10] W. Imrich, S. KlavZar, and D. F. Rall, Graphs and Their Cartesian Product, A. K. Peters, Wellesley, MA, 2008. [11] W. Imrich and P. F. Stadler, Minimal cycle bases of product graphs, Australasian J. of Combinatorics 26 (2002) 233-244. [12] P. C. Kainen, On robust cycle bases, Proc. 9th Quadr. Conf. in Graph Theory, June 2000, Y. Alavi et al., Ed., in Electr. Notes in Discr. Math. 11 (2002), 430-437 (art. 38, pp. 1-8). [13] P. C. Kainen, Isolated squares in hypercubes and robustness of commutativity, Cahiers de Topologie et Géométrie Différentielle Catégoriques XLIII (2002), 213-220. [14] P. C. Kainen, Graph cycles and diagram commutativity, pp. 177-238, in Diagrammes, Sup-plem. aux vol. 67+68, Paris, 2012. [15] K. Klemm and P. F. Stadler, Statistics of cycles in large networks, Phys. Rev. E 73 (2006) 025101. [16] K. Klemm and P. F. Stadler, A note on fundamental, non-fundamental, and robust cycle bases, Discrete Applied Mathematics 157 (2009), 2432-2438. [17] S. Mac Lane, Categories for the working mathematician, Springer, New York, 1971 [18] F. Orejas, On the representation of data types, in Formalization of Programming Concepts, Lecture Notes in Computer Science, Vol. 107, 1981, 419-431. [19] P-J Ostermeier, M. Hellmuth, K. Klemm, J. Leydold and P. F. Stadler, A note on quasi-robust cycle bases, Ars Mathematica Contemporanea 2 (2009), 231-240. [20] I. Peterin, A characterization of planar partial cubes, Discrete Math. 308(2008), 6596-6609. [21] B. C. Pierce, Basic Category Theory for Computer Scientists, MIT Press, 1991. [22] M. M. Syslo, On cycle bases of a graph, Networks 9 (1979), 123-132. [23] A. Weinstein, Groupoids: Unifying Internal and External Symmetry, Notices Amer. Math. Soc. 43 (1996), 744-752. [24] A. White, Graphs of Groups on Surfaces, Mathematics Studies 188, North-Holland, Amsterdam, 2001.