D IAGRAMMES PAUL C. K AINEN Graph cycles and diagram commutativity Diagrammes, tome S67-68 (2012), p. 177-237 © Université Paris 7, UER math., 2012, tous droits réservés. L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ DIAGRAMMES , SUPPLEMENT AUX VOLUMES 67 + 68 , 2012, PARIS, pp. 177-238 GRAPH CYCLES AND DIAGRAM COMMUTATIVITY P. KAINEN EDITE PAR L. COPPEY , F. FOLTZ , R. GUITART, C. HENRY , C. LAIR 179 Graph cycles and diagram commutativity Paul C. Kainen Department of Mathematics and Statistics Georgetown University Washington, D.C. 20057-1233, USA Abstract Bases are exhibited for Kn , Kp,q , and Qd , and it is shown how each cycle of the various graphs can be built as a hierarchical ordered sum in which all of the partial sums are (simple) cycles with each cycle from either the basis or one of the hierarchically constructed cycle-sets meeting the partial sum of its predecessors in a nontrivial path. A property that holds for this “connected sum” of two cycles whenever it holds for both the parents is called constructable. It is shown that any constructable property holding for the specified basis cycles holds for every cycle in the graph, that commutativity is a constructable property of cycles in a groupoid diagram, and that “economies of scale” apply to ensuring commutativity for diagrams of the above three types. A procedure is given to extend a commutative groupoid diagram for any digraph that contains the diagram’s scheme. Keywords. Robust basis, well-arranged sum, blocking number, groupoid. 1 180 Preface The intended readership of this paper are category-theorists and systemsbiologists with an interest in the work of Professor Andrée Ehresmann. However, the main tool turns out to be topological graph theory; graph theorists can skip to sections 5 through 8, where constructions are given in which a cycle may be seen as being built up (“growing” in a sense) through the successive attachments of new cycles along a common nontrivial path. After developing this first portion, we proceed to the case of directed graphs and graph embeddings of various types including as diagram schemes in a category. Finally, there is an application to commutativity of diagrams, and this is the pay-off for our typical reader. Accordingly, such a reader may wish to first go to sections 10 through 19, going back to the preceding sections as needed to follow the arguments. To describe biological form and function, we suggested in [16] that all the branches of mathematics and perhaps some new ones will be required. The present work uses algebra, combinatorics, and topology, and provides insight into the notion of cycle. Present in so many aspects of biology, from circadian rhythms, to the cell-cycle, to population growth and decline, the treatment of cycles should be keystone for biological theory; see [13]. Broad-brush, any notion of biological action should incorporate a flexible but powerful notion of cycle, which addresses the problem of freedom vs. constraint. The connection of this work with that of Professor A. C. Ehresmann is through its utilization of hierarchical constructions and its potential application to error-control for the elaborate diagrammatic schema required for higher category theory and biological networks. An early version of these ideas [15] was presented at a conference in Amiens. 2 181 Our theory proposes that the sort of dynamic, symbol-bearing graphs described in the Ehresmann-Vanbremeersch theory can be structured so that their cycles evolve through a finite, hierarchical process. At each stage, a cycle meets the partial sum of its predecessors in a nontrivial path so under mod-2 addition, the repeated path disappears and each partial sum constitutes a cycle. In this direction, building up (or “composition”), the process is deterministic. However, in the reverse direction, a single cycle can develop a cross-path connecting two of its non-adjacent vertices by a path whose internal vertices are disjoint from the cycle. Thereby the original cycle can split into two cycles in many possible ways. Thus, cycles already contain features of biological flavor. Moreover, if two cycles have some nice property and meet in a common nontrivial path, then their sum is also nice. Nice properties turn out to include: bounding a disk if the graph is embedded in a surface, being unknotted if the graph is embedded in 3-space, or having composite value 1 if the graph has a diagram in some groupoid. The latter application is the one which will be expanded upon in this study. To help convince a skeptical reader that graph theory might be of value for biology, let me mention a simple example that uses geometrical information about a graph G to predict the complexity of its complement (or “anti-graph”) Ḡ. As each distinct unordered pair of vertices is either in the graph or the ¯ = G, so a gain for the graph is a loss for the complement and anti-graph, Ḡ vice-versa. We shall show that if G contains two non-adjacent vertices with no common neighbor, then Ḡ is connected; this is (*) below. Thus, if G wants to keep Ḡ disconnected, then G should avoid having such a pair of vertices. (Avoiding such a pair is a necessary condition for keeping the complement 3 182 disconnected but it is not always sufficient.) For the argument, define distance in a graph as the length of a shortest path joining two vertices, with value +∞ if no path joins them - i.e., if the points chosen belong to different connected components of the graph. Let diam(G) denote the greatest distance occurring between all possible pairs of vertices of G, the worst-case distance one might need to travel to go from one vertex of the graph to another. So diam(G) = ∞ iff G is not connected. We claim that diam(G) ≥ 3 =⇒ Ḡ is connected. (∗) First, note that the following holds: (G not connected) =⇒ (Ḡ has diameter ≤ 2.) (∗∗) Indeed, if two vertices lie in different connected components of G, then all edges joining vertices of the two components fail to exist in G (else the components wouldn’t be distinct), so the two vertices chosen are adjacent in Ḡ. Otherwise, the two vertices both belong to one of the components of G and since G isn’t connected, there is another vertex in a different component to which each of the chosen pair is adjacent in Ḡ. Now the result (*) follows by the logical jiu-jitsu of contraposition (If P , then Q; so if not Q, then not P ) applied to (**) with G and Ḡ interchanged. While diam(G) = 1 iff every distinct pair of vertices are adjacent, diam(G) = 2 is already nontrivial; see, e.g., [7]. This simple example illustrates how certain natural propensities of the networks themselves might allow qualitative emergence of new properties in a fashion which the organism could exploit. 4 183 1 Introduction A diagram is said to commute when the morphisms produced by composing the arrows along any two parallel paths are the same, where (directed) paths are “parallel” if they begin and end at common nodes. It is of interest to know when commutativity of the entire diagram follows from that of some of its parts. Since various mathematical properties can be described via commutative diagrams, the extension of commutativity could provide statistical reliability in the determination of such properties. Commutativity is an algebraic constraint but it is expressed within the combinatorial context of the underlying diagram scheme, which is a directed graph. Hence, it is not surprising that combinatorial arguments yield conditions which force or block commutativity. Previously, we found such conditions when the scheme is that of a d-dimensional hypercube (or more briefly, d-cube). In addition, the arguments required that the category in which the diagram appears has all of its morphisms invertible - i.e., it is a groupoid. In [14] commutativity of a d-cube diagram in a groupoid was shown to be guaranteed (i.e., “forced ”) by the commutativity of a particular family of its square faces containing approximately 4/d of all the square faces. On the other hand, in [15] it was shown that while d − 1 square faces can “block” commutativity, d − 2 cannot; that is, a non-commutative d-cube diagram must have at least d − 1 non-commuting square faces (as conjectured in [14]). Here these prior results are extended. We have tried to include sufficient background that any category theorist or systems biologist can understand the underlying topological and combinatorial results. Aspects related only to (undirected) graphs are considered first. Cycle bases with desired special properties are constructed for the three standard graph families consisting of 5 184 hypercubes, complete and bipartite complete graphs, and the combinatorial isolation theorem for cubes given in [15] are extended to comparable results for complete and bipartite graphs. This is extended to the case of directed graphs and conditions are reviewed for embeddability of such “digraphs” in suitable host graphs. We then apply the developed cycle theory to commutativity of diagrams in general and particularly in groupoid categories to give some new results regarding both forcing and blocking of commutativity in various diagram schemes. In [6], A. C. Ehresmann and J.-P. Vanbremeersch describe the notion of an evolutionary and hierarchical system of categories and functors, which we call an EV-model. The biologically oriented Ehresmann-Vanbremeersch theory builds on Charles Ehresmann’s foundational work on categories both alone and, in later years, with Andrée Ehresmann (see [5]) while the EV-theory also includes the contributions of gerontologist, Jean-Paul Vanbremeersch. The EV-theory is very detailed and attempts to give a complete account of biological function and misfunction (e.g., aging) from the conceptual down to the cellular level. The intriguing idea of a sequence of hierarchically organized implicit diagrams however seems to need some form of error-correction to ensure coherence, and it is the intent of this paper to consider tools appropriate for the task. Interestingly, giving a full account of the notion of cycle “robustness” required for the combinatorics led to an enriched hierarchical structure in which cycles are constructed in a topologically natural way. A diagram is just a subdigraph of the digraph skeleton of a category, similar to what C. Ehresmann called a “sketch” By implicit diagrams of an EVmodel, we mean not just the “web of interactions” of the centers of regulation (CR), but also the categorical machinery itself since all basic notions of cat6 185 egory theory, such as functors and natural transformations, can be presented as commutative diagrams. In addition to describing the syntactic rules, diagrams may also encode semantics such as products, limits, pullbacks, and dual notions such as colimit. In an EV-type category-theoretic model, the cooperating CRs transmit information. Making the identification of morphism with message, coherence in such transmission corresponds to the condition that the implicit diagrams of an EV-model are commutative. Further, one would like to have some assurance in constructing an EV-model that “sufficiently close” ensures correctness and that there is a reward for intelligence which improves with complexity. Thus, the goals of coherent information, correction of errors, and cognitive leverage provide our primary motivation for offering a paper on the theory of commutative and partially commutative diagrams as part of this compendium. The paper is organized as follows. Sections 2–4 cover some graph theory basics. Section 5 presents a generalization of the “robust basis” theory introduced in [14] with results in sections 6–8. Section 9 reviews digraphs and diagrams, and gives the notion of a face of a digraph. Sections 10 and 11 consider how commutativity of a diagram is related to commutativity of bases, while Sections 12 and 13 tabulate the commutativity properties of diagrams on the scheme of certain standard orientations of the complete graph and of the hypercube. There is an exploration of the geometry of hypercube faces in Section 14, while the classical “cube lemma” and its groupoid simplification appear in section 15. Section 16 describes commutativity in hypercubes in more detail. Thresholds for commutativity and blocking numbers are studied in Section 17. Finally, in Section 18, we give a theorem on groupoid diagram extension, showing it is not possible when the category where the diagrams live is not a groupoid. Section 19 puts the results into the context of biology. 7 186 2 Graphs, paths, and cycles Let N, Z, R, and C denote the sets of nonnegative integers, all integers, real, and complex numbers, respectively. Write #S for the number of elements in a finite set S. For n > 0 in N, [n] := {1, 2, . . . , n}. If S is a set, diag(S) := {(s, s) : s ∈ S} ⊆ S × S, where equality holds iff #S = 1. We briefly define various graph theory terms used throughout this paper; see, e.g., [10]. A graph G = (V, E) consists of a finite, non-empty set V = V (G) of vertices and a set E = E(G) of edges which are unordered pairs of distinct vertices. Equivalently, (V, E) is a graph if 0 < #V < ∞ and E⊆ V × V \ diag(V ) , τ where τ is the equivalence relation with equivalence classes {(v, w), (w, v)}. Two vertices v, w are said to be joined by the edge e = vw (the equivalence class of (v, w)), and v and w are the endpoints. A multigraph (V, E, Φ) is an ordered triple, where V is a non-empty finite set, E is a finite set, and Φ is an incidence function which maps each edge e ∈ E to an unordered pair of not-necessarily-distinct vertices in V , called the endpoints of e. If Φ(e) has only one endpoint, the edge e is a loop. Two distinct edges e, e� are called parallel if they are incident to the same unordered pair {v, w} of vertices. When Φ is implicit, we will denote a multigraph merely by (V, E). We sometimes write “graph” instead of “multigraph” for brevity. Graphs are multigraphs without loops or parallel edges. Further, each graph determines a symmetric, irreflexive relation on its vertex set; two vertices v, w are adjacent iff they are joined by an edge of the graph. The intersection of two edges is the set of their common endpoints. In a multigraph, two edges can intersect in two vertices but in a graph, two edges can have at 8 187 most one common endpoint. Topologically, multigraphs are 1-dimensional CW-complexes, while graphs are 1-dimensional simplicial complexes. Let G = (V, E) be a graph. If E � ⊆ E, we write G(E � ) for the graph (V � , E � ) where V � is the set of all vertices in V which are endpoints of an edge in E � . If W ⊆ V , let G(W ) be the graph (W, E|W ), where E|W is the set of all edges in E which join two vertices in W ; the adjacency relation determined by E|W on the set W is exactly the same as the restriction of the adjacency relation on V determined by E. In general, H = (W, F ) is a subgraph of G = (V, E) if H is a graph, W ⊆ V , and F ⊆ E. Subgraphs of the form G(E � ) and G(W ) are called induced. Then G(E � ) is the smallest subgraph H of G with E(H) ⊇ E � while G(W ) is the largest subgraph H of G with V (H) ⊆ W . The degree deg(v) of a vertex v is the number of edges which are incident with it, and we write deg(H, v) to denote the degree of v with respect to some subgraph H. Technically, it is sometimes more convenient in the definition of G(E � ) to let V � = V , where vertices not incident with an edge in E � have degree zero with respect to G(E � ). Let G, H be graphs. A one-to-one correspondence φ : V (G) → V (H) given by v �→ v � is an isomorphism of G and H if vw ∈ E(G) iff v � w� ∈ E(H). The two graphs are called isomorphic, denoted G ≡ H. Two multigraphs G = (V, E, Φ) and G� = (V � , E � , Φ� ) are isomorphic if there are one-to-one correspondences α : V → V � , β : E → E � which commute with the respective attaching maps Φ and Φ� ; that is, the following square is commutative. E −→ (V × V )/τ ↓ ↓ E � −→ (V � × V � )/τ 9 188 Every multigraph G = (V, E) has a topological realization |G| which is the topological space obtained by identifying #V points and #E pairwise-disjoint copies of the unit interval [0, 1] =: I according to the way the edges intersect at their endpoints with respect to the incidence function Φ. In fact, |G| can be embedded in 3-dimensional Euclidean space, R3 , and if G is a graph, then |G| is homeomorphic to a subset of R3 in such a way that edges correspond to straight-line segments. Indeed, the union of any finite (or even countable) family of lines and planes is of 3-dimensional Lebesgue measure zero. Hence, one can place the vertices of G in R3 with no 3 vertices on a line and no 4 vertices in the same plane (this is called being in general position). Each straight-line-segment [v, w] = {(1 − t)v + tw : 0 ≤ t ≤ 1} determined by all convex combinations of a pair of distinct points v, w ∈ R3 is homeomorphic to I, and general position ensures that two distinct line segments of this type can only intersect at common endpoints of the edges to which they correspond. The union of the set of line-segments determined by the edges is a geometric representation of the graph (corresponding to the particular general-position placement of its vertices). For a graph, the topology which such a geometric representation inherits as a subspace of R3 is identical to that of the topological realization. We say that a multigraph is connected precisely when its topological realization is a connected topological space. A path is a connected graph which is either trivial (i.e., has one vertex) or which has exactly two vertices of degree 1 (the endpoints) with all other vertices, if any, of degree 2. Thus, a path corresponds to a sequence v1 , v2 , . . . , vr of distinct vertices with each successive pair vi , vi+1 adjacent, 1 ≤ i ≤ r − 1. A 10 189 path in a graph is a subgraph which is a path. A graph is connected if and only if every pair of distinct vertices are the endpoints of a path. The endpoints of a path are said to be joined by the path. Two paths with the same pair of endpoints are called internally disjoint (i.d.) if they have no other common vertices. The length of a path is the number of edges it contains, and a v-w-path has v and w as endpoints. The distance between two vertices v and w in a connected graph is the minimum length of any v-w-path. A path is called geodesic if it has length equal to the distance between its endpoints. A cycle is a graph which is connected and regular of degree 2. Adding an edge between the two endpoints of a path of length ≥ 2 creates a cycle. A cycle in a graph is a subgraph which is a cycle. In a graph, the shortest possible cycle has length 3, where the length of a cycle is the number of edges. (In a multigraph, loops are cycles of length 1 and two parallel edges constitute a 2-cycle.) For instance, the complete graph K4 on 4 vertices contains four distinct 3-cycles. Any two distinct vertices in a cycle are joined by two i.d. paths, and a cycle is geodesic if at least one of these paths is geodesic. A graph is bipartite if its vertices can be 2-colored with no two adjacent vertices colored the same. In a bipartite graph, all cycles have even length. Two vertices (resp., two edges) of a cycle of length 2k are said to be diametrical or diametrically opposite if they are separated by paths of length k (resp. k−1). A tree is a connected graph with no cycles. If G, H are graphs, then their cartesian product G × H is the graph with vertex set V (G × H) := V (G) × V (H) and E(G × H) := E(G) × V (H) ∪ V (G) × E(H). If G, H are connected, then so is their product. 11 190 3 Algebra of cycles in a graph One can do useful algebra with the subgraphs of a graph by identifying subgraphs with their edge-sets. Using the finite field Z2 = {0, 1}, a set of edges corresponds to a linear combination of edges with coefficients in Z2 . As 1 + 1 = 0 in this field, the algebraic sum of two linear combinations of edges corresponds to the symmetric difference of the corresponding edge-sets. More formally, a 1-chain c = � e∈E � e has support E � and the support of c1 + c2 is E1 ∪ E2 \ E1 ∩ E2 , where E1 , E2 are the supports of c1 , c2 . Let C1 (G) denote the set of 1-chains. Similarly, let C0 (G) denote the set of 0 chains which are Z2 -linear combinations of vertices of G. One defines ∂ : C1 (G) → C0 (G) as the unique linear extension of the correspondence vw �→ v + w; that is,  ∂ � e∈E �  e = � v. {v:deg(G(E � ),v) is odd} Hence, the set of all edge-sets F ⊆ E with ∂(F ) = 0 constitutes a Z2 -vector space and consists of all edge-sets F for which deg(G(F ), v) is even for every vertex v of G. These are called the algebraic cycles and correspond to the Eulerian subgraphs of G. Every cycle is an algebraic cycle but the Fis clearly false. However, every algebraic cycle is the sum of a set of cycles which are edge-disjoint. A set S of cycles in a graph is called spanning if it has the property that every cycle in the graph is the algebraic sum of some subset of S. A cycle basis of a graph is a spanning set of cycles which is minimal in the sense that no proper subset is spanning. A set of cycles is independent if a linear combination (over Z2 ) of members of the set is zero if and only if all coefficients of combination are zero. By linear algebra, a set of cycles is a basis for the cycles if and only if it is a maximal independent set and all cycle-bases of a 12 191 graph G have the same cardinality, denoted β(G) and called the cyclomatic number of G. It is well-known and easy to prove that for any graph G, β(G) = #E(G) − #V (G) + π0 (G), (1) where π0 (G) denotes the number of connected components of the graph. Given a graph G = (V, E) and an edge e ∈ E, the elementary subdivision Ge of G replaces e by a path of length 2; this introduces one new vertex while removing one edge, creating two new edges which join the new vertex to the endpoints of the removed edge. Since the number of connected components remains constant when G is replaced by Ge , by equation (1), cyclomatic number doesn’t change under elementary subdivision. Now if one iterates the elementary process; say, ((Ge )e� )e�� , . . . , e� ∈ E(Ge ), e�� ∈ E((Ge )e� ), . . . , subdividing newly created edges and edges from the original graph, then one obtains a general subdivision where various edges of G are subdivided multiple times and cyclomatic number will be unchanged. The relation of subdivision is a partial order on graphs; also for any edge e of the path, (Pn )e ≡ Pn+1 and similarly for cycles. Two graphs G1 and G2 have homeomorphic realizations if and only if there is a graph H which is a common subdivision of both G1 and G2 . Hence, β(G) depends only on the topology |G| of the graph so cyclomatic number is a topological invariant (in fact, it is an invariant up to homotopy equivalence). Note that G is a tree if and only if G is connected with β(G) = 0. 13 192 4 Three graph families We consider graph families: complete graphs Kn , bipartite complete graphs Kp,q , and hypercubes Qd . A graph is complete if every distinct pair of vertices are adjacent, and Kn denotes a complete graph with n vertices. For example, the competition between teams in a league determines a complete graph when each pair of teams competes. A triangle in Kn is a subgraph which is complete of order 3; let T (Kn ) denote the set of all triangles in Kn , so #T (Kn ) = � � n . 3 (2) From equation (1), one has � � � � n n−1 β(Kn ) = −n+1= . 2 2 (3) A bipartite graph is complete if all pairs ij � , 1 ≤ i ≤ p, 1 ≤ j ≤ q of different type vertices are adjacent and Kp,q denotes the complete bipartite graph with p “red” vertices and q “blue” ones. A complete bipartite graph is formed if each of p humans is able to operate each of q machines. A square in Kp,q is a subgraph which is isomorphic to K2,2 . Let S(Kp,q ) denote the set of all squares; this set has positive cardinality #S(Kp,q ) = � �� � p 2 q 2 (4) if min{p, q} ≥ 2. A similar calculation as for the complete graph determines the cyclomatic number: β(Kp,q ) = pq − (p + q) − 1 = (p − 1)(q − 1). (5) For d any non-negative integer, the hypercube of dimension d (or more briefly, the d-cube), Qd , d ∈ N, is the graph (V, E) with V = {0, 1}d and vw in 14 193 E iff v and w differ in exactly one coordinate; i.e., the vertices are the length-d bit strings and adjacency corresponds to Hamming distance 1. This graph has 2d vertices each of degree d, so there are d2d−1 edges. Let wt(v) denote the weight of a vertex v, which is the number of 1s in the bit-string v - i.e., the number of coordinates with value 1. Every hypercube is a bipartite graph as edges must join vertices with different parity weights. A square in Qd consists of an induced subgraph which is isomorphic to Q2 . Thus, a square s in Qd is determined by two of the d coordinates - say i and j - and the four vertices of the square are identical in all coordinates except for coordinates i and j, where all four possible pairs of values 0 and 1 appear. Let S(Qd ) denote the set of squares in Qd . Then #S(Qd ) = � � d d−2 2 = d(d − 1)2d−3 . 2 (6) As K2,2 ≡ C4 ≡ Q2 , the notion of “square” for Kp,q and Qd is the same. Again, one can easily calculate the number of elements in a cycle basis of Qd , β(Qd ) = d2d−1 − 2d + 1 = (d − 2)2d−1 + 1. (7) The d-cube may be viewed as two copies of the d − 1-cube (say, bottom Q0d and top Q1d ) with a set of disjoint edges connecting each vertex v0 in one copy with the corresponding vertex v1 in the other copy; that is, Qd is the cartesian product of Qd−1 with K2 , Qd = Qd−1 × K2 . Hence, hypercubes are connected graphs. We give a direct inductive argument for the connectedness of hypercubes which generalizes usefully. The result holds for Q0 and Q1 . Suppose it’s true for Qd−1 and let u, v ∈ V (Qd ). If u, v belong to some Qd−1 -subgraph, then by the induction hypothesis, they are joined by a path in Qd−1 and hence in Qd . If u ∈ Q0d and v ∈ Q1d , then by induction there is a path P in Q0d from u to 15 194 the unique vertex v � ∈ Q0d with vv � ∈ E(Qd ) and extending P by the edge vv � gives a path in Qd from u to v. A similar inductive argument proves that Qd is d-connected; that is, any two distinct vertices are joined by d pairwise-i.d. paths. In spite of its apparent simplicity, the hypercube graph has many unsolved problems. For example, even the order of magnitude of the number of Hamiltonian cycles (that is, cycles which include all of the vertices) is unknown. Lovasz [19] conjectured that the set of vertices of weight k or k + 1 in the 2k + 1-cube always induce a subgraph of the cube which has a Hamiltonian cycle. This has been shown to be true up to d = 35 [26]. Geometric questions also abound for the hypercube - for instance, Hadamard’s conjecture that every hypercube of dimension 4k (with vertex set {−1, +1}4k ) contains an orthogonal subset with 4k members. Also, it is unknown whether the upper bound of d − 1 on the book thickness of Qd [1] is best possible. Hypercubes have been used as an architectural model for parallel computers, and they provide the geometry of digital codes. If hypercubes can be applied as a model for cognition, then they might enable a graceful approach to complexity as theorems in the sequel show a computational advantage which grows with the dimension of the hypercube. 5 Well-arranged sequences of cycles We define special types of cycle basis with the property that every cycle can be built up from the members of the basis in a recursively convenient fashion. These include robust bases [14], of interest in mathematical biology [17], [24], and a generalization, introduced here, called a robustly hierarchically generating basis (or rhg-basis), which uses a hierarchical construction. 16 195 Two elements of cyc(G) are called compatible if their intersection is homeomorphic to P2 ; i.e., if they intersect in a nontrivial path. The sum of two compatible cycles is a cycle. As in [14], call a sequence z1 , . . . , zk of cycles well arranged if for each i, 1 ≤ i ≤ k − 1, the partial sum z1 + · · · + zi intersects zi+1 in a nontrivial path. By induction, each of the partial sums of a well-arranged sequence is a cycle, and each cycle in the sequence is compatible with the previous partial sum. Let S be any set of cycles in some graph G and let z be a cycle of G. The set S will be said to robustly span z if there is a well-arranged sequence z1 , . . . , zk of elements in S such that z = z1 + · · · + zk , and S robustly spans a set T of cycles if S robustly spans each cycle in T . A set of cycles is a robust spanning set if it robustly spans the set cyc(G) of all cycles in the graph. We write rspan(S) for the set of all cycles robustly spanned by S. In [14], we focused on the question of when a graph has a cycle basis which is also a robust spanning set. Such a basis, if it exists, is called a robust basis for the given graph. Every graph has a robust spanning set of cycles - for instance, cyc(G) suffices with well-arranged sequences of length 1 for every cycle! But the cardinality of the smallest robust spanning set is not known. Here we shall weaken the notion of “robustly spanning” in order to generate all cycles of certain graphs with well-arranged sequences. This will be sufficient to ensure that various properties holding for the generating cycles must also hold for all cycles which was our original motivation for introducing the notion of a robust spanning set. 17 196 5.1 Hierarchically well-arranged sums Let S, T ⊆ cyc(G); S robustly hierarchically generates T if there is a positive integer k and a sequence F0 ⊆ F1 ⊆ · · · ⊆ Fk such that S = F0 , T = Fk , and Fi robustly spans Fi+1 for 0 ≤ i ≤ k − 1; we call k the depth of the hierarchy by which S robustly hierarchically generates T . We write rhg(S) := � T, where the union is over all T which are robustly hierarchically generated by S. Thus, rhg(S) = cyc(G) if and only if every cycle of G can be hierarchically constructed from the cycles in S where in each step of the hierarchy, cycles are the sum of well-arranged sequences of cycles from lower levels. Conjecture 5.1 For every graph G there is a basis S of cycles such that rhg(S) = cyc(G). We show that Conjecture 5.1 does hold for the three graph families: complete, bipartite complete, and hypercubes. For complete graphs, one only needs k = 1; that is, they do have a robust basis (as shown in [14]). However, for bipartite complete graphs and for hypercubes, the previous arguments were incomplete and one needs k > 1. 5.2 An example of non-robustness To show that this property of robustness is nontrivial, we exhibit a graph and a non-robust basis due to Andrew Vogt; see [14] just before Proposition 1. Consider the plane graph G which is formed by a hexagon, with an inscribed triangle. As G has 6 vertices, 9 edges, and is connected, there must be 4 elements in any basis for its cycles. Labeling the 6 nodes in counter-clockwise 18 197 order by 1, 2, 3, 4, 5, 6, with 1, 3, 5 as the inscribed triangle, consider the basis V formed by the boundaries of the three diamond-shaped regions, z1 = 1235, z2 = 3451, z3 = 5613 and z4 = 135. The 6-cycle z = 123456 is the sum of the three diamonds z = z1 + z2 + z3 , but because any two of the diamonds intersect in the disconnected graph formed by an edge of the inscribed triangle (with its endpoints) together with the opposite vertex of the inscribed triangle, V is not a robust basis of G. (8) In fact, this graph and basis don’t even satisfy the weaker condition that the sum of the first two cycles in the sequence is itself a cycle; that is, the basis is not “cyclically robust” in the sense of [14]. For an example which is cyclically robust but not robust, consider K4 with the basis 1243, 1234, 134. Then 1324 is the sum of 1243 and 1234 but the latter two cycles intersect in two disjoint edges 12 and 34. 6 Examples of hierarchically robust bases Hierarchically robust bases will be shown to exist for three of the most regular graphs: complete, bipartite complete, and hypercube graphs. First, we show that for any graph the geodesic cycles robustly hierarchically generate all cycles. Our argument follows that of Georgakopoulos and Sprűssel [8] who extended the fact that geodesic cycles span to the case of graphs with infinitely many vertices (but with finite vertex degrees). It might 19 198 be interesting to consider the extension of both the graph theory and its applications to diagrams for countably infinite, locally finite situations. Would such an extension be relevant for the field of theoretical biology? We leave these questions to another paper. Theorem 6.1 Let G be a graph and let GE = GE(G) denote the set of geodesic cycles of G. Then rhg(GE) = cyc(G) and one can require that all geodesic cycles used in the hierarchical well-arranged (hwa) sum for a cycle z have length not exceeding the length of z. Proof. Suppose that the theorem were false. Then there would exist some cycle z of G which is not a hwa sum and, among all such cycles, z has minimum length. Since z is not geodesic cycle, there must exist a nontrivial path P intersecting z in exactly two vertices v, w, where the length of P is less than the length of either of the paths P1 , P2 within z joining v and w. Let z1 , z2 , resp., denote the two cycles obtained by replacing P1 (or P2 ) with P . As the new cycles are shorter, each is an hwa-sum and z1 , z2 is a well-arranged sequence for z. This contradicts the assumption that z is not an hwa sum. ✷ While this proves that the geodesic cycles robustly hierarchically generate all cycles, the method is existential. An algorithmic approach should also give information on the depth of such hwa sums. 6.1 The complete graphs Kn The set K(Kn ) consisting of the triangles formed by a fixed vertex 1 with all possible distinct pairs {i, j}, 2 ≤ i, j ≤ n, is an independent set of cycles for Kn with cardinality � n−1 2 � , but by equation (3) this is the same as β(Kn ) and so K(Kn ) is a basis. This set robustly spans all the cycles of Kn [14]. 20 199 Theorem 6.2 The set K(Kn ) is a robust basis for Kn . Proof. Let z = (i, j, k, . . . , �, m) which misses 1. Then z is the sum of the well-arranged sequence 1ij, 1jk, . . . , 1�m, 1mi. To get a cycle z which includes the special vertex 1 let i and m be the nearest neighbors of 1 on the cycle and consider the well-arranged sequence 1ij, 1jk, . . . , 1�m, where i, j, k, . . . , �, m is the unique path in z joining i and m and avoiding 1. 6.2 ✷ The bipartite complete graphs Kp,q Let K(Kp,q ) be the set of all squares in Kp,q of the form 1, 1� , i, j � , where 2 ≤ i ≤ p, 2 ≤ j ≤ q, and x, x� denote vertices in the bipartite decomposition corresponding to Kp,q . This is the set of all 4-cycles containing the edge 11� . The lines ij � are all distinct, so the members of K(Kp,q ) form an independent set of cycles and has cardinality (p − 1)(q − 1) so by (5) it is a basis. Theorem 6.3 Let p, q ≥ 2. Then K(Kp,q ) robustly hierarchically generates GE(Kp,q ) with hierarchical depth k = 2. Proof. The squares which include the chosen edge 11� are already in the basis. To get a square which includes exactly one endpoint of the chosen edge, say ij � 1k � , add the basis squares ij � 11� and ik � 11� which meet in the path 11� i. To get a square ij � k�� which is (vertex) disjoint from 11� , start with ij � k1� and add ij � �� 1� to get k�� 11� . Add ij � 11� to get ij � k�� as required. Note that for each of these sums, the two cycles intersect in nontrivial paths. Thus, the basis of special squares K(Kp,q ) generates all squares, using two hierarchical levels. But a cycle in the bipartite complete graph is geodesic if and only if it is a square. ✷ Corollary 6.4 For p, q ≥ 2, rhg(K(Kp,q )) = cyc(Kp,q ). 21 200 7 Cycles in the hypercube Qd We will frequently use the decomposition E(Qd ) = E(Q0d ) + E(Q1d ) + E(Si(Qd )), (9) where Q0d = {0} × Qd−1 and Q1d = {1} × Qd−1 denote the “bottom” and “top” of the d-cube, while Si(Qd ) = Qd − (E(Q0d ) ∪ E(Q1d )) denotes the remainder of the cube (its “sides”). Let K(Qd ) be the following recursively defined collection of squares in Qd . For d = 0 and d = 1, the set is empty, and K(Q2 ) = {Q2 }. Having defined K(Qd−1 ) for d ≥ 3, let S � the corresponding set of squares in the bottom of Qd and let S �� be the set of all squares in the “sides” of Qd . Then K(Qd ) = S � ∪ S �� . that is, K(Qd ) = K(Q0d ) ∪ � e∈E(Qd−1 ) (Q1 × ē), where ē denotes the K2 determined by e and its endpoints. So K(Q3 ) consists of the bottom square and the four side squares. For convenience, we write Qd “contains” a square to mean the square is a subgraph and use similar transparent phrasings on occasion for descriptive clarity. We claim that K(Qd ) is a cycle basis. It is independent since by induction the squares in S � in the decomposition (9) are independent and the squares in the sides, S �� , are independent of those in the bottom S and also of each other 22 201 since each corresponds to a different edge. But again by induction #K(Q0d ) + #E(Qd−1 ) = 1 + (d − 3)2d−2 + (d − 1)2d−2 = 1 + (d − 2)2d−1 so the set K(Qd ) is a maximum independent set of cycles by (7). Theorem 7.1 The basis K(Qd ) robustly hierarchically generates the geodesic cycles of Qd with a depth 2 hierarchy. We prove this by generating the squares of Qd as members of the robust span of K(Qd ) and showing the squares robustly span the geodesic cycles. Theorem 7.2 For every d ≥ 2, rspan(K(Qd )) ⊇ S(Qd ). Proof. Every square in 1 × Qd−1 (i.e., every square in the top of Qd ) is the top square of 3-cube with base in 0 × Qd−1 and sides in the sides of Qd . Hence, the following argument, for the 3-cube itself, applies to all such squares. A well-arranged sequence to build the top square Q13 of the cube is as follows: Q03 , e¯1 × K2 , . . . , e¯4 × K2 , where e1 , . . . , e4 is an ordering of the edges of the 4-cycle Q03 . ✷ In fact any ordering which starts with the bottom square is well-arranged; a sequence which is not well-arranged would be any sequence starting e¯1 × K2 , e¯3 × K2 , . . . since the two cycles don’t intersect. Next we characterize the geodesic cycles of the hypercube. Lemma 7.3 A cycle in Qd is geodesic if and only if the corresponding sequence of coordinate-flips corresponding to the sequence of its edges (starting anywhere on the cycle) consists of a permutation repeated twice. 23 202 Proof. It is easy to see that a cycle satisfying the permutation condition must be geodesic. Conversely, in each cycle, each bit must change its state an even number of times. Each edge flips a bit. If two edges change the same bit and no other edge changing that bit is between them, then the bit must be changed in opposite directions by that pair of edges. If in a cycle z of length 2k two such successive i-th bit flipping edges e, e� are not diametrically opposite in the cycle, then there exist two diametrically opposite vertices v, w in the cycle such that there exists a v-w-path P contained in z with e, e� ∈ P (E). But then v and w are also joined by a path of length less than k obtained by making exactly the same bit flips as in P except that the i-th bit is never flipped. Hence, in a geodesic cycle, the permutation condition holds. ✷ An example of two internally disjoint paths in Q4 corresponding to nonreversed permutations may help for understanding. Let P1 be the path P1 = 0000, 1000, 1100, 1110, 1111 which corresponds to the permutation 1234; let P2 be the path P2 = 0000, 0010, 1010, 1011, 1111 corresponding to the permutation 3142. The vertices v = 0010 and w = 1110 have distance 4 around the cycle formed by P1 and P2 , but u = 1010 is adjacent to both v and w. Notice that in any geodesic cycle, no two successive edges can flip the same bit. A cycle of length 4 corresponds to a square of Qd and vice versa. To get a geodesic cycle, one needs to generate permutations and this can be done by composing a sequence of transpositions which exactly correspond to squares. Lemma 7.4 Every geodesic cycle in Qd is robustly spanned by the squares; 24 203 that is, rspan(S(Qd )) ⊇ GE(Qd ). Proof. It suffices to show that the geodesic cycle zd in Qd determined by the identity permutation π : i �→ i (i.e., (123 · · · d) in one-line notation), repeated twice as required by Lemma 7.3, is a well-arranged sum of squares. The cycle zd consists of the two internally disjoint paths P (d) and P � (d), both from 0̄ to 1̄ where P � (d) corresponds to the reverse permutation π op := πd , πd−1 , . . . , π2 , π1 . For example, in cyclic order, starting at 0̄, the cycle for d = 3 is given by z3 = (000, 100, 110, 111, 011, 001). To make the induction work, we show further that the family of squares constituting a well-arranged sequence can be chosen so that every edges along P are taken in order of their appearance between 0̄ and 1̄.. This corresponds to the sequence τ1 , τ2 , . . . , τr , where r = (d2 + d)/2 formed by concatenating the interchange sequences {12, 13, . . . , 1d}, {23, 24, . . . , 2d}, . . ., {(d − 2)(d − 1), (d − 2)d}, and {(d − 1)d}. Alternatively, writing the permutation of S as a sequence of members of S, σ := π −1 ◦ π op which carries π to π op can be factored as a sequence of transpositions of members of the current permutation string which are adjacent to one another in the current string. This can be visualized in the usual fashion of topology in terms of braids by interchanging the first string consecutively with each of the others till it is in the last position. Then do the same thing moving the second string into the next to last place, and so forth. Now Qd consists of two copies of Qd−1 , and in the bottom copy by the inductive hypothesis, there is a well-arranged sequence of squares which sums 25 204 to 0 × zd−1 in such a way that the edges in the forward path 0 × P (d − 1) are covered in sequential order by the well arranged sequence of squares in 0 × Qd−1 . Since the sequence of squares 12, 13, . . . , 1d is well arranged and sums to a cycle which meets 0 × zd−1 in 0 × P (d − 1), the induction holds and the result is established. ✷ For instance, apply {12, 13, 14, 23, 24, 34} to π = 1234 to get 4321. Now 12 and 13 correspond to the squares 0000 → 1000 ↓ ↓ 0100 → 1100 and 0100 → 1100 ↓ ↓ , respectively, 0110 → 1110 meeting in edge 0100 → 1100. The sum of these two squares is the cycle z � = (0000, 1000, 1100, 1110, 0110, 0100), where as always (a1 , a2 , . . . , ak ) means the cycle with edges [a1 , a2 ], . . . [ak−1 , ak ]. The transposition 14 corresponds to the square 0110 → 1110 ↓ ↓ 0111 → 1111 which intersects z � in the edge 0110 → 1110. Let z �� be the sum of the square corresponding to 14 with the cycle z � , so z �� = (0000, 1000, 1100, 1110, 1111, 0111, 0110, 0100). But {0} × z3 is the cycle (0000, 0100, 0110, 0111, 0011, 0001, 0000) which inter- sects z �� in {0} × P (3). Theorem 7.1 now follows from Theorems 6.3 and 7.2 and Lemma 7.4. 26 205 8 Isolation theorems The combinatorial results proved in this section will allow us to later derive corresponding results on blocking of commutativity. The first is from [15]. Theorem 8.1 Let d ≥ 3. For any nonempty set S of d − 2 or fewer squares in Qd , there exists a Q3 -subgraph of Qd containing exactly one element of S. Using the method given in [15], one can prove an analogous theorem for the complete graph. Theorem 8.2 Let n ≥ 4. For any nonempty set T of n − 3 or fewer triangles in Kn , there exists a K4 -subgraph of Kn containing exactly one element of T . Proof. The result holds for n = 4. Suppose the result holds for n = p − 1 and let T be a nonempty set of at most p − 3 triangles in Kp . Then either (i) T is contained in the set of triangles of some Kp−1 -subgraph G of Kp or (ii) there exists a proper subset T � ⊂ T with T � contained in the set of triangles of some Kp−1 -subgraph H of Kp . In case (i), every t ∈ T is in the K4 subgraph determined by t ∪ {v}, where v is the unique vertex in V (Kp ) \ V (G). In case (ii), 1 ≤ |T � | ≤ p − 4 so by the inductive hypothesis there is a K4 -subgraph of H (and hence of Kp ) which contains exactly one member of T � . ✷ Similarly, one has a result for the bipartite complete graph. Theorem 8.3 Let p ≥ 2, q ≥ 2, p+q ≥ 5. For any nonempty set S of p+q−4 or fewer squares in Kp,q , there exists a K3,2 -subgraph (or a K2,3 -subgraph) of Kp,q containing exactly one element of S. 27 206 Proof. Let S(G) denote the set of squares in G. Either (i) S ⊆ S(G), where G is isomorphic to Kp−1,q , p ≥ 3, or to Kp,q−1 , q ≥ 3, or (ii) ∃ a proper subset S � ⊂ S such that S � ⊆ S(G), with same condition on G. In case (i), every square K2,2 is isolated by the K3,2 obtained by appending the missing “red” vertex or the missing “blue” vertex according to the color of the vertex removed to obtain G. Case (ii) follows from induction on p + q. ✷ 9 Digraphs, Faces, and Diagrams A digraph D = (V, A, Ψ) is a finite nonempty set V of vertices, a set A of arcs, and an incidence function Ψ : A → V × V . Define the source of an arc a ∈ A as Π1 (Ψ(a)) =: src(a) and the target of a as Π2 (Ψ(a)) =: tgt(a), where Π1 , Π2 denote the first and second coordinate projection. We write a = (v, w) for an arc a when src(a) = v, tgt(a) = w. If A ⊆ V × V and Ψ is the inclusion, then D is simply a relation on V . An isomorphism from D = (V, A, Ψ)) to D� = (V � , A� , Ψ� ) is a pair of bijections φ1 : V → V � , φ2 : A → A� such that for every a ∈ A, Ψ� (φ2 (a)) = (φ1 (src(a)), φ1 (tgt(a)). Two digraphs are isomorphic if there is an isomorphism from one to the other. For a digraph D = (V, A, Ψ), the underlying multigraph G = U (D) is G = (V, A, Φ), where Φ(a) = {v, w} if Ψ(a) = (v, w); that is, one forgets the sense of direction of the arcs. Given any multigraph G, an orientation of G is a directed graph whose underlying multigraph is G. Equivalently, an orientation is a function which assigns to each edge e = vw of G one of the two ordered pairs (v, w) or (w, v). Let Ω(G) denote the set of orientations of G; for a labeled graph G with 28 207 m non-loop edges, there are 2m distinct orientations. For instance, K2 has a unique (up to isomorphism) orientation but if the vertices are labeled, say with v, w, then the two digraphs (v, w) and (w, v) can be distinguished. Taking hypercubes as labeled graphs, Qd has 2d2 d−1 distinct orientations; for d = 0, 1, 2, 3, this gives 1, 2, 16, 4096, respectively. An ordered pair of arcs (a1 , a2 ) in a digraph are called composable if and only if src(a2 ) = tgt(a1 ). If (φ1 , φ2 ) : D → D� is an isomorphism, then an ordered pair (a1 , a2 ) in A(D) are composable if and only if the ordered pair (φ2 (a1 ), φ2 (a2 )) of arcs in A(D� ) are composable. A digraph D is called transitive if for every pair (a, b) of composable arcs, there is an arc c = (v, w), where v = src(a) and w = tgt(b); D is reflexive if for every vertex v there is a loop (v, v) in A; and D is symmetric if and only if (v, w) is an arc whenever (w, v) is an arc. A small category is a reflexive digraph with an associative law of composition on the set of composable arcs which has an identity for each vertex. See [20] for category theoretic concepts. A small category C has a digraph skeleton Sk(C) (forget the composition) Sk(C) = (V, A, Ψ), where V = Obj(C), A := mor(C) = � x,y∈Obj(C) C(x, y), and for a ∈ A, Ψ(a) = (x, y) if a ∈ C(x, y). A digraph is the digraph skeleton of a small category if and only if it is transitive and reflexive, and it is the digraph skeleton of a small groupoid if and only if it is reflexive, symmetric, and transitive. For k ≥ 1, a sequence of arcs a1 , a2 , . . . , ak of arcs in A(D) is called a dipath (or dicycle) of length k if and only if (i) for each i, 1 ≤ i ≤ k − 1, (ai , ai+1 ) is composable and (ii) all of the k+1 vertices src(a1 ), src(a2 ), . . . , src(ak ), tgt(ak ) are distinct (or (ii)’ all of the k vertices src(a1 ), src(a2 ), . . . , src(ak ) are distinct 29 208 and tgt(ak ) = src(a1 ) so (ak , a1 ) is composable). A dipath (a1 , a2 , . . . , ak ) with src(a1 ) = v and tgt(ak ) = w is called a v-w-dipath. Given a ∈ A(D) and v ∈ V (D), we say that a is incident to v (or “directed toward”) if v = tgt(a) and that a is incident from v (or “directed away from”) if v = src(a). Let outdeg(v) denote the number of arcs directed away from v and let indeg(v) denote the number of arcs directed toward v. A source vertex in D is a vertex v with indeg(v) = 0, and a target vertex v in D satisfies outdeg(v) = 0. A digraph is acyclic if it contains no dicycle. Each acyclic graph contains a source; dipaths are acyclic and have a unique source. By reversing all arcs, each acyclic graph has a target and dipaths have a unique target. A pair of dipaths are called parallel if they have common source and target vertices, say, v and w. Two dipaths are said to be internally disjoint if they are parallel v-w paths with v and w the only common vertices. A face of the digraph (from v to w) is a pair of internally disjoint vw-dipaths; the length of the face is the sum of the lengths of the dipaths. To avoid trivial faces, we assume that v �= w. This is not the same as the notion of “face” of a polytope unless the digraph has a plane embedding, and the two dipaths constituting a digraph face from v to w have topologically realizations which together bound a 2-dimensional disk (e.g., for the 3-cube with its standard orientation. From now on, face means in the digraph sense. A face f of D gives rise to a cycle in U (D) by means of the natural function ν : F(D) → cyc(U (D)) where if f = {P1 , P2 }, then ν(f ) = U (P1 ) ∪ U (P2 ). We call a digraph essential if the faces of D correspond under ν to an rhg-spanning set of cycles. For example, the standard tournament Kn∗ and standard directed hypercube Q∗d are essential, while an inessential digraph can 30 209 be formed by attaching acyclic triangles to each arc of an alternating square. The resulting digraph has 8 vertices, 12 arcs, and (being a connected graph) has a cycle basis with 5 cycles but it has only 4 faces (the acyclic triangles). Let D be a digraph and let C be a small category. A diagram on the scheme D in the category C is a pair of functions (both denoted δ for convenience) which maps the vertices of D to the objects of C and the arcs of D to the morphisms of C in a compatible way; that is, δ : D → C, where for v, w ∈ V (D) and a = (v, w) ∈ A(D), δ(v), δ(w) ∈ Obj(C) and δ(a) ∈ C(δ(v), δ(w)). Let D be a digraph which is isomorphic to a subdigraph of the skeleton digraph of some small category C. Then D determines a diagram and conversely every diagram arises in this way. When a diagram δ : D → C exists, each pair of parallel dipaths in D provides alternative morphism strings with common source and target objects. If the composition of these morphism strings gives the same result for any two v-w-parallel dipaths, then the diagram is said to commute between v and w. A diagram is commutative if it commutes between all pairs of distinct vertices. Commutative diagrams can be used to express many mathematical facts. For example, if D is the digraph Q2 with its standard orientation and C is any category, then for all A, B, C, D ∈ Obj(C), there are commutative diagrams δ = δA,B,C,D on the scheme D in the category of sets Ens given by C(A, B) × C(B, C) × C(C, D) ↓b C(A, C) × C(C, D) a −→ d −→ 31 C(A, B) × C(B, D) ↓c C(A, D) 210 where a = (1, ◦B,C,D ) : (α, β, γ) �→ (α, β ◦ γ), and similarly b = (◦A,B,C , 1), c = ◦A,B,D , and d = ◦A,C,D . Commutativity of diagrams such as these can be used to express various algebraic properties of a category. For example, in this case, the diagrams express the associativity of composition. Let δ : D → C be a diagram. If both morphism strings in C corresponding under δ to the two internally-disjoint dipaths in a face of D give the same composition, then the face commutes with respect to δ. Theorem 9.1 Let δ : D → G be any diagram with G a groupoid. Then δ is commutative iff and only if every face of D commutes with respect to δ. Proof. Let v, w ∈ V with parallel dipaths P, P � joining v to w. Then there exists a positive integer k and dipath decompositions P = P1 ∗ Q 1 ∗ P2 ∗ Q 2 ∗ · · · P k ∗ Q k and P � = P1� ∗ Q1 ∗ P2� ∗ Q2 ∗ · · · Pk� ∗ Qk , where ∗ denotes composition of dipaths and for each i, 1 ≤ i ≤ k, the pair Pi , Pi� determine a face. Note that the common dipath segments Qi can be trivial dipaths consisting of a single vertex. Induction on k completes the argument. ✷ We write F(D, v, w) to denote the set of v-w-faces in the digraph D and F(D) for the set of all faces. In fact one only needs to examine the faces corresponding to a robust hierarchically generating set of cycles. In the best case, an rhg-basis suffices. 32 211 10 Commutativity in groupoids Even if faces intersect in a common nontrivial dipath, their sum might not be a face (although it is a cycle) since there may not be unique source and target vertices. The difficulty can be alleviated by assuming that C is a groupoid; that is, every morphism has an inverse. In this case, one can extend δ : D → C to δ̃ : D̃ → C, where D̃ is the intersection of all symmetric digraphs which contain D (that is, D̃ is obtained from D by appending the reverse arcs a−1 = (w, v) for each arc a = (v, w) ∈ A(D), ∀v, w ∈ V (D), setting δ̃(a−1 ) = (δ(a))−1 . For every cycle z ∈ cyc(U (D) and all distinct vertices v, w ∈ V (z) there is a unique v-w face f of D̃ with U (f ) = z. Thus, the natural function ν is onto and the cardinality of ν −1 (z) is � � k 2 where k = #V (z). Groupoid categories provide a convenient environment for diagrams since one can “forget” the direction of the arcs, following a path in the underlying undirected graph. This means that given a diagram in the groupoid, any path or cycle in the underlying graph produces uniquely specified string of morphisms. When an edge is traversed in its proper sense as an arc, use the morphism associated with the arc; otherwise, use the inverse morphism to represent the oppositely oriented arc. Cycles were defined above as connected subgraphs which are regular of degree two. However, one may also regard a cycle z as the sequence of its edges (or vertices) taken in fixed clockwise or counterclockwise order and starting at any v ∈ V (z). Thus, a cycle of length k gives rise to 2k distinct ordered cycles, denoted (z, v, +), (z, v, −), v ∈ V (z). Similarly, any nontrivial path P gives rise to two ordered paths P ± . 33 212 Let δ : D → G be a diagram, where G is a groupoid. An ordered cycle in the underlying graph of D starting at a vertex v has a natural interpretation as a morphism in G from δ(v) to itself, while an ordered v-w-path can be interpreted as a morphism in G from δ(v) to δ(w) in the “positive” orientation (or in reverse in the negative orientation). Indeed, let D be a digraph whose underlying graph is a cycle or path, and let a1 , . . . , ak be the sequence of arcs corresponding to some choice of starting point v and direction of traversing the cycle or path. Suppose that δ : D → G is a diagram on the scheme D in a groupoid. Then each ai is either traversed in its proper or reversed sense and we accordingly assign either δ(ai ) or δ(ai )−1 to the edge traversal. Let (z, v, +) or P + denote an ordered cycle or path, and define the value of δ(z, v, +) or δ(P + ) to be δ(a1 )ι1 ◦ δ(a2 )ι2 ◦ · · · ◦ δ(ak )ιk , where the exponents ιj are ±1 according to whether the arc aj is traversed in its proper or reversed sense when following the given order. Clearly, δ(z, v, +) ∈ G(δ(v), δ(v)) and if P is a v-w-path, then δ(P + ) ∈ G(δ(v), δ(w)). A cycle in the underlying graph of the digraph scheme of a groupoid diagram will be called a cycle of the diagram. A cycle z of a diagram δ : D → G is a commutative cycle if δ(z, v, +)) = 1v for some ordering (z, v, +). This condition is independent of the ordering chosen. Indeed, if vw ∈ E(z) with a = (v, w) ∈ A(D), then (δ(a))−1 ◦ δ(z, v, +) ◦ δ(a) = δ(z, w, +) so δ(z, w, +) = 1w iff δ(z, v, +) = 1v . Hence, starting point doesn’t matter and reversing direction takes the inverse of the morphism With respect to diagrams in groupoids, a face f commutes if and only if the corresponding cycle ν(f ) is commutative. 34 213 Lemma 10.1 Let δ : D → G be a groupoid diagram with internally disjoint v-w-dipaths P1 , P2 . Then δ(P1 ) = δ(P2 ) if and only if ν(P1 , P2 ) commutes. We call a diagram in a groupoid strongly commutative if all of its cycles commute. A diagram is strongly commutative if and only if all orientations of its underlying graph are commutative, so a strongly commutative diagram is commutative. However, the converse is false. Consider a diagram on the scheme of an alternatingly oriented cycle in which arcs meet either head-to-head or tailto-tail. Such a diagram is trivially commutative since maximal dipaths have length 1 so the diagram has no faces. But the corresponding cycle may not commute. Indeed, let G be the category F of finite sets and bijections, let [2] be the set with two elements, and let τ : [2] → [2] be the non-identity bijection. For the alternating orientation D of C4 , let δ : D → F be defined by δ(v) = [2] for every vertex and let δ assign τ to exactly one of the arcs and the identity to the others. If z is any ordering of C4 , then δ(z) = τ . 11 Sums of commutative cycles Suppose that a diagram in a groupoid has the property that every cycle in a cycle basis is commutative. Must the diagram be strongly commutative? In [14, Thm 1], we argued that this is true using the assertion that, if a cycle z is a sum of commutative cycles, then z also must commute. We use Vogt’s basis (see (8) and the paragraph preceding) to show that the sum of commutative cycles can be a cycle which does not commute. Make the graph G into a digraph D by orienting the hexagon in counter-clockwise order, and similarly orienting the three edges of the inscribed triangle 135 35 214 in counter-clockwise order. The digraph D, in turn, is enriched to form a diagram δ in the category C of complex vector spaces and linear isomorphisms by letting each node of the diagram be the vector space C and each of the 9 arrows be multiplication by the complex number i. Then since i4 = 1, zj commutes, j = 1, 2, 3. However, the hexagon does not commute and (the inscribed triangle) z4 also does not commute. If one reverses the orientations of the edges 35, 56, 45, 34 and replaces the previous morphisms (multiplication by i) assigned to the corresponding arcs by the morphism multiplication by −i, then for the resulting orientation D� of G and corresponding diagram δ � : D� → C, the diamonds are commutative faces but the hexagon is a noncommutative face from vertex 6 to 3. We now show that if a groupoid diagram gives the identity on two compatible cycles, then it gives the identity on the cycle which is their sum. Lemma 11.1 Commutativity is constructable for cycles of groupoid diagrams. Proof. Let δ : D → G be any diagram in a groupoid and z1 , z2 be two cycles in cyc(U (D)) intersecting in a nontrivial path P . Choose one of the two possible orderings of P as P + . Put P1 = z1 − P and P2 = z2 − P , and let P1+ and P2+ be the orderings so that all three paths proceed in parallel from the first vertex of P + to the last vertex of P + . As z1 and z2 commute, by Lemma 10.1, δ(P1+ ) = δ(P + ) = δ(P2+ ). Hence, z = z1 + z2 commutes. ✷ Theorem 11.2 Let δ : D → G be a diagram, G a groupoid, and B an rhg-basis of G = U (D). Then δ commutes if and only if for every cycle z ∈ B, δ(z) = 1. 36 215 Proof. The theorem is true for a hierarchy of depth k = 1 by induction on the number of terms in the longest well-arranged sequence for any member of the robust span, using the preceding Lemma. Now by induction on the depth of the hierarchy, again using Lemma 11.1, the theorem holds. 12 ✷ Standard diagrams in Kn The standard orientation Kn∗ of a labeled Kn has e = ij oriented as (i, j) iff i < j. This is the tournament in which there is a strict pecking order and competitions are always won by the higher-ranking team. For the standard orientation, if i < j are vertices of Kn , then the set Fi,j,n := F(Kn∗ , i, j) of all faces of Kn∗ from i to j is in one-to-one correspondence with the set of all unordered pairs of disjoint subsets S, T ⊆ {i + 1, i + 2, . . . , j − 1} where at least one of S and T is nonempty. The interior vertices of the two internally disjoint dipaths constitute S and T . Conversely, two such subsets determine the dipaths as the graph is complete and the vertices are totally ordered. Thus, the number of (i, j)-faces, for i < j is the number of edges in the graph ¯ I(P({i + 1, i + 2, . . . , j − 1}) which is the complement of the intersection graph of the family of all subsets of {i, i + 1, . . . , j}. In particular, this number is independent of n for n ≥ j. Lemma 12.1 Let i < j ≤ n. Then #Fi,j,n = (3j−i−1 − 1)/2. 37 216 Proof. Let S, T be disjoint subsets of {i + 1, i + 2, . . . , j − 1}. Let Ξ : {i + 1, i + 2, . . . , j − 1} → {0, 1, 2} send k to 0 if it is not chosen for either S or T , to 1 if it is chosen for S, and to 2 otherwise, i.e., when it is chosen for T . As the choice S = {} = T is excluded, the disjointness of S and T guarantees S and T are distinct. Hence, interchanging S with T produces an involution with no fixed points and the result follows. ✷ For instance F1,4,4 has 4 elements, {124, 134}, {14, 124}, {14, 134}, and {14, 1234} agreeing with (32 − 1)/2 from the theorem. The total number of faces of Kn∗ is the sum #F(Kn∗ ) = � 1≤i j. The indecomposable permutations of [3] are (in 1-line notation) 231, 312, 313. Let a(d) denote the number of indecomposable permutations of [d]. For d = 2, 3, 4, 5, a(d) = 1, 3, 13, 71. Further, a(d) satisfies a recursion: a(d) = d! − d−1 � i=1 i!a(d − i); (12) see sequence A003319 in [23]. Lemma 14.1 Let d ≥ 2. Then the binding number of (Q∗d , 0̄, 1̄) is the number a(d) of indecomposable permutations of [d]. Proof. By symmetry, it suffices to consider the standard 0̄-1̄-dipath corresponding to the sequence 1, 2, . . . , d of bit positions which is the identity permutation. Any other permutation σ of [d] produces a parallel 0̄-1̄-dipath, which is internally disjoint from the standard dipath if and only if σ is indecomposable. Indeed, if the two dipaths intersect before reaching 1̄, then at the first vertex where they intersect, the same set of bit-flips has occurred along both dipaths; hence, the corresponding permutation is not indecomposable. Conversely, if π|[j] is a permutation for j < d, then the dipath determined by π intersects the standard dipath in the j-th element. ✷ This proves the following result. Theorem 14.2 # (F(Q∗d )(0̄, 1̄)) = d!a(d)/2 For example, the number of 0̄-1̄-faces of Q∗3 is 9 and of Q4 156. Further, Φ(Q∗3 , 0̄, 1̄) ≡ K3 × K2 . The total number of faces of Q∗d is obtained from Theorem 14.2 by counting the cube subdigraphs. Theorem 14.3 #F(Q∗d ) = �d j=2 � � d j 2d−j j!a(j)/2. 42 221 15 The Cube Lemma and groupoids In this section, we state and prove the elementary (and well-known) lemma which plays a fundamental role. The description is kept informal here for brevity and clarity. Consider the graph formed from the 8 corners and 12 edges of a standard 3-dimensional cube, and make this into a digraph by orienting the edges, say, from left to right, top to bottom, and front to back. As a digraph, this cube has a unique source vertex (with all arrows out) and a unique target vertex (with all arrows coming in). As “C” is reserved for “cycle,” the usual notation is Q3 for the underlying graph, and we write Q∗3 for the standard (directed) 3-cube. Viewed in 3 dimensions, Q3 is a “box” with six square faces (the four sides plus top and bottom). The term “square” here just means a cycle C4 of length 4 (also written Q2 ), and we write Q∗2 consisting of two internally disjoint directed paths as shown in the figure below. • −→ • ↓ ↓ • −→ • Just as graphs can be enriched by drawing them on a surface, digraphs can have value added by placing them in a category, where the vertices become objects of the category and an arrow between two vertices becomes a morphism between the corresponding objects. This is called a “diagram” on the “scheme” of the digraph. For example, the digraph C4∗ above gives rise to diagrams of the form 43 222 a A → B ↓b d ↓c C → D If two vertices in the digraph are joined by a directed path, then there is an induced morphism between the corresponding objects of the category. When this morphism is independent of the choice of directed path between the objects, we say that the diagram “commutes.” For example, the preceding square diagram commutes iff b ◦ d = a ◦ c, where “◦” denotes composition in the category defined when the target of the first morphism is equal to the source of the second morphism. Recall that a morphism e is called an epimorphism provided that e ◦ f = e ◦ g ⇒ f = g, where we write composition algebraically from left to right (so e ◦ f means do e first, then f ). For example, for the category of sets and functions, epimorphisms are just the surjective (“onto”) functions. By virtue of the categorical notion of duality which reverses all of the arrows, one obtains the definition of monomorphisms which are cancellable post-composition, and correspond to the injective (“one-to-one”) functions. The following little result is key to our arguments. We give it first as explicitly stated in Mitchell [21]. Lemma 15.1 (Cube Lemma) Let C be any category. If δ : Q3 → C is any diagram, if every square face commutes except possibly for the top, and if the morphism e to the source node of the top square is an epimorphism, then the top square must also commute. 44 223 Proof. Preceding the composition of the two dipaths of the top square by e yields two length-3 dipaths which are equal by a simple “diagram-chasing” argument utilizing commutativity of the other five squares. Since e is an epimorphism, the top square is commutative. ✷ The categorical dual of this lemma says that the bottom square must commute if the morphism from its target object is a monomorphism and the other squares commute. Furthermore, each square of the cube corresponds to top or bottom under the cube’s three-fold directional symmetry. A groupoid is a category where every morphism has an inverse and hence is both a monomorphism and an epimorphism. Therefore, in a groupoid category, one has the following more convenient symmetric form [14] of the Cube Lemma: In a groupoid diagram on the scheme of the standard 3-cube, if any five of the six squares are commutative, then the sixth square must also commute. We use groupoids as the co-domain of diagrams to apply cancellation arguments to all pairs of parallel paths. Groupoids are a topic of current research in several rather diverse areas - for example, within topology [3], Lie theory [30], networks and biology [9], [28], and the theory of ribbon categories [25]. Another attractive property of groupoids is their capacity to model the notion of reversible computation and, in particular, of quantum computation; see, e.g., [2], [29], [4]. 16 Commutativity in hypercubes In this section, we study the connection between commutativity of some faces in hypercubes. By Lemma 7.3, every square in the graph Qd corresponds to a 45 224 face of length 4 in Q∗d . Hence, K(Qd ) ⊆ S(Qd ) = F4 (Q∗d ) ⊆ F(Q∗d ), where Fr (D) := set of faces of D with length r. Now let δ : Q∗d → C be any diagram. Consider the following three state- ments, each of which is implied by the next. Every face in K(Qd ) commutes with respect to δ. (13) Every square of Q∗d commutes with respect to δ. (14) Every face of Q∗d commutes with respect to δ. (15) We will show that (14) and (15) are equivalent, while (13) and (14) are equivalent if C is a groupoid. The first theorem is from [14]. For the reader’s convenience, we repeat the brief argument. A different proof is given in the next section. Theorem 16.1 If δ : Q∗d → G with G a groupoid, (13) ⇒ (14); that is, if every special square commutes, then every square commutes. Proof. By the decomposition (9), squares in Qd are of three types - from the bottom, from the sides, and from the top. The first two types are already in the recursive basis K(Qd ), while every square from the top of the d-cube is the top of a 3-cube whose bottom and sides are in K(Qd ). By the Cube Lemma (Lemma 15.1), such squares must also be commutative. ✷ The next theorem is also from [14]. The proof-sketch given there used the fact that every permutation is a composition of transpositons, but the argument actually needs these transpositions to be of adjacent symbols in the permutation. 46 225 To give the proof, we introduce some convenient ad hoc notation. Each arc in the standard directed d-cube Q∗d corresponds to incrementing exactly one of the d coordinates (from 0 to 1). Let εj denote the standard unit vector of length d with 1 in coordinate j and 0 everywhere else. Then a typical arc a in Q∗d is of the form a = (v, v + εj ) for some vertex vector v which has vj = 0. When v = 0̄, we denote the arc a = (v, v + εj ) merely by εj , where context makes clear the distinction. If σ is any sequence of arcs which constitutes a dipath, we write P (σ) for the corresponding dipath. By Lemma 7.3 the permutations of [k] are in one-to-one correspondence with the dipaths from 0̄ to 1̄ in Qk . We write P (σ) for this dipath. For any dipath P in a digraph D and any diagram δ : D → C, write δ(P ) for the induced morphism in C. The following lemma says that the morphism induced by any permutation (that is, by the dipath in the cube which corresponds to the permutation) is unchanged if the permutation is composed with any transposition of adjacent terms - i.e., δ(P (η) = δ(P (η1 , . . . , ηi−1 , ηi+1 , ηi , ηi+2 , . . . , ηk )). Lemma 16.2 Let k ≥ 2 be a positive integer and let η be any permutation of [k]. Let δ : Qk → C be any diagram on the scheme Qk . Suppose that 1 ≤ i ≤ k − 1 and that δ(P (ηi , ηi+1 ) = δ(P (ηi+1 , ηi ). Then for the transposition τ = (i, i + 1), we have δ(P (η) = δ(P (τ ◦ η). 47 226 Proof. By definition, δ(P (τ ◦ η) = δ(P (η1 , . . . , ηi−1 ) ◦ δ(P (ηi , ηi+1 ) ◦ δ(P (ηi+2 , . . . , ηk )). Using the assumption, we obtain the desired conclusion. ✷ We use this lemma repeatedly in the proof of the following theorem. Theorem 16.3 For every diagram δ : Q∗d → C with d ∈ N, (14) ⇒ (15); that is, if every square commutes, then so does every face. Proof. Let F be any face of δ. Then there exist (i) a subset I = {i1 , . . . , im } ⊆ [d] with 2 ≤ m ≤ d, (ii) vertices v, w ∈ V (Qd ) with v(i) = 0 ∀i ∈ I, w(i) = 1 ∀i ∈ I, with v(j) = w(j) ∀j ∈ [d] \ I, and (iii) permutations π and σ of I such that F = P (π) ∪ P (σ), where P (π) := P (v, v + επ(1) , v + επ(1) + επ(2) , . . . , w) and similarly for σ. Let π ◦ σ −1 = τ1 ◦ τ2 · · · ◦ τn be any factorization of the permutation π ◦ σ −1 into adjacent transpositions. Then using Lemma 16.2 n times, δ(P (σ)) = δ(P (τn ◦ σ)) = δ(P (τn−1 ◦ τn σ)) = · · · = δ(P (τ1 ◦ · · · ◦ τn ◦ σ)). But τ1 ◦ · · · ◦ τn ◦ σ = π ◦ σ −1 ◦ σ so δ(P (σ)) = δ(P (π)). Hence, every face of δ commutes if every square of δ commutes. 48 ✷ 227 17 Threshold for commutativity For all three of the test graph families, Kn , Kp,q , Qd , we built up commutativity beginning with the minimal cycles, triangles and squares, respectively. Here we show that for groupoid diagrams on the scheme of such a graph, there is a threshold value such that if at least that number of minimal cycles commute, then all cycles must commute. that is, the number of noncommuting cycles can’t be smaller than a certain value. The results follow from our isolation theorems. Theorem 17.1 Let n ≥ 4 and let G be a groupoid. If δ : Kn → G is a diagram and if at least commutative. � � n 3 − n + 3 cycles in T (Kn ) commute w.r.t. δ, then δ is strongly Proof. Suppose that at least � � n 3 − n + 3 triangles in T (Kn ) commute w.r.t. δ. If all triangles commute, we’re done. Otherwise, by (2), there must be a nonempty set S of at most n − 3 cycles which don’t commute. But then by Theorem 8.2 there is a K4 -subgraph of Kn which contains exactly one, say T ∈ S, of the noncommuting triangles. Since the triangles robustly span K4 , the commutativity of the other 3 triangles in K4 contradicts the supposed noncommutativity of T . Hence, δ is strongly commutative. ✷ Hence, the smallest number of noncommutative faces which can block commutativity, the blocking number, is n − 2 for Kn . It follows from the theorems below that the blocking number of Kp,q is p + q − 3 and the blocking number of Qd is d − 1. Theorem 17.2 Let p ≥ 2, q ≥ 2, p + q ≥ 5, and let G be a groupoid. If δ : Kp,q → G is a diagram and if at least � �� � p 2 q 2 − (p + q) + 4 cycles in S(Kp,q ) commute w.r.t. δ, then δ is strongly commutative. 49 228 Theorem 17.3 Let d ≥ 3 and let G be a groupoid. If δ : Qd → G is a diagram and if at least 1 + (d − 2)2d−1 − d + 2 = (d − 2)2d−1 − d + 3 cycles in S(Qd ) commute w.r.t. δ, then δ is strongly commutative. 18 Digraph embedding and diagram extension Some digraphs can be embedded in our standard digraph families. Of course, any graph embeds in a complete graph, but not every digraph embeds in Kn∗ (for instance, it must have no dicycles). An odd cycle can’t embed in a bipartite graph, so it is rather natural to allow subdivision of the graph before embedding, and this applies just as well to digraphs. The following theorem was proved in [11, Thm. 4.1]. Theorem 18.1 (Hechler and Kainen, 1974) Let D be any acyclic digraph with n vertices. Then D has a subdivision D� which is isomorphic to a subdigraph of Q∗2n . Moreover, for every n, there are acyclic digraphs with 9n vertices which do not have subdivisions embeddable in a cube of dimension less than 10n. (This follows from [11, Thm. 3.7, Lemma 4.2], using the fact that Lemma 4.2 there is actually an equivalence.) Hence, one could at best replace 2 by 10/9 in any improvement of the above result. However, for particular digraphs, one can possibly obtain subdivisions embedding in cubes of much lower dimension e.g., if D consists of two internally-disjoint paths of length d so D has n = 2d vertices, then D embeds in a cube of dimension d. 50 229 How can one extend hypercube embeddings of subdivisions of digraphs to the enriched case of diagrams in a category C? In fact, once one has an embedding, the extension turns out to be easy. A subdivision of a diagram is obtained by replacing some of the morphisms by sequences of pairwiseconsecutively-composable morphisms; it is called a parsimonious subdivision if at most one non-identity morphism in the diagram is assigned to some arc in the dipath replacing each morphism. If D is a subdigraph of Q∗d and δ : D → C is a diagram, then a diagram δ̂ : Q∗d → C extends δ if δ̂|D = δ. Extension itself is trivial; it becomes interesting and nontrivial when the diagram and its extension are required to be commutative. 18.1 The groupoid case If a diagram δ : G → G is strongly commutative, then all v-w-paths induce the same G-morphism which we denote by δ(v, w). Let δ(v, v) be the identity on v. The extension problem for a diagram in a groupoid whose underlying graph is a subgraph of some given graph is straight-forward. Moreover, one can achieve this using the least possible number of nonidentity morphisms. If one has a strongly commutative diagram, then by Theorem 18.1 there is an extension of the diagram (or of some subdivision) to a hypercube. Having a groupoid category is crucial for the argument which follows. An infiltrating forest for a subgraph G in a graph Γ is a set of trees contained in Γ, each containing a single vertex from V (G) such that every vertex of Γ belongs to one of the trees. For a graph H, �H� := #EH and |H| := #V H. Lemma 18.2 Let F be the set of edges in an infiltrating forest for G in Γ. Then #F = �Γ(F )� = |Γ| − |G|. 51 230 Proof. Each edge of Γ not in G or F , when added to the subgraph of Γ determined by G ∪ F ∪ set of previously selected edges, causes the cyclomatic number to increase by 1. Since the total increase is β(Γ) − β(G), we have �Γ� − �G� − #F = �Γ� − |Γ| + 1 − (�G� − |G| + 1), so #F = |Γ| − |G|. ✷ Theorem 18.3 (Embedding Theorem for Diagrams) Let G ⊂ Γ be a subgraph, let F be any infiltrating forest for G in Γ, and δ : G → G a strongly commutative diagram. Then there is a strongly commutative diagram δ̄ : Γ → G which extends δ using only identity morphisms on F . Moreover, each edge xy in Γ not in G ∪ F is assigned the corresponding morphism δ(v, w), where v and w are the vertices of V (G) to whose trees x and y belong. Proof. We consider an arbitrary cycle z in cyc(Γ). Suppose the cycle contains no edges in G or F and is given by the sequence x1 , x2 , . . . , xr ∈ V Γ. Then there is a corresponding sequence v1 , v2 , . . . , vr ∈ V G, where the vi may not all be distinct. As z is a cycle, the sequence of vi must be a closed walk in G. As δ is strongly commutative, the composition of each cycle is the identity; hence, so is the composition of each closed walk. Therefore, z is commutative with respect to δ̄. 18.2 ✷ Diagrams with no hypercube extension When the ambient category is not a groupoid, such diagram extensions may not exist. 52 231 Theorem 18.4 There exists d ∈ N, a digraph D which is a subdigraph of Qd , a finite category F, and a diagram δ : D → F such that δ is commutative, but there is no commutative diagram δ̂ : Q∗d → F which extends δ. Proof. Take d = 2. Let D be an orientation of K1,2 with no length-2 dipath. Then D has a unique embedding in Q∗2 . Without loss of generality, we take D to be the digraph with vertices v1 , v2 , v3 and arcs (v2 , v1 ), (v2 , v3 ). Now consider a category F which has four distinct objects A, B, U, V . Assume that F(A, B) = {a}, F(A, U ) = {b}, F(B, V ) = {x}, F(U, V ) = {y}, and F(A, V ) = {α, β}, with F(X, X) = {1X } for all X ∈ Obj(F). Suppose ax = α, by = β, where α �= β. Then the diagram δ : D → F given by δ(v2 , v1 ) = a, δ(v2 , v3 ) = b is commutative (vacuously as it has no cycles) but the unique diagram in F which extends δ to the cube Q∗2 is not commutative. ✷ With a bit more work, the same method applies to a nontrivially commutative diagram. Let D be the digraph which has two parallel, internally disjoint dipaths R, S, T, U and R, X, U joining the two vertices R and U , where both dipaths are oriented from R to U . Now subdivide the arc RX as the dipath R, Y, X, and consider the corresponding digraph D� which includes all six vertices. We can embed D� into the cube Q3 by the following vertex function f : R �→ (000), S �→ (100), T �→ (101), U �→ (111), Y �→ (001), X �→ (011) and this can be extended to a commutative diagram in some category F whose objects will be denoted using the corresponding binary triple from the standard parameterization of the vertices of Q3 . We use the notation [000, 100] := F((000), (100)), etc. 53 232 The category F is required to satisfy the following conditions: [000, 100], [100, 101], [101, 111], [000, 001], [001, 011], [011, 111] are all singletons. If δ : D� → F is the commutative F-diagram obtained by requiring that the dipath of length 3 maps to the sequence of morphisms a, b, c contained in [000, 100], [100, 101], [101, 111], resp. and the dipath of length 2 maps to the sequence of morphisms d, 1, e contained in [000, 001], [001, 011], [011, 111], resp., with 1 denoting the identity map, so the F-objects (001) and (011) are the same. By commutativity of δ we require that both sequences of morphisms have the same composition in F; that is, abc = de = d1e. Suppose now that in F we also have [000, 010], [010, 011] are both singletons. Then as in the first example, if [000, 011] = {α, β}, the composition of the unique morphisms in [000, 010] and [010, 011] is α while the composition of d, e is β �= α, then there is no commutative extension of δ to Q3 (in fact, not even to the subdigraph determined by the 8 arcs of the cube listed here). Extending a commutative diagram with respect to a digraph embedding may not be possible, but as the cubes are nested, if there is an embedding of D in Qd , then there are embeddings of D into all hypercubes of dimension ≥ d. One might take a more “spread out” embedding of D in the hypercube. In that case, it seems possible that the nonidentity morphisms of the hypercube diagram could be so mutually far apart in the hypercube that a commutative extension to the hypercube. That is, perhaps one can achieve diagram extensions if the hypercube has sufficiently large dimension. One further consideration is the choice of subdivision if one first starts with a commutative diagram and the goal is to extend an embedded subdivision to a larger digraph. 54 233 19 Cycles and commutativity as biology Arthur Winfree’s wonderful book, The Geometry of Biological Time, concerned the influence of topology on the possibilities of “phase-resetting” of the internal clock which governs various biological processes. The EV-theory moves from one clock to many interrelated ones. As biology is certainly not a closed system, one can’t expect an organism to ever return to exactly the same state. Once approximate cycles are admitted, however, the periodicity depends on the tolerance chosen. In fact, there are many simultaneously active periodic pathways in an organism - from rotational modes of nuclei and molecules, to cell growth, and sleep-wake cycles in dreaming. It is rather natural to look at these cycles as built up hierarchically. But then one needs to ensure that multiple routes (unknown in advance) must provide comparable results. Comparable could mean equal up to some equivalence. For instance, if myths are viewed as mechanisms to communicate from the racial unconscious through a set of stylized behaviors and scenarios, then Levy-Strauss’s research shows that the spatially parallel routes afforded by distinct cultures provide agreement up to some notion of polarity, with spatial contiguity corresponding to switches. In dynamical systems, one can close non-repeating trajectories at points of close self-approach. This is done, for instance, in the Kolmogorov-ArnoldMoser Theorem, where almost periodic motion converges to the periodic. In knot theory, there is a theorem that knots of a given complexity cannot be approximated by strings with too large a thickness. For instance, a knot made with string of thickness more than 1/12 of its length must be the unknot. In the theory considered above, we find that the collective commutativity 55 234 of a sufficient set of minimal cycles forces the commutativity of all cycles. In our nice regular example graphs such results hold and by the Embedding Theorem, they also hold for diagrams whose digraphs can be topologically embedded in a nice graph. An opposite instance is also defined above. If a sufficiently small set of minimal cycles is suspected of failure, then the diagram must commute! In addition to holding for our test graphs, the result holds for digraphs topologically embedded in them. Such a scenario, where only a relatively few minimal cycles are in question could occur if one had a quantum computer which simultaneously checked all cycles and which was infallible in affirming commutivity for a cycle but which could answer ”False” for some small number of cycles due to either noise or to failure of a heuristic within the time specified. Do such testing mechanisms occur within biology? Could thresholds exist so that error below the threshold is ignored, while error above threshold triggers a control process? We think that the idea of implementing general diagrams within either the standard ordered simplex Kn∗ or especially the standard ordered hypercube Q∗d would give organisms a superior tool-box for modeling disparate phenomena with an overall efficient investment of resources. Thus, we hope that the theory of robustly hierarchically generating sets of cycles will be helpful in understanding the complexly interwoven “geometry of biological time” of Ehresmann and Vanbremeersch. References [1] Bernhart, F. R. & Kainen, P. C., On the book thickness of a graph, J. Comb. Th., Ser. B, 27 (1979) no. 3, 320–331. 56 235 [2] C. H. Bennett, Logical reversibility of computation, IBM J. Res. November 1973, 525–532. [3] R. Brown, From groups to groupoids: A brief survey, Bull. London Math. Soc. 19 (1987) 113–134 [4] D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. Royal Soc. of London A 400 (1985) 97–117. [5] Ehresmann, C., Oeuvres Completes, Univ.-de-Picardie, 2000 (4 volumes). [6] Ehresmann, A. C., Vanbremeersch, J.-P., Memory evolutive systems: hierarchy, emergence, cognition. Elsevier, Amsterdam, 2007. [7] Erdős, P., Fajtlowicz, S., Hoffman, A. J., Maximum degree in graphs of diameter 2, Networks 10 (1980) 87–90. [8] Georgakopoulos, A., and Sprűssel, P. Geodesic topological cycles in locally finite graphs. [9] Golubitsky, M., Stewart, I., Nonlinear dynamics of networks: The groupoid formalism, Bull. AMS 43(3) (2006) 305–364. [10] Harary, F., Graph Theory, Addison-Wesley, Reading, MA, 1970. [11] Hechler, S. H., Kainen, P. C., Immersion of digraphs in cubes, Israel J. Math. 18 (1974) 221–233. [12] Kainen, P. C. Some recent results in topological graph theory, in Graphs and combinatorics (Proc. GWU Conf., 1973), Bari, R. 57 236 A. Harary, F., Eds., Springer Lecture Notes in Math. 406, Berlin, 1974, pp. 76–108. [13] Kainen, P. C., Mathematical cognition, J. of Evolution and Cognition, 4 (1998) 81–89. [14] Kainen, P. C., On robust cycle bases, in Proc. of 9th Quadrennial Conference on Graph Theory, Combinatorics, Algorithms and Applications, Ed. by Y. Alavi, D. Jones, D. R. Lick, and J. Liu, Kalamazoo, MI, 4–9 June, 2000; Electronic Notes in Discrete Math. 11 art. no. 38, 1–8. [15] Kainen, P. C., Cahiers de topologie et géometrie différentielle catégoriques XLIII (2002) 13 –20. [16] Kainen, P. C., On the Ehresmann-Vanbremeersch theory and mathematical biology, Axiomathes (2009) 19:225–244. [17] Klemm, K., Stadler, P. F., A note on fundamental, non-fundamental, and robust cycle bases, Discr. Appl. Math. 157 (2009) 2432–2438. [18] Lawvere, F. W., Schanuel, S. H., Introduction to Categories in Continuum Physics, Springer LNM 1174, 1986, pp. 1-16. [19] Lovasz, L. Problem 11, Combinatorial Structures and their Applications, Gorden and Breach (1970). [20] Mac Lane, S., Categories for the Working Mathematician, Springer. [21] Mitchell, B., Category Theory, Academic Press, NY, 1967. 58 237 [22] Moon, J. W., Topics on Tournaments, Holt, Rinehard and Winston, NY, 1968. [23] Online Encyclopedia of Integer Sequences, http: [24] Ostermeier, P.-J., et al., A note on quasi-robust cycle bases, Ars. Math. Contemp. 2 (2009) 231–240. [25] Reshnikov and Turaev?, Ribbon categories?, AMS, 2005? [26] Shields, I., Shields, B. J., Savage, C. D., An update on the middle levels problem, Discrete Math. 309 (2009) 5271–5277. [27] Spanier, E. H., Algebraic topology, McGraw-Hill, NY, 1966. [28] Stewart, I., Golubitsky, M., and Pivato, M., Symmetry groupoids and patterns of synchrony in coupled cell networks, SIAM J. Appl. Dyn. Syst., 2:4 (2003) 609–646. [29] Toffoli, T., Reversible computing, MIT/LCS/TM-151, preprint from http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM151.pdf [30] Weinstein, A., Groupoids: Unifying internal and external symmetry, Notices A.M.S. 43:7 (1996) 744–752. 59