View source for Manifold crystallization

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 146 formulas, 146 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
Coloured graphs (and crystallizations are a special class of them; cf. also [[Graph colouring|Graph colouring]]) constitute a nice combinatorial approach to the topology of piecewise-linear manifolds of any dimension. It is based on the facts that an edge-coloured graph provides precise instructions to construct a [[Polyhedron|polyhedron]], and that any piecewise-linear manifold (cf. [[Topology of manifolds|Topology of manifolds]]) arises in this way. The original concept is that of a contracted triangulation, due to M. Pezzana [[#References|[a9]]], which is a special kind of dissection of a [[Manifold|manifold]] yielding, in a natural way, a minimal atlas and a combinatorial representation of it via coloured graphs.

The graphs, considered in the theory, can have multiple edges but no loops. Given such a [[Graph|graph]] $G$, let $V ( G )$ and $E ( G )$ denote the vertex set and the edge set of $G$, respectively. An $( n + 1 )$-coloured graph is a pair $( G , c )$, where $G$ is regular of degree $n$ and $c$ is a mapping (the edge-colouring) from $E ( G )$ to $\Delta _ { n } = \{ 0 , \dots , n \}$ (the colour set) such that incident edges have different colours. The motivation for this definition is that any $( n + 1 )$-coloured graph encodes an $n$-dimensional complex $K ( G )$ constructed as follows. Take an $n$-simplex $\sigma ( x )$ for each vertex $x$ of $G$, and label its vertices and its $( n - 1 )$-faces by the colours of $\Delta _ { n }$ in such a way that vertices and opposite $( n - 1 )$-faces have the same label. Then each coloured edge of $G$ indicates how to glue two $n$-simplexes along one of their common $( n - 1 )$-faces (the colour says which). More precisely, if $x$ and $y$ are vertices of $G$ joined by an edge coloured $\alpha \in \Delta _ { n }$, then identify the $( n - 1 )$-faces of $\sigma ( x )$ and $\sigma ( y )$ labelled by $\alpha$, so that equally labelled vertices are identified together. Clearly, $K ( G )$ is not, in general, a [[Simplicial complex|simplicial complex]] (two simplexes may meet in more than a single subsimplex), but it is a pseudo-complex, i.e. a ball complex in which each $h$-ball, considered with all its faces, is abstractly isomorphic to an $h$-simplex.

The pair $( G , c )$ is called a crystallization of a closed connected piecewise-linear $n$-manifold $M$ if the polyhedron underlying $K ( G )$ is piecewise-linearly homeomorphic to $M$, and $K ( G )$ has exactly $n + 1$ vertices (or, equivalently, $K ( G )$ is a contracted triangulation of $M$). The existence theorem of the theory says that any closed connected piecewise-linear $n$-manifold $M$ can be represented by a crystallization $( G , c )$ in the sense made precise above [[#References|[a9]]]. This result can be extended to piecewise-linear manifolds with non-empty boundary and to piecewise-linear generalized (homology) manifolds by suitable modifications of the definition of crystallization. So, piecewise-linear manifolds can be studied through graph theory. Unfortunately, there are many different crystallizations representing the same manifold. However, two crystallizations represent piecewise-linear homeomorphic manifolds if and only if one can be transformed into the other by a finite sequence of elementary moves (i.e. cancelling and/or adding so-called dipoles) [[#References|[a7]]]. It follows that every topological invariant of a closed piecewise-linear manifold $M$ can be directly deduced from a crystallization of $M$ via a graph-theoretical algorithm.

Below, a few such invariants are indicated; see [[#References|[a1]]], [[#References|[a6]]], [[#References|[a8]]] for more results and for further developments of crystallization theory.

==Orientability.==
A closed piecewise-linear $n$-manifold $M$ is orientable if and only if a crystallization of $M$ is bipartite (cf. also [[Graph, bipartite|Graph, bipartite]]), i.e. a graph whose vertex set can be partitioned into two sets in such a way that each edge joins a vertex of the first set to a vertex of the second set.

==Connected sums.==
Let $M$ and $M^{\prime}$ be closed connected orientable piecewise-linear $n$-manifolds, and let $G$ and $G ^ { \prime }$ be crystallizations of them. A crystallization for the connected sum $M \# M ^ { \prime }$ can be obtained as follows. Match arbitrarily the colours of $G$ with those of $G ^ { \prime }$, and take away arbitrarily a vertex for either graph. Then past together the free edges with colours corresponding in the matching. This yields the requested crystallization since, by the disc theorem, the connected sum can be performed by hollowing out the two $n$-simplexes represented by the deleted vertices. The two permutation classes of matching correspond to an orientation-preserving, respectively an orientation-reversing, homeomorphism of the boundaries.

==Characterizations.==
An immediate characterization of coloured graphs representing piecewise-linear manifolds is provided by the following criterion. An $( n + 1 )$-coloured graph $( G , c )$ encodes a closed piecewise-linear $n$-manifold $M$ if and only if any connected component of the partial subgraphs obtained from $G$ by deleting all identically coloured edges, for each colour at a time, represents the standard piecewise-linear $( n - 1 )$-sphere. See [[#References|[a1]]], [[#References|[a6]]], [[#References|[a8]]] for other combinatorial characterizations of coloured graphs encoding low-dimensional manifolds.

==Homotopy and homology.==
A presentation of the [[Fundamental group|fundamental group]] of a closed connected piecewise-linear $n$-manifold $M$ can be directly deduced from its crystallization $G$ as follows. Choose two colours $\alpha$ and $\beta$ in $\Delta _ { n }$, and denote by $x_{1} $… $x _ { r }$ the connected components, but one, of the $( n - 1 )$-subgraph obtained from $G$ by deleting all edges coloured $\alpha$ or $\beta$ (the missing component can be chosen arbitrarily). Of course, the connected components of the complementary $2$-subgraph are simple cycles with edges alternatively coloured $\alpha$ and $\beta$. If $M$ is a surface, let $y_1$ be the unique cycle as above. If the dimension of $M$ is greater than $2$, denote by $y _ { 1 } , \dots , y _ { s }$ these cycles, all but one arbitrarily chosen, and fix an orientation and a starting point for each of them. For each $y_j$, compose the word $w_j$ on generators $x_{i}$ by the following rules. Follow the chosen orientation starting from the chosen vertex, and write down consecutively every generator met with exponent $+ 1$ or $- 1$ according to the colour $\alpha$ or $\beta$ of the edge leading to the generator. A presentation of the fundamental group of $M$ has now generators $x _ { 1 } , \dots , x _ { r }$, and relators $w _ { 1 } , \dots , w _ { s }$. A homology theory for coloured graphs was developed in [[#References|[a5]]], where one can find the graph-theoretical analogues to exact homology sequences, cohomology groups, product, duality, etc. and the corresponding topological meanings.

==Numerical invariants.==
Let $( G , c )$ be a crystallization of a closed connected piecewise-linear $n$-manifold $M$. For each cyclic permutation $\epsilon = ( \epsilon_{0} , \dots , \epsilon _ { n } )$ of $\Delta _ { n }$, there exists a unique $2$-cell imbedding (called regular; cf. also [[Graph imbedding|Graph imbedding]]) of $G$ into a closed surface $F$ (which is orientable or non-orientable together with $M$) such that its regions are bounded by simple cycles of $G$ with edges alternatively coloured $\epsilon_{i}$ and $\epsilon_{i + 1}$ (where the indices are taken modulo $n + 1$). The regular genus of $G$ is defined as the smallest integer $k$ such that $G$ regularly imbeds into the closed (orientable or non-orientable) surface of genus $k$. The regular genus of $M$ is then the smallest of the regular genera of its crystallizations. A typical problem is to find relations between the regular genus of a manifold and the piecewise-linear structure of it. The topological classification of all closed $4$-manifolds up to regular genus six can be found, for example, in [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]]. In particular, if the regular genus could be proved to be additive for connected sums in dimension $4$, then this would imply the piecewise-linear generalized Poincaré conjecture in that dimension. Other numerical invariants of piecewise-linear manifolds arising from crystallizations, as for example many types of complexities, can be found in [[#References|[a1]]], [[#References|[a5]]].

==Geometric structure.==
An $( n + 1 )$-coloured graph $( G , c )$ is regular if its automorphism group $\operatorname { Aut } ( G , c )$ acts transitively on $V ( G )$ (cf. also [[Graph automorphism|Graph automorphism]]). $( G , c )$ is locally regular if all the cycles of $G$, with edges alternatively coloured $\alpha$ and $\beta$, have the same number of vertices, for any $\alpha , \beta \in \Delta$. If a locally regular graph $( G , c )$ encodes a closed connected piecewise-linear $n$-manifold $M$, then there is a regular graph $( \tilde { G } , \tilde { c } )$ such that $K ( \tilde{ G } )$ is isomorphic to a tessellation (cf. also [[Geometry of numbers|Geometry of numbers]]; [[Dirichlet tesselation|Dirichlet tesselation]]) by geometric $n$-simplexes of $X$, where $X$ is either the hyperbolic $n$-space, the Euclidean $n$-space or the $n$-sphere, and there is a subgroup $\Lambda \cong \pi _ { 1 } ( M )$ of $\operatorname { Aut } ( \tilde { G } , \tilde{c} )$ acting freely on $X$ such that $( \tilde { G } , \tilde{c} ) / \Lambda$ is isomorphic to $( G , c )$.

====References====
<table><tr><td valign="top">[a1]</td> <td valign="top">  J. Bracho,   L. Montejano,   "The combinatorics of coloured triangulations of manifolds"  ''Geom. Dedicata'' , '''22'''  (1987)  pp. 303–328</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  A. Cavicchioli,   "A combinatorial characterization of $\mathbf{S} ^ { 3 } \times \mathbf{S} ^ { 1 }$ among closed $4$-manifolds"  ''Proc. Amer. Math. Soc.'' , '''105'''  (1989)  pp. 1008–1014</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  A. Cavicchioli,   "On the genus of smooth $4$-manifolds"  ''Trans. Amer. Math. Soc.'' , '''331'''  (1992)  pp. 203–214</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  A. Cavicchioli,   M. Meschiari,   "On classification of $4$-manifolds according to genus"  ''Cah. Topol. Géom. Diff. Cat.'' , '''34'''  (1993)  pp. 37–56</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  A. Cavicchioli,   M. Meschiari,   "A homology theory for colored graphs"  ''Discrete Math.'' , '''137'''  (1995)  pp. 99–136</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  A. Cavicchioli,   D. Repovš,   A.B. Skopenkov,   "Open problems on graphs arising from geometric topology"  ''Topol. Appl.'' , '''84'''  (1998)  pp. 207–226</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  M. Ferri,   C. Gagliardi,   "Crystallization moves"  ''Pacific J. Math.'' , '''100'''  (1982)  pp. 85–103</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  M. Ferri,   C. Gagliardi,   L. Grasselli,   "A graph-theoretical representation of PL-manifolds: A survey on crystallizations"  ''Aequat. Math.'' , '''31'''  (1986)  pp. 121–141</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  M. Pezzana,   "Sulla struttura topologica delle varietà compatte"  ''Atti Sem. Mat. Fis. Univ. Modena'' , '''23'''  (1974)  pp. 269–277</td></tr></table>