Flex complexes of graphs

Abstract In this paper, we study a new construction which associates a combinatorial cubical complex $$\texttt {Flex}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Flex</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to an arbitrary undirected simple graph G . The vertices of $$\texttt {Flex}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Flex</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> are indexed by all possible orientations of the edges of G . The cells of $$\texttt {Flex}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Flex</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 $$\texttt {Flex}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Flex</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 $$\texttt {Flex}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Flex</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 $$\texttt {Flex}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Flex</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.