Flex complexes of graphs

Abstract In this paper, we study a new construction which associates a combinatorial cubical complex Flex (G) Flex (G) to an arbitrary undirected simple graph G. The vertices of Flex (G) Flex (G) are indexed by all possible orientations of the edges of G. The cells of Flex (G) Flex (G) are the sets of independent flexes, where a flex is a simultaneous change of orientations of the edges adjacent to a certain sink or a certain source in G. Accordingly, we call Flex (G) Flex (G) the flex complex of the graph G. Our focus is on studying topology and combinatorics of the flex complexes. The main topological theorem says that for an arbitrary graph G, the flex complex Flex (G) Flex (G) is homotopy equivalent to a disjoint union of tori. We also provide formulae for the number of these tori. Furthermore, we prove a much more precise combinatorial result saying that when G is connected, every connected component of Flex (G) Flex (G) is either a collapsible cubical complex, or can be collapsed to a cycle whose length is equal to the number of vertices of G. We shall provide a combinatorial enumeration for the components of both types. Our study is motivated by the beauty and naturality of the graph construction, as well as by the mathematical modeling of the network evolution.