Simplicial Complexes
====================

The module supports creation of simplicial complexes from lists of faces, as
well as a few preprogrammed complex types. Furthermore, several standard
techniques for modifying and recombining simplicial complexes are available.

.. magma:function:: SimplicialComplex(f)
   :input_types: SeqEnum[SetEnum]
   :output_types: SmpCpx
   :label: SimplicialComplex_SeqEnum_SetEnum

   Constructs an abstract simplicial complex with the faces in the list :math:`f`.
   The argument should be a sequence of sets. There is no requirement on the type
   of the elements in the face sets, however several of the constructions require
   the sets to have integer entries. See for automated renumbering of the face set
   elements.

.. magma:example:: Example: construct
   :label: construct

   We give a simplicial complex by listing the facets, or also redundant faces if
   we want to. We can view the facets (faces not included in any other faces) of
   the complex, or by giving the ``:Maximal`` output flag, we can view all faces.

   .. code-block:: magma

      > sc := SimplicialComplex([{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,5},{2,5}]);
      > sc;
      Simplicial complex
      [
      \    { 2, 3, 4 },
      \    { 1, 2, 3 },
      \    { 1, 2, 4 },
      \    { 2, 5 },
      \    { 1, 5 },
      \    { 1, 3, 4 }
      ]

      > sc:Maximal;
      Simplicial complex
      {
      \    {},
      \    { 4 },
      \    { 2, 3, 4 },
      \    { 2, 3 },
      \    { 3, 4 },
      \    { 1, 3 },
      \    { 3 },
      \    { 1 },
      \    { 1, 4 },
      \    { 1, 2, 3 },
      \    { 2 },
      \    { 1, 2 },
      \    { 1, 2, 4 },
      \    { 2, 5 },
      \    { 1, 5 },
      \    { 5 },
      \    { 2, 4 },
      \    { 1, 3, 4 }
      }

.. magma:function:: SimplicialComplex(G)
   :input_types: Grph
   :output_types: SmpCpx
   :label: SimplicialComplex_Grph

   Constructs a 1-dimensional simplicial complex isomorphic to the graph :math:`G`.

.. magma:function:: FlagComplex(G)
   :input_types: Grph
   :output_types: SmpCpx
   :label: FlagComplex_Grph

.. magma:function:: CliqueComplex(G)
   :input_types: Grph
   :output_types: SmpCpx
   :label: CliqueComplex_Grph

   Constructs a simplicial complex with an :math:`n`-simplex for each
   :math:`n`-clique in the graph :math:`G`.

.. magma:function:: Dimension(X)
   :input_types: SmpCpx
   :output_types: RngIntElt
   :label: Dimension_SmpCpx

   Returns the dimension of the highest dimensional face of the simplicial complex
   :math:`X`. Note that there is a difference between degrees and dimensions of
   faces. A face is said to have degree :math:`n` if there are :math:`n` elements
   in the face as a set, and it is said to have dimension :math:`n` if there are
   :math:`n+1` elements in the face as a set.

.. magma:example:: Example: dimension
   :label: dimension

   The recently defined simplicial complex has top dimension 2.

   .. code-block:: magma

      > Dimension(sc);
      2
      %%a> assert $1 eq 2;

.. magma:function:: Faces(X, d)
   :input_types: SmpCpx, RngIntElt
   :output_types: SeqEnum[SetEnum]
   :label: Faces_SmpCpx_RngIntElt

   Returns the faces of one degree :math:`d` of the simplicial complex :math:`X`.
   Recall that the degree of a face is the number of elements in the face as a set,
   and one more than the dimension of the face.

   The order of faces returned for each degree is also the correspondence between
   faces and the basis of the corresponding module in a chain complex constructed
   from the simplicial complex.

   If the complex does not possess any faces of the requested degree, an empty
   sequence is returned.

.. magma:example:: Example: faces
   :label: faces

   We can list faces of any degree in the defined simplicial complex.

   .. code-block:: magma

      > Faces(sc,2);
      [
      \    { 2, 3 },
      \    { 3, 4 },
      \    { 1, 3 },
      \    { 1, 4 },
      \    { 1, 2 },
      \    { 2, 5 },
      \    { 1, 5 },
      \    { 2, 4 }
      ]
      > Faces(sc,5);
      []

.. magma:function:: Facets(X)
   :input_types: SmpCpx
   :output_types: SeqEnum[SetEnum]
   :label: Facets_SmpCpx

   Returns the facets of the simplicial complex :math:`X`. The facets of a
   simplicial complex are the faces that are not themselves subsets of another
   face. This is what the normal printing mode for a simplicial complex outputs.

.. magma:example:: Example: facets
   :label: facets

   We can read the facets both by fetching the sequence of facets and by printing
   the complex as such.

   .. code-block:: magma

      > Facets(sc);
      [
      \    { 2, 3, 4 },
      \    { 1, 2, 3 },
      \    { 1, 2, 4 },
      \    { 2, 5 },
      \    { 1, 5 },
      \    { 1, 3, 4 }
      ]
      > sc;
      Simplicial complex
      [
      \    { 2, 3, 4 },
      \    { 1, 2, 3 },
      \    { 1, 2, 4 },
      \    { 2, 5 },
      \    { 1, 5 },
      \    { 1, 3, 4 }
      ]

.. magma:function:: \name{SmpCpx
   :input_types: Normalization}{Normalization}(X) : SmpCpx
   :output_types: SmpCpx

.. magma:function:: Normalization($\sim$X)
   :input_types: SmpCpx
   :label: Normalization_SmpCpx_ref

   Relabels the points (elements of the face sets) of the simplicial complex
   :math:`X` using :math:`1,2,3,\ldots`. This ensures that the simplicial complex
   is built on subsets of the integers, which is a prerequisite for several
   functions handling simplicial complexes. We call a simplicial complex on subsets
   of the integers *normalized* in this handbook.

   Note the two calling signatures of this function. The first signature copies the
   simplicial complex and returns a new complex with the desired modification,
   whereas the second signature modifies the complex in place.

.. magma:function:: Shift(X, n)
   :input_types: SmpCpx, RngIntElt
   :output_types: SmpCpx
   :label: Shift_SmpCpx_RngIntElt

.. magma:function:: Shift($\sim$X, n)
   :input_types: SmpCpx, RngIntElt
   :label: Shift_SmpCpx_RngIntElt_ref

   Shifts all integer points in the normalized simplicial complex :math:`X` by an
   offset given by :math:`n`.

   Note the two calling signatures of this function. The first signature copies the
   simplicial complex and returns a new complex with the desired modification,
   whereas the second signature modifies the complex in place.

.. magma:example:: Example: Normalize Shift
   :label: normalize-shift

   We define a simplicial complex using string labels, normalize it and then shift
   the labels.

   .. code-block:: magma

      > cpx := Boundary(SimplicialComplex([{"a","b","c"}]));
      > cpx;
      Simplicial complex
      [
      \    { c, a },
      \    { c, b },
      \    { b, a }
      ]

      > Normalization(~cpx);
      > cpx;
      Simplicial complex
      [
      \    { 1, 3 },
      \    { 2, 3 },
      \    { 1, 2 }
      ]

      > Shift(~cpx,-2);
      > cpx;
      Simplicial complex
      [
      \    { -1, 1 },
      \    { 0, 1 },
      \    { -1, 0 }
      ]

.. magma:function:: Boundary(X)
   :input_types: SmpCpx
   :output_types: SmpCpx
   :label: Boundary_SmpCpx

   Returns the simplicial complex generated by all simplexes that lie in the
   boundary of the simplicial complex :math:`X`. This can be used to easily acquire
   a simplicial complex representing the :math:`n`-sphere.

.. magma:example:: Example: boundary
   :label: boundary

   We can determine the boundary of our previously defined simplicial complex, or
   construct a 4-sphere.

   .. code-block:: magma

      > Boundary(sc);
      Simplicial complex
      [
      \    { 2, 3 },
      \    { 3, 4 },
      \    { 1, 3 },
      \    { 1, 4 },
      \    { 1, 2 },
      \    { 5 },
      \    { 2, 4 }
      ]
      > sph4 := Boundary(SimplicialComplex([{1,2,3,4,5,6}]));
      > sph4;
      Simplicial complex
      [
      \    { 1, 2, 3, 5, 6 },
      \    { 2, 3, 4, 5, 6 },
      \    { 1, 3, 4, 5, 6 },
      \    { 1, 2, 3, 4, 5 },
      \    { 1, 2, 4, 5, 6 },
      \    { 1, 2, 3, 4, 6 }
      ]

.. magma:operation:: S + T
   :input_types: SmpCpx, SmpCpx
   :output_types: SmpCpx
   :label: op_plus_SmpCpx_SmpCpx

   Returns the topological sum, or disjoint union, of two simplicial complexes.
   Requires both complexes to be normalized using .

.. magma:example:: Example: sum
   :label: sum

   We can construct a disjoint union of two circles.

   .. code-block:: magma

      > sph2 := Boundary(SimplicialComplex([{1,2,3}]));
      > sph2 + sph2;
      Simplicial complex
      [
      \    { 4, 6 },
      \    { 2, 3 },
      \    { 4, 5 },
      \    { 5, 6 },
      \    { 1, 3 },
      \    { 1, 2 }
      ]

.. magma:operation:: S eq T
   :input_types: SmpCpx, SmpCpx
   :output_types: BoolElt
   :label: op_eq_SmpCpx_SmpCpx

   Compares two simplicial complexes. Will not try to find an isomorphism, rather
   does the comparison by ensuring that the points are in the same universe and
   then doing a set comparison on the set of faces.

.. magma:example:: Example: eq
   :label: eq

   Shifting a complex, for instance, will break equality, since the labels differ.
   Furthermore, isomorphic complexes with different labels will not be equal.

   .. code-block:: magma

      > sc eq Shift(sc,2);
      false
      %%a> assert not $1;
      > sc eq Shift(Shift(sc,2),-2);
      true
      %%a> assert $1;
      > circ1 := Boundary(SimplicialComplex([{1,2,3}]));
      > circ2 := Boundary(SimplicialComplex([{"a","b","c"}]));
      > circ1 eq circ2;
      false
      %%a> assert not $1;

.. magma:function:: Product(S,T)
   :input_types: SmpCpx, SmpCpx
   :output_types: SmpCpx
   :label: Product_SmpCpx_SmpCpx

   Returns the cartesian product of two simplicial complexes. This will work on any
   complexes, since the new points will be pairs of points from the component
   complexes.

.. magma:example:: Example: product
   :label: product

   Using the two different circles from the last example, we can now construct a
   torus. If we want something less unwieldy – especially after repeated cartesian
   products – we can always normalize the resulting complexes.

   .. code-block:: magma

      > Product(circ1,circ2);
      Simplicial complex
      [
      \    { <3, b>, <1, b>, <3, c> },
      \    { <1, c>, <3, c>, <1, a> },
      \    { <2, a>, <3, b>, <3, a> },
      \    { <3, b>, <1, b>, <1, a> },
      \    { <1, b>, <2, b>, <2, c> },
      \    { <2, a>, <3, c>, <3, a> },
      \    { <1, c>, <1, b>, <3, c> },
      \    { <3, c>, <2, b>, <2, c> },
      \    { <1, c>, <1, b>, <2, c> },
      \    { <3, c>, <3, a>, <1, a> },
      \    { <2, a>, <3, c>, <2, c> },
      \    { <3, b>, <3, a>, <1, a> },
      \    { <2, a>, <1, a>, <2, b> },
      \    { <2, a>, <1, a>, <2, c> },
      \    { <1, c>, <1, a>, <2, c> },
      \    { <3, b>, <3, c>, <2, b> },
      \    { <1, b>, <1, a>, <2, b> },
      \    { <2, a>, <3, b>, <2, b> }
      ]
      > line := SimplicialComplex([{1,2}]);
      > square := Product(line,line); 
      > cube1 := Product(square,line);
      > cube2 := Product(line,square);
      > cube1 eq cube2;
      false
      %%a> assert not $1;
      > Normalization(cube1) eq Normalization(cube2);
      false
      %%a> assert not $1;
      > cube1;
      Simplicial complex
      [
      \    { <<1, 2>, 1>, <<1, 2>, 2>, <<1, 1>, 1>, <<2, 2>, 2> },
      \    { <<2, 1>, 1>, <<2, 2>, 1>, <<1, 1>, 1>, <<2, 2>, 2> },
      \    { <<1, 2>, 2>, <<1, 1>, 1>, <<1, 1>, 2>, <<2, 2>, 2> },
      \    { <<1, 2>, 1>, <<2, 2>, 1>, <<1, 1>, 1>, <<2, 2>, 2> },
      \    { <<1, 1>, 1>, <<1, 1>, 2>, <<2, 1>, 2>, <<2, 2>, 2> },
      \    { <<2, 1>, 1>, <<1, 1>, 1>, <<2, 1>, 2>, <<2, 2>, 2> }
      ]
      > Normalization(cube1);
      Simplicial complex
      [
      \    { 3, 4, 5, 8 },
      \    { 4, 5, 6, 8 },
      \    { 1, 3, 4, 5 },
      \    { 2, 4, 5, 7 },
      \    { 1, 2, 4, 5 },
      \    { 4, 5, 6, 7 }
      ]

.. magma:function:: Join(S,T)
   :input_types: SmpCpx, SmpCpx
   :output_types: SmpCpx
   :label: Join_SmpCpx_SmpCpx

.. magma:operation:: S * T
   :input_types: SmpCpx, SmpCpx
   :output_types: SmpCpx
   :label: op_times_SmpCpx_SmpCpx

   Constructs the join of two simplicial complexes. The join of two simplicial
   complexes is defined as the complex generated by faces on the form
   :math:`\{x_1,\dots,x_r,y_1,\dots,y_s\}` for :math:`\{x_1,\dots,x_r\}\in S` and
   :math:`\{y_1,\dots,y_s\}\in T`. Requires both simplicial complexes to be
   normalized.

.. magma:example:: Example: join
   :label: join

   The join of two edges is a 3-simplex.

   .. code-block:: magma

      > SimplicialComplex([{1,2}]) * SimplicialComplex([{1,2}]);
      Simplicial complex
      [
      \    { 1, 2, 3, 4 }
      ]

.. magma:function:: AddSimplex(X, s)
   :input_types: SmpCpx, SetEnum
   :output_types: SmpCpx
   :label: AddSimplex_SmpCpx_SetEnum

.. magma:function:: AddSimplex($\sim$X, s)
   :input_types: SmpCpx, SetEnum
   :label: AddSimplex_SmpCpx_SetEnum_ref

.. magma:function:: AddSimplex(X, s)
   :input_types: SmpCpx, SeqEnum
   :output_types: SmpCpx
   :label: AddSimplex_SmpCpx_SeqEnum

.. magma:function:: AddSimplex($\sim$X, s)
   :input_types: SmpCpx, SeqEnum
   :label: AddSimplex_SmpCpx_SeqEnum_ref

   Adds either a single simplex :math:`s` expressed as a set or a sequence of
   simplexes to a simplicial complex. The functional versions of the function call
   return a new complex with the added simplices included, and the procedural
   change the complex in place.

.. magma:function:: Prune(X, f)
   :input_types: SmpCpx, SetEnum
   :output_types: SmpCpx
   :label: Prune_SmpCpx_SetEnum

.. magma:function:: Prune($\sim$X, f)
   :input_types: SmpCpx, SetEnum
   :label: Prune_SmpCpx_SetEnum_ref

   Removes a face :math:`f` and all faces containing :math:`f` from a simplicial
   complex :math:`X`. If :math:`f` is not a face of :math:`X`, then :math:`X` is
   returned unchanged.

   Note the two calling signatures of this function. The first signature copies the
   simplicial complex and returns a new complex with the desired modification,
   whereas the second signature modifies the complex in place.

.. magma:function:: Glue(X, e)
   :input_types: SmpCpx, SeqEnum
   :output_types: SmpCpx
   :label: Glue_SmpCpx_SeqEnum

.. magma:function:: Glue($\sim$X, e)
   :input_types: SmpCpx, SeqEnum
   :label: Glue_SmpCpx_SeqEnum_ref

   In the simplicial complex :math:`X`, identify all points identified by pairs in
   the sequence :math:`e`.

   The sequence :math:`e` should be a sequence of pairs of elements of the face
   sets of :math:`X`. The identification will eliminate the first component of each
   pair, replacing it with the second component wherever it occurs in :math:`X`.

   Note the two calling signatures of this function. The first signature copies the
   simplicial complex and returns a new complex with the desired modification,
   whereas the second signature modifies the complex in place.

.. magma:example:: Example: Prune Glue
   :label: prune-glue

   We can, for instance, construct the connected sum of two tori using ``Product``,
   ``Prune``, the topological sum and ``Glue``.

   Note that we find the glue data by considering that the maximal point in the
   original torus had number :math:`9`, so for the second added torus, all points
   will be shifted by :math:`9` and in the third all points will be shifted by
   :math:`18`. Thus, the excised facets :math:`\{1,2,7\}` and :math:`\{6,8,9\}`
   turn into :math:`\{10,11,16\}` and :math:`\{15,17,18\}`, and the excised facet
   :math:`\{1,2,7\}` in the third torus turns into :math:`\{19,20,25\}`.

   .. code-block:: magma

      > circ := SimplicialComplex([{1,2},{2,3},{3,1}]);
      > torus := Product(circ,circ);
      > Normalization(~torus);
      > torus;
      Simplicial complex
      [
          { 2, 3, 6 },
          { 1, 2, 9 },
          { 2, 6, 8 },
          { 4, 7, 8 },
          { 3, 5, 9 },
          { 4, 6, 7 },
          { 1, 8, 9 },
          { 1, 4, 8 },
          { 6, 8, 9 },
          { 2, 7, 8 },
          { 2, 3, 9 },
          { 5, 6, 9 },
          { 1, 3, 5 },
          { 1, 4, 6 },
          { 3, 6, 7 },
          { 1, 5, 6 },
          { 1, 2, 7 },
          { 1, 3, 7 }
      ]

      > oneholetorus := Prune(torus,{1,2,7});
      > twoholetorus := Prune(Prune(torus,{1,2,7}),{6,8,9});
      > threetori := oneholetorus + twoholetorus + oneholetorus;
      > threetorus := Glue(threetori,[<1,10>,<2,11>,<7,16>,<15,19>,<17,20>,<18,25>]);

.. magma:function:: BarycentricSubdivision(X)
   :input_types: SmpCpx
   :output_types: SmpCpx
   :label: BarycentricSubdivision_SmpCpx

   Constructs the barycentric subdivision of the simplicial complex :math:`X`.
   Abstractly, this is a simplicial complex whose faces are chains
   :math:`X_1 \subset \dots \subset X_n` of faces from :math:`X`. The new complex
   has more faces but the same homotopy type as the old complex.

.. magma:function:: Skeleton(X, q)
   :input_types: SmpCpx, RngIntElt
   :output_types: SmpCpx
   :label: Skeleton_SmpCpx_RngIntElt

   Returns the :math:`q`-skeleton of the simplicial complex :math:`X`. This is the
   complex consisting of all faces of :math:`X` of dimension at most :math:`q`.

.. magma:function:: UnderlyingGraph(X)
   :input_types: SmpCpx
   :output_types: GrphUnd, GrphVertSet, GrphEdgeSet
   :label: UnderlyingGraph_SmpCpx

   Constructs a graph isomorphic, as a graph, to the 1-skeleton of the simplicial
   complex :math:`X`.

.. magma:function:: Cone(X)
   :input_types: SmpCpx
   :output_types: SmpCpx
   :label: Cone_SmpCpx

   Constructs a cone over the simplicial complex :math:`X`. The cone is generated
   by all faces of the complex, with an additional vertex included into each face.
   Any cone is acyclic, in other words all homology groups vanish. Requires a
   normalized simplicial complex.

.. magma:function:: Suspension(X)
   :input_types: SmpCpx
   :output_types: SmpCpx
   :label: Suspension_SmpCpx

   Constructs the suspension, or double cone, over the normalized simplicial
   complex :math:`X`. The suspension has the added property that all the homology
   groups occur in it, shifted up by one dimension.

.. magma:example:: Example: Cone Suspension
   :label: cone-suspension

   For computation of the relevant homology, and a demonstration of the stated
   facts about the cone and suspension operations, please refer to examples in the
   Section on homology computation.

   .. code-block:: magma

      > circ := Boundary(SimplicialComplex([{1,2,3}]));
      > Cone(circ);
      Simplicial complex
      [
      \    { 1, 3, 4 },
      \    { 2, 3, 4 },
      \    { 1, 2, 4 }
      ]

      > Suspension(circ); 
      Simplicial complex
      [
      \    { 1, 3, 5 },
      \    { 1, 3, 4 },
      \    { 1, 2, 5 },
      \    { 2, 3, 4 },
      \    { 1, 2, 4 },
      \    { 2, 3, 5 }
      ]

Standard Topological Objects
----------------------------

.. magma:function:: Simplex(n)
   :input_types: RngIntElt
   :output_types: SmpCpx
   :label: Simplex_RngIntElt

   Returns the :math:`n`-dimensional simplex as a simplicial complex.

.. magma:function:: Sphere(n)
   :input_types: RngIntElt
   :output_types: SmpCpx
   :label: Sphere_RngIntElt

   Returns a simplicial complex triangulating the :math:`n`-sphere.

.. magma:function:: KleinBottle()
   :output_types: SmpCpx
   :label: KleinBottle

   Returns a triangulation of the Klein bottle as an abstract simplicial complex.

.. magma:function:: Torus()
   :output_types: SmpCpx
   :label: Torus

   Returns a triangulation of a torus as an abstract simplicial complex.

.. magma:function:: Cylinder()
   :output_types: SmpCpx
   :label: Cylinder

   Returns a triangulation of a cylinder as an abstract simplicial complex.

.. magma:function:: MoebiusStrip()
   :output_types: SmpCpx
   :label: MoebiusStrip

   Returns a triangulation of the Moebius strip as an abstract simplicial complex.

.. magma:function:: LensSpace(p)
   :input_types: RngIntElt
   :output_types: SmpCpx
   :label: LensSpace_RngIntElt

   Constructs the lens space :math:`L(p,1)`. This has a 1-dimensional homology
   generator of order :math:`p`.

.. magma:function:: SimplicialProjectivePlane()
   :output_types: SmpCpx
   :label: SimplicialProjectivePlane

   Constructs a triangulation of the projective plane.

Examples for the usage of ``LensSpace`` and ``SimplicialProjectivePlane`` will
be given in Section :ref:`hom-comp` on homology computation.