ELIMINATION OF MULTIPLE ARROWS AND SELF-CONNECTIONS IN COUPLED CELL NETWORKS

A coupled cell network is a finite directed graph in which nodes and edges are classified into equivalence classes. Such networks arise in a formal theory of coupled systems of differential equations, as a schematic indication of the topology of the coupling, but they can be studied independently as combinatorial objects. The edges of a coupled cell network are "identical" if they are all equivalent, and the network is "homogeneous" if all nodes have isomorphic sets of input edges. Golubitsky et al. [2005] proved that every homogeneous identical-edge coupled cell network is a quotient of a network that has no multiple edges and no self-connections. We generalize this theorem to any coupled cell network by removing the conditions of homogeneity and identical edges. The problem is a purely combinatorial assertion about labeled directed graphs, and we give two combinatorial proofs. Both proofs eliminate self-connections inductively. The first proof also eliminates multiple edges inductively, the main feature being the specification of the inductive step in terms of a complexity measure. The second proof obtains a more efficient result by eliminating all multiple edges in a single construction.