Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- r""" Finite simplicial complexes
AUTHORS:
- John H. Palmieri (2009-04)
- D. Benjamin Antieau (2009-06): added is_connected, generated_subcomplex, remove_facet, and is_flag_complex methods; cached the output of the graph() method.
- Travis Scrimshaw (2012-08-17): Made :class:`SimplicialComplex` have an immutable option, and added ``__hash__()`` function which checks to make sure it is immutable. Made :meth:`SimplicialComplex.remove_face()` into a mutator. Deprecated the ``vertex_set`` parameter.
- Christian Stump (2011-06): implementation of is_cohen_macaulay
- Travis Scrimshaw (2013-02-16): Allowed :class:`SimplicialComplex` to make mutable copies.
- Simon King (2014-05-02): Let simplicial complexes be objects of the category of simplicial complexes.
- Jeremy Martin (2016-06-02): added cone_vertices, decone, is_balanced, is_partitionable, intersection methods
This module implements the basic structure of finite simplicial complexes. Given a set `V` of "vertices", a simplicial complex on `V` is a collection `K` of subsets of `V` satisfying the condition that if `S` is one of the subsets in `K`, then so is every subset of `S`. The subsets `S` are called the 'simplices' of `K`.
A simplicial complex `K` can be viewed as a purely combinatorial object, as described above, but it also gives rise to a topological space `|K|` (its *geometric realization*) as follows: first, the points of `V` should be in general position in euclidean space. Next, if `\{v\}` is in `K`, then the vertex `v` is in `|K|`. If `\{v, w\}` is in `K`, then the line segment from `v` to `w` is in `|K|`. If `\{u, v, w\}` is in `K`, then the triangle with vertices `u`, `v`, and `w` is in `|K|`. In general, `|K|` is the union of the convex hulls of simplices of `K`. Frequently, one abuses notation and uses `K` to denote both the simplicial complex and the associated topological space.
.. image:: ../../media/simplices.png
For any simplicial complex `K` and any commutative ring `R` there is an associated chain complex, with differential of degree `-1`. The `n^{th}` term is the free `R`-module with basis given by the `n`-simplices of `K`. The differential is determined by its value on any simplex: on the `n`-simplex with vertices `(v_0, v_1, ..., v_n)`, the differential is the alternating sum with `i^{th}` summand `(-1)^i` multiplied by the `(n-1)`-simplex obtained by omitting vertex `v_i`.
In the implementation here, the vertex set must be finite. To define a simplicial complex, specify its vertex set: this should be a list, tuple, or set, or it can be a non-negative integer `n`, in which case the vertex set is `(0, ..., n)`. Also specify the facets: the maximal faces.
.. NOTE::
The elements of the vertex set are not automatically contained in the simplicial complex: each one is only included if and only if it is a vertex of at least one of the specified facets.
.. NOTE::
This class derives from :class:`~sage.homology.cell_complex.GenericCellComplex`, and so inherits its methods. Some of those methods are not listed here; see the :mod:`Generic Cell Complex <sage.homology.cell_complex>` page instead.
EXAMPLES::
sage: SimplicialComplex([[1], [3, 7]]) Simplicial complex with vertex set (1, 3, 7) and facets {(3, 7), (1,)} sage: SimplicialComplex() # the empty simplicial complex Simplicial complex with vertex set () and facets {()} sage: X = SimplicialComplex([[0,1], [1,2], [2,3], [3,0]]) sage: X Simplicial complex with vertex set (0, 1, 2, 3) and facets {(1, 2), (2, 3), (0, 3), (0, 1)} sage: X.stanley_reisner_ring() Quotient of Multivariate Polynomial Ring in x0, x1, x2, x3 over Integer Ring by the ideal (x1*x3, x0*x2) sage: X.is_pure() True
Sage can perform a number of operations on simplicial complexes, such as the join and the product, and it can also compute homology::
sage: S = SimplicialComplex([[0,1], [1,2], [0,2]]) # circle sage: T = S.product(S) # torus sage: T Simplicial complex with 9 vertices and 18 facets sage: T.homology() # this computes reduced homology {0: 0, 1: Z x Z, 2: Z} sage: T.euler_characteristic() 0
Sage knows about some basic combinatorial data associated to a simplicial complex::
sage: X = SimplicialComplex([[0,1], [1,2], [2,3], [0,3]]) sage: X.f_vector() [1, 4, 4] sage: X.face_poset() Finite poset containing 8 elements sage: X.stanley_reisner_ring() Quotient of Multivariate Polynomial Ring in x0, x1, x2, x3 over Integer Ring by the ideal (x1*x3, x0*x2)
Mutability (see :trac:`12587`)::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S.add_face([1,3]) sage: S.remove_face([1,3]); S Simplicial complex with vertex set (1, 2, 3, 4) and facets {(2, 4), (1, 4), (3,)} sage: hash(S) Traceback (most recent call last): ... ValueError: This simplicial complex must be immutable. Call set_immutable(). sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S.set_immutable() sage: S.add_face([1,3]) Traceback (most recent call last): ... ValueError: This simplicial complex is not mutable sage: S.remove_face([1,3]) Traceback (most recent call last): ... ValueError: This simplicial complex is not mutable sage: hash(S) == hash(S) True
sage: S2 = SimplicialComplex([[1,4], [2,4]], is_mutable=False) sage: hash(S2) == hash(S) True
We can also make mutable copies of an immutable simplicial complex (see :trac:`14142`)::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S.set_immutable() sage: T = copy(S) sage: T.is_mutable() True sage: S == T True """ from __future__ import print_function, absolute_import from six.moves import range from six import integer_types
# possible future directions for SimplicialComplex: # # make compatible with GAP (see http://linalg.org/gap.html) # compare to and make compatible with polymake # see Macaulay: http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.1/share/doc/Macaulay2/SimplicialComplexes/html/___Simplicial__Complex.html; compare performance and make compatible # should + have any meaning? # cohomology: compute cup products (and Massey products?)
from copy import copy from sage.misc.lazy_import import lazy_import from sage.misc.cachefunc import cached_method from sage.homology.cell_complex import GenericCellComplex from sage.structure.sage_object import SageObject from sage.structure.parent import Parent from sage.rings.integer import Integer from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.sets.set import Set from sage.rings.integer_ring import ZZ from sage.rings.rational_field import QQ from sage.structure.category_object import normalize_names from sage.misc.latex import latex from sage.misc.misc import union from sage.matrix.constructor import matrix from sage.homology.chain_complex import ChainComplex from sage.graphs.graph import Graph from functools import reduce, total_ordering from itertools import combinations lazy_import('sage.categories.simplicial_complexes', 'SimplicialComplexes') from sage.misc.cachefunc import cached_method from sage.misc.decorators import rename_keyword
def lattice_paths(t1, t2, length=None): """ Given lists (or tuples or ...) ``t1`` and ``t2``, think of them as labelings for vertices: ``t1`` labeling points on the x-axis, ``t2`` labeling points on the y-axis, both increasing. Return the list of rectilinear paths along the grid defined by these points in the plane, starting from ``(t1[0], t2[0])``, ending at ``(t1[last], t2[last])``, and at each grid point, going either right or up. See the examples.
:param t1: labeling for vertices :param t2: labeling for vertices :param length: if not ``None``, then an integer, the length of the desired path. :type length: integer or ``None``; optional, default ``None`` :type t1: list, other iterable :type t2: list, other iterable :return: list of lists of vertices making up the paths as described above :rtype: list of lists
This is used when triangulating the product of simplices. The optional argument ``length`` is used for `\Delta`-complexes, to specify all simplices in a product: in the triangulation of a product of two simplices, there is a `d`-simplex for every path of length `d+1` in the lattice. The path must start at the bottom left and end at the upper right, and it must use at least one point in each row and in each column, so if ``length`` is too small, there will be no paths.
EXAMPLES::
sage: from sage.homology.simplicial_complex import lattice_paths sage: lattice_paths([0,1,2], [0,1,2]) [[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)], [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)], [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)], [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]] sage: lattice_paths(('a', 'b', 'c'), (0, 3, 5)) [[('a', 0), ('a', 3), ('a', 5), ('b', 5), ('c', 5)], [('a', 0), ('a', 3), ('b', 3), ('b', 5), ('c', 5)], [('a', 0), ('b', 0), ('b', 3), ('b', 5), ('c', 5)], [('a', 0), ('a', 3), ('b', 3), ('c', 3), ('c', 5)], [('a', 0), ('b', 0), ('b', 3), ('c', 3), ('c', 5)], [('a', 0), ('b', 0), ('c', 0), ('c', 3), ('c', 5)]] sage: lattice_paths(range(3), range(3), length=2) [] sage: lattice_paths(range(3), range(3), length=3) [[(0, 0), (1, 1), (2, 2)]] sage: lattice_paths(range(3), range(3), length=4) [[(0, 0), (1, 1), (1, 2), (2, 2)], [(0, 0), (0, 1), (1, 2), (2, 2)], [(0, 0), (1, 1), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 1), (2, 2)], [(0, 0), (0, 1), (1, 1), (2, 2)], [(0, 0), (1, 0), (1, 1), (2, 2)]] """ # Convert t1, t2 to tuples, in case they are (for example) Python 3 ranges. # 0 x n (or k x 0) rectangle: return [[]] # 1 x n (or k x 1) rectangle: else: # recursive: paths in rectangle with either one fewer row # or column, plus the upper right corner in lattice_paths(t1[:-1], t2)] + [path + [(t1[-1], t2[-1])] for path in lattice_paths(t1, t2[:-1])]) else: # as above, except make sure that lengths are correct. if # not, return an empty list. # # 0 x n (or k x 0) rectangle: if length == 0: return [[]] else: return [] # 1 x n (or k x 1) rectangle: else: else: else: # recursive: paths of length one fewer in rectangle with # either one fewer row, one fewer column, or one fewer of # each, and then plus the upper right corner in lattice_paths(t1[:-1], t2, length=length-1)] + [path + [(t1[-1], t2[-1])] for path in lattice_paths(t1, t2[:-1], length=length-1)] + [path + [(t1[-1], t2[-1])] for path in lattice_paths(t1[:-1], t2[:-1], length=length-1)])
def rename_vertex(n, keep, left=True): """ Rename a vertex: the vertices from the list ``keep`` get relabeled 0, 1, 2, ..., in order. Any other vertex (e.g. 4) gets renamed to by prepending an 'L' or an 'R' (thus to either 'L4' or 'R4'), depending on whether the argument left is ``True`` or ``False``.
:param n: a 'vertex': either an integer or a string :param keep: a list of three vertices :param left: if ``True``, rename for use in left factor :type left: boolean; optional, default ``True``
This is used by the :meth:`~SimplicialComplex.connected_sum` method for simplicial complexes.
EXAMPLES::
sage: from sage.homology.simplicial_complex import rename_vertex sage: rename_vertex(6, [5, 6, 7]) 1 sage: rename_vertex(3, [5, 6, 7, 8, 9]) 'L3' sage: rename_vertex(3, [5, 6, 7], left=False) 'R3' """ else:
@total_ordering class Simplex(SageObject): """ Define a simplex.
Topologically, a simplex is the convex hull of a collection of vertices in general position. Combinatorially, it is defined just by specifying a set of vertices. It is represented in Sage by the tuple of the vertices.
:param X: set of vertices :type X: integer, list, other iterable :return: simplex with those vertices
``X`` may be a non-negative integer `n`, in which case the simplicial complex will have `n+1` vertices `(0, 1, ..., n)`, or it may be anything which may be converted to a tuple, in which case the vertices will be that tuple. In the second case, each vertex must be hashable, so it should be a number, a string, or a tuple, for instance, but not a list.
.. WARNING::
The vertices should be distinct, and no error checking is done to make sure this is the case.
EXAMPLES::
sage: Simplex(4) (0, 1, 2, 3, 4) sage: Simplex([3, 4, 1]) (3, 4, 1) sage: X = Simplex((3, 'a', 'vertex')); X (3, 'a', 'vertex') sage: X == loads(dumps(X)) True
Vertices may be tuples but not lists::
sage: Simplex([(1,2), (3,4)]) ((1, 2), (3, 4)) sage: Simplex([[1,2], [3,4]]) Traceback (most recent call last): ... TypeError: unhashable type: 'list' """
def __init__(self, X): """ Define a simplex. See :class:`Simplex` for full documentation.
EXAMPLES::
sage: Simplex(2) (0, 1, 2) sage: Simplex(('a', 'b', 'c')) ('a', 'b', 'c') sage: Simplex(-1) () sage: Simplex(-3) Traceback (most recent call last): ... ValueError: the n-simplex is only defined if n > -2 """
def tuple(self): """ The tuple attached to this simplex.
EXAMPLES::
sage: Simplex(3).tuple() (0, 1, 2, 3)
Although simplices are printed as if they were tuples, they are not the same type::
sage: type(Simplex(3).tuple()) <... 'tuple'> sage: type(Simplex(3)) <class 'sage.homology.simplicial_complex.Simplex'> """
def set(self): """ The frozenset attached to this simplex.
EXAMPLES::
sage: Simplex(3).set() frozenset({0, 1, 2, 3}) """
def is_face(self, other): """ Return ``True`` iff this simplex is a face of other.
EXAMPLES::
sage: Simplex(3).is_face(Simplex(5)) True sage: Simplex(5).is_face(Simplex(2)) False sage: Simplex(['a', 'b', 'c']).is_face(Simplex(8)) False """
def __contains__(self, x): """ Return ``True`` iff ``x`` is a vertex of this simplex.
EXAMPLES::
sage: 3 in Simplex(5) True sage: 3 in Simplex(2) False """
def __getitem__(self, n): """ Return the `n`-th vertex in this simplex.
EXAMPLES::
sage: Simplex(5)[2] 2 sage: Simplex(['a', 'b', 'c'])[1] 'b' """
def __iter__(self): """ Iterator for the vertices of this simplex.
EXAMPLES::
sage: [v**2 for v in Simplex(3)] [0, 1, 4, 9] """
def __add__(self, other): """ Simplex obtained by concatenating the underlying tuples of the two arguments.
:param other: another simplex
EXAMPLES::
sage: Simplex((1,2,3)) + Simplex((5,6)) (1, 2, 3, 5, 6) """
def face(self, n): """ The `n`-th face of this simplex.
:param n: an integer between 0 and the dimension of this simplex :type n: integer :return: the simplex obtained by removing the `n`-th vertex from this simplex
EXAMPLES::
sage: S = Simplex(4) sage: S.face(0) (1, 2, 3, 4) sage: S.face(3) (0, 1, 2, 4) """ else: raise IndexError("{} does not have an nth face for n={}.".format(self, n))
def faces(self): """ The list of faces (of codimension 1) of this simplex.
EXAMPLES::
sage: S = Simplex(4) sage: S.faces() [(1, 2, 3, 4), (0, 2, 3, 4), (0, 1, 3, 4), (0, 1, 2, 4), (0, 1, 2, 3)] sage: len(Simplex(10).faces()) 11 """
def dimension(self): """ The dimension of this simplex.
The dimension of a simplex is the number of vertices minus 1.
EXAMPLES::
sage: Simplex(5).dimension() == 5 True sage: Simplex(5).face(1).dimension() 4 """
def is_empty(self): """ Return ``True`` iff this simplex is the empty simplex.
EXAMPLES::
sage: [Simplex(n).is_empty() for n in range(-1,4)] [True, False, False, False, False] """
def join(self, right, rename_vertices=True): """ The join of this simplex with another one.
The join of two simplices `[v_0, ..., v_k]` and `[w_0, ..., w_n]` is the simplex `[v_0, ..., v_k, w_0, ..., w_n]`.
:param right: the other simplex (the right-hand factor)
:param rename_vertices: If this is ``True``, the vertices in the join will be renamed by this formula: vertex "v" in the left-hand factor --> vertex "Lv" in the join, vertex "w" in the right-hand factor --> vertex "Rw" in the join. If this is false, this tries to construct the join without renaming the vertices; this may cause problems if the two factors have any vertices with names in common.
:type rename_vertices: boolean; optional, default ``True``
EXAMPLES::
sage: Simplex(2).join(Simplex(3)) ('L0', 'L1', 'L2', 'R0', 'R1', 'R2', 'R3') sage: Simplex(['a', 'b']).join(Simplex(['x', 'y', 'z'])) ('La', 'Lb', 'Rx', 'Ry', 'Rz') sage: Simplex(['a', 'b']).join(Simplex(['x', 'y', 'z']), rename_vertices=False) ('a', 'b', 'x', 'y', 'z') """ + ["R" + str(w) for w in right]) else:
def product(self, other, rename_vertices=True): r""" The product of this simplex with another one, as a list of simplices.
:param other: the other simplex
:param rename_vertices: If this is ``False``, then the vertices in the product are the set of ordered pairs `(v,w)` where `v` is a vertex in the left-hand factor (``self``) and `w` is a vertex in the right-hand factor (``other``). If this is ``True``, then the vertices are renamed as "LvRw" (e.g., the vertex (1,2) would become "L1R2"). This is useful if you want to define the Stanley-Reisner ring of the complex: vertex names like (0,1) are not suitable for that, while vertex names like "L0R1" are.
:type rename_vertices: boolean; optional, default ``True``
Algorithm: see Hatcher, p. 277-278 [Hat2002]_ (who in turn refers to Eilenberg-Steenrod, p. 68): given ``S = Simplex(m)`` and ``T = Simplex(n)``, then `S \times T` can be triangulated as follows: for each path `f` from `(0,0)` to `(m,n)` along the integer grid in the plane, going up or right at each lattice point, associate an `(m+n)`-simplex with vertices `v_0`, `v_1`, ..., where `v_k` is the `k^{th}` vertex in the path `f`.
Note that there are `m+n` choose `n` such paths. Note also that each vertex in the product is a pair of vertices `(v,w)` where `v` is a vertex in the left-hand factor and `w` is a vertex in the right-hand factor.
.. NOTE::
This produces a list of simplices -- not a :class:`Simplex`, not a :class:`SimplicialComplex`.
EXAMPLES::
sage: len(Simplex(2).product(Simplex(2))) 6 sage: Simplex(1).product(Simplex(1)) [('L0R0', 'L0R1', 'L1R1'), ('L0R0', 'L1R0', 'L1R1')] sage: Simplex(1).product(Simplex(1), rename_vertices=False) [((0, 0), (0, 1), (1, 1)), ((0, 0), (1, 0), (1, 1))] """
def alexander_whitney(self, dim): r""" Subdivide this simplex into a pair of simplices.
If this simplex has vertices `v_0`, `v_1`, ..., `v_n`, then subdivide it into simplices `(v_0, v_1, ..., v_{dim})` and `(v_{dim}, v_{dim + 1}, ..., v_n)`.
INPUT:
- ``dim`` -- integer between 0 and one more than the dimension of this simplex
OUTPUT:
- a list containing just the triple ``(1, left, right)``, where ``left`` and ``right`` are the two simplices described above.
This method allows one to construct a coproduct from the `p+q`-chains to the tensor product of the `p`-chains and the `q`-chains. The number 1 (a Sage integer) is the coefficient of ``left tensor right`` in this coproduct. (The corresponding formula is more complicated for the cubes that make up a cubical complex, and the output format is intended to be consistent for both cubes and simplices.)
Calling this method ``alexander_whitney`` is an abuse of notation, since the actual Alexander-Whitney map goes from `C(X \times Y) \to C(X) \otimes C(Y)`, where `C(-)` denotes the chain complex of singular chains, but this subdivision of simplices is at the heart of it.
EXAMPLES::
sage: s = Simplex((0,1,3,4)) sage: s.alexander_whitney(0) [(1, (0,), (0, 1, 3, 4))] sage: s.alexander_whitney(2) [(1, (0, 1, 3), (3, 4))] """ Simplex(self.tuple()[dim:]))]
def __eq__(self, other): """ Return ``True`` iff this simplex is the same as ``other``: that is, if the vertices of the two are the same, even with a different ordering
:param other: the other simplex
EXAMPLES::
sage: Simplex([0,1,2]) == Simplex([0,2,1]) True sage: Simplex([0,1,2]) == Simplex(['a','b','c']) False sage: Simplex([1]) < Simplex([2]) True sage: Simplex([1]) > Simplex([2]) False """
def __ne__(self, other): """ Return ``True`` iff this simplex is not equal to ``other``.
:param other: the other simplex
EXAMPLES::
sage: Simplex([0,1,2]) != Simplex([0,2,1]) False sage: Simplex([0,1,2]) != Simplex(['a','b','c']) True """
def __lt__(self, other): """ Return ``True`` iff the sorted tuple for this simplex is less than that for ``other``.
:param other: the other simplex
EXAMPLES::
sage: Simplex([1]) < Simplex([2]) True sage: Simplex([2,3]) < Simplex([1]) False sage: Simplex([0,1,2]) < Simplex([0,2,1]) False
Test ``@total_ordering`` by testing other comparisons::
sage: Simplex([0,1,2]) <= Simplex([0,2,1]) True sage: Simplex([1]) <= Simplex([2]) True sage: Simplex([2]) <= Simplex([1]) False sage: Simplex([0,1,2]) > Simplex([0,2,1]) False sage: Simplex([1]) > Simplex([2]) False sage: Simplex([2]) > Simplex([1]) True sage: Simplex([0,1,2]) > Simplex([0,2,1]) False sage: Simplex([0,1,2]) >= Simplex([0,2,1]) True sage: Simplex([1]) >= Simplex([2]) False sage: Simplex([2]) >= Simplex([1]) True """
def __hash__(self): """ Hash value for this simplex. This computes the hash value of the Python frozenset of the underlying tuple, since this is what's important when testing equality.
EXAMPLES::
sage: Simplex([1,2,0]).__hash__() == Simplex(2).__hash__() True sage: Simplex([1,2,0,1,1,2]).__hash__() == Simplex(2).__hash__() True """
def _repr_(self): """ Print representation.
EXAMPLES::
sage: S = Simplex(5) sage: S._repr_() '(0, 1, 2, 3, 4, 5)' """
def _latex_(self): r""" LaTeX representation.
EXAMPLES::
sage: Simplex(3)._latex_() \left(0, 1, 2, 3\right) """
class SimplicialComplex(Parent, GenericCellComplex): r""" Define a simplicial complex.
:param maximal_faces: set of maximal faces :param from_characteristic_function: see below :param maximality_check: see below :type maximality_check: boolean; optional, default ``True`` :param sort_facets: see below :type sort_facets: boolean; optional, default ``True`` :param name_check: see below :type name_check: boolean; optional, default ``False`` :param is_mutable: Set to ``False`` to make this immutable :type is_mutable: boolean; optional, default ``True`` :param category: the category of the simplicial complex :type category: category; optional, default finite simplicial complexes :return: a simplicial complex
``maximal_faces`` should be a list or tuple or set (indeed, anything which may be converted to a set) whose elements are lists (or tuples, etc.) of vertices. Maximal faces are also known as 'facets'.
Alternatively, the maximal faces can be defined from a monotone boolean function on the subsets of a set `X`. While defining ``maximal_faces=None``, you can thus set ``from_characteristic_function=(f,X)`` where ``X`` is the set of points and ``f`` a boolean monotone hereditary function that accepts a list of elements from ``X`` as input (see :func:`~sage.combinat.subsets_hereditary.subsets_with_hereditary_property` for more information).
If ``maximality_check`` is ``True``, check that each maximal face is, in fact, maximal. In this case, when producing the internal representation of the simplicial complex, omit those that are not. It is highly recommended that this be ``True``; various methods for this class may fail if faces which are claimed to be maximal are in fact not.
If ``sort_facets`` is ``True``, sort the vertices in each facet. If the vertices in different facets are not ordered compatibly (e.g., if you have facets ``(1, 3, 5)`` and ``(5, 3, 8)``), then homology calculations may have unpredictable results.
If ``name_check`` is ``True``, check the names of the vertices to see if they can be easily converted to generators of a polynomial ring -- use this if you plan to use the Stanley-Reisner ring for the simplicial complex.
EXAMPLES::
sage: SimplicialComplex([[1,2], [1,4]]) Simplicial complex with vertex set (1, 2, 4) and facets {(1, 2), (1, 4)} sage: SimplicialComplex([[0,2], [0,3], [0]]) Simplicial complex with vertex set (0, 2, 3) and facets {(0, 2), (0, 3)} sage: SimplicialComplex([[0,2], [0,3], [0]], maximality_check=False) Simplicial complex with vertex set (0, 2, 3) and facets {(0, 2), (0, 3), (0,)} sage: S = SimplicialComplex((('a', 'b'), ['a', 'c'], ('b', 'c'))) sage: S Simplicial complex with vertex set ('a', 'b', 'c') and facets {('b', 'c'), ('a', 'c'), ('a', 'b')}
Finally, if there is only one argument and it is a simplicial complex, return that complex. If it is an object with a built-in conversion to simplicial complexes (via a ``_simplicial_`` method), then the resulting simplicial complex is returned::
sage: S = SimplicialComplex([[0,2], [0,3], [0,6]]) sage: SimplicialComplex(S) == S True sage: Tc = cubical_complexes.Torus(); Tc Cubical complex with 16 vertices and 64 cubes sage: Ts = SimplicialComplex(Tc); Ts Simplicial complex with 16 vertices and 32 facets sage: Ts.homology() {0: 0, 1: Z x Z, 2: Z}
From a characteristic monotone boolean function, e.g. the simplicial complex of all subsets `S\subseteq \{0,1,2,3,4\}` such that `sum(S)\leq 4`::
sage: SimplicialComplex(from_characteristic_function=(lambda x:sum(x)<=4, range(5))) Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 4), (0, 1, 2), (0, 1, 3)}
or e.g. the simplicial complex of all 168 hyperovals of the projective plane of order 4::
sage: l = designs.ProjectiveGeometryDesign(2,1,GF(4,name='a')) sage: f = lambda S: not any(len(set(S).intersection(x))>2 for x in l) sage: SimplicialComplex(from_characteristic_function=(f, l.ground_set())) Simplicial complex with 21 vertices and 168 facets
TESTS:
Check that we can make mutable copies (see :trac:`14142`)::
sage: S = SimplicialComplex([[0,2], [0,3]], is_mutable=False) sage: S.is_mutable() False sage: C = copy(S) sage: C.is_mutable() True sage: SimplicialComplex(S, is_mutable=True).is_mutable() True sage: SimplicialComplex(S, is_immutable=False).is_mutable() True
.. WARNING::
Simplicial complexes are not proper parents as they do not possess element classes. In particular, parents are assumed to be hashable (and hence immutable) by the coercion framework. However this is close enough to being a parent with elements being the faces of ``self`` that we currently allow this abuse. """
def __init__(self, maximal_faces=None, from_characteristic_function=None, maximality_check=True, sort_facets=True, name_check=False, is_mutable=True, is_immutable=False, category=None): """ Define a simplicial complex. See ``SimplicialComplex`` for more documentation.
EXAMPLES::
sage: SimplicialComplex([[0,2], [0,3], [0]]) Simplicial complex with vertex set (0, 2, 3) and facets {(0, 2), (0, 3)} sage: SimplicialComplex((('a', 'b'), ('a', 'c'), ('b', 'c'))) Simplicial complex with vertex set ('a', 'b', 'c') and facets {('b', 'c'), ('a', 'c'), ('a', 'b')}
TESTS::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S2 = SimplicialComplex([[1,4], [2,4]], is_mutable=False) sage: S == S2 True sage: S3 = SimplicialComplex(maximal_faces=[[1,4], [2,4]]) sage: S == S3 True
Test that we have fixed a problem revealed in :trac:`20718`; see also :trac:`20720`::
sage: SimplicialComplex([2], sort_facets=False) Simplicial complex with vertex set (0, 1, 2) and facets {(0, 1, 2)}
sage: S = SimplicialComplex((('a', 'b'), ('a', 'c'), ('b', 'c'))) sage: S == loads(dumps(S)) True
sage: TestSuite(S).run() sage: TestSuite(S3).run() """ from_characteristic_function is not None): raise ValueError("maximal_faces and from_characteristic_function cannot be both defined")
else: # Convert it into a list (in case it is an iterable)
else: try: if int(v) < 0: raise ValueError("The vertex %s does not have an appropriate name."%v) except ValueError: # v is not an integer try: normalize_names(1, v) except ValueError: raise ValueError("The vertex %s does not have an appropriate name."%v) # build dictionary of generator names # build set of facets
# check whether each given face is actually maximal any(face.is_face(other) for other in good_faces)):
# if no maximal faces, add the empty face as a facet # now record the attributes for self # self._vertex_set: the tuple formed by the vertices # self._facets: list of facets # self._sorted: True if the vertex set should be sorted. This # gets used by the add_face method. # self._faces: dictionary of dictionaries of faces. The main # dictionary is keyed by subcomplexes, and each value is a # dictionary keyed by dimension. This should be empty until # needed -- that is, until the faces method is called # self._gen_dict: dictionary of names for the polynomial # generators of the Stanley-Reisner ring # self._complex: dictionary indexed by dimension d, subcomplex, # etc.: differential from dim d to dim d-1 in the associated # chain complex. thus to get the differential in the cochain # complex from dim d-1 to dim d, take the transpose of this # one. # self.__contractible: if not None, a contractible subcomplex # of self, as found by the _contractible_subcomplex method. # self.__enlarged: dictionary of enlarged subcomplexes, # indexed by subcomplexes. For use in the _enlarge_subcomplex # method. # initialize self._graph to None.
# Handle mutability keywords
def __hash__(self): """ Compute the hash value of ``self``.
If this simplicial complex is immutable, it computes the hash value based upon the facets. Otherwise it raises a ``ValueError``.
EXAMPLES::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: hash(S) Traceback (most recent call last): ... ValueError: This simplicial complex must be immutable. Call set_immutable(). sage: S.set_immutable() sage: hash(S) == hash(S) True sage: S2 = SimplicialComplex([[1,4], [2,4]], is_mutable=False) sage: S == S2 True sage: hash(S) == hash(S2) True """
def __eq__(self, right): """ Two simplicial complexes are equal iff their vertex sets are equal and their sets of facets are equal.
EXAMPLES::
sage: SimplicialComplex([[1,2], [2,3], [4]]) == SimplicialComplex([[4], [2,3], [3], [2,1]]) True sage: X = SimplicialComplex() sage: X.add_face([1,3]) sage: X == SimplicialComplex([[1,3]]) True """
def __ne__(self, right): """ Return ``True`` if ``self`` and ``right`` are not equal.
EXAMPLES::
sage: SimplicialComplex([[1,2], [2,3], [4]]) != SimplicialComplex([[4], [2,3], [3], [2,1]]) False sage: X = SimplicialComplex() sage: X.add_face([1,3]) sage: X != SimplicialComplex([[1,3]]) False """
def __copy__(self): """ Return a mutable copy of ``self``.
EXAMPLES::
sage: S = SimplicialComplex([[0,2], [0,3]], is_mutable=False) sage: S.is_mutable() False sage: C = copy(S) sage: C.is_mutable() True sage: C == S True sage: S.is_mutable() False sage: T = copy(C) sage: T == C True """
def vertices(self): """ The vertex set, as a tuple, of this simplicial complex.
EXAMPLES::
sage: S = SimplicialComplex([[i] for i in range(16)] + [[0,1], [1,2]]) sage: S Simplicial complex with 16 vertices and 15 facets sage: S.vertices() (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) """
def _an_element_(self): """ The first facet of this complex.
EXAMPLES::
sage: SimplicialComplex()._an_element_() () sage: simplicial_complexes.Sphere(3)._an_element_() (1, 2, 3, 4) """
def __contains__(self, x): """ True if ``x`` is a simplex which is contained in this complex.
EXAMPLES::
sage: K = SimplicialComplex([(0,1,2), (0,2,3)]) sage: Simplex((0,2)) in K True sage: Simplex((1,3)) in K False sage: 0 in K # not a simplex False """
def __call__(self, simplex): """ If ``simplex`` is a simplex in this complex, return it. Otherwise, raise a ``ValueError``.
EXAMPLES::
sage: K = SimplicialComplex([(0,1,2), (0,2,3)]) sage: K(Simplex((1,2))) (1, 2) sage: K(Simplex((0,1,3))) Traceback (most recent call last): ... ValueError: the simplex is not in this complex """
def maximal_faces(self): """ The maximal faces (a.k.a. facets) of this simplicial complex.
This just returns the set of facets used in defining the simplicial complex, so if the simplicial complex was defined with no maximality checking, none is done here, either.
EXAMPLES::
sage: Y = SimplicialComplex([[0,2], [1,4]]) sage: Y.maximal_faces() {(1, 4), (0, 2)}
``facets`` is a synonym for ``maximal_faces``::
sage: S = SimplicialComplex([[0,1], [0,1,2]]) sage: S.facets() {(0, 1, 2)} """
facets = maximal_faces
def faces(self, subcomplex=None): """ The faces of this simplicial complex, in the form of a dictionary of sets keyed by dimension. If the optional argument ``subcomplex`` is present, then return only the faces which are *not* in the subcomplex.
:param subcomplex: a subcomplex of this simplicial complex. Return faces which are not in this subcomplex.
:type subcomplex: optional, default ``None``
EXAMPLES::
sage: Y = SimplicialComplex([[1,2], [1,4]]) sage: Y.faces() {-1: {()}, 0: {(1,), (2,), (4,)}, 1: {(1, 2), (1, 4)}} sage: L = SimplicialComplex([[1,2]]) sage: Y.faces(subcomplex=L) {-1: set(), 0: {(4,)}, 1: {(1, 4)}} """ # Make the subcomplex immutable if it is not sort_facets=False, is_mutable=False)
# Faces is the dictionary of faces in self but not in # subcomplex, indexed by dimension # sub_facets is the dictionary of facets in the subcomplex # bad_faces is the set of faces in the subcomplex in the # current dimension # bad_bdries = boundaries of bad_faces: things to be # discarded in dim-1
def face_iterator(self, increasing=True): """ An iterator for the faces in this simplicial complex.
INPUT:
- ``increasing`` -- (optional, default ``True``) if ``True``, return faces in increasing order of dimension, thus starting with the empty face. Otherwise it returns faces in decreasing order of dimension.
EXAMPLES::
sage: S1 = simplicial_complexes.Sphere(1) sage: [f for f in S1.face_iterator()] [(), (2,), (0,), (1,), (1, 2), (0, 2), (0, 1)] """ dim_index = reversed(dim_index)
cells = faces
def n_faces(self, n, subcomplex=None): """ The set of simplices of dimension ``n`` of this simplicial complex. If the optional argument ``subcomplex`` is present, then return the ``n``-dimensional faces which are *not* in the subcomplex.
:param n: non-negative integer :param subcomplex: a subcomplex of this simplicial complex. Return ``n``-dimensional faces which are not in this subcomplex. :type subcomplex: optional, default ``None``
.. NOTE::
This method is not used elsewhere in Sage. The current usage: if order doesn't matter, for example to test membership, use :meth:`faces`. If the order of the cells matters, use :meth:`n_cells`.
EXAMPLES::
sage: S = Set(range(1,5)) sage: Z = SimplicialComplex(S.subsets()) sage: Z Simplicial complex with vertex set (1, 2, 3, 4) and facets {(1, 2, 3, 4)} sage: Z.n_faces(2) {(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)} sage: K = SimplicialComplex([[1,2,3], [2,3,4]]) sage: Z.n_faces(2, subcomplex=K) {(1, 2, 4), (1, 3, 4)} """ else: return set([])
def n_cells(self, n, subcomplex=None, sort=None): """ List of cells of dimension ``n`` of this cell complex.
If the optional argument ``subcomplex`` is present, then return the ``n``-dimensional faces which are *not* in the subcomplex. Sort the list if the argument ``sort`` is ``True``. If ``sort`` is ``None`` (the default), then sort depending on the value of the ``sort_facets`` parameter (from the initialization of the simplicial complex).
.. NOTE::
This list is sorted to provide reliable indexing for the rows and columns of the matrices of differentials in the associated chain complex.
EXAMPLES::
sage: S = Set(range(1,5)) sage: Z = SimplicialComplex(S.subsets()) sage: Z Simplicial complex with vertex set (1, 2, 3, 4) and facets {(1, 2, 3, 4)} sage: Z.n_cells(2) [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)] sage: K = SimplicialComplex([[1,2,3], [2,3,4]]) sage: Z.n_cells(2, subcomplex=K) [(1, 2, 4), (1, 3, 4)] sage: S = SimplicialComplex([[complex(i), complex(1)]], sort_facets=False) sage: S.n_cells(0) [(1j,), ((1+0j),)] """ else:
def is_pure(self): """ Return ``True`` iff this simplicial complex is pure.
A simplicial complex is pure if and only if all of its maximal faces have the same dimension.
.. WARNING::
This may give the wrong answer if the simplicial complex was constructed with ``maximality_check`` set to ``False``.
EXAMPLES::
sage: U = SimplicialComplex([[1,2], [1, 3, 4]]) sage: U.is_pure() False sage: X = SimplicialComplex([[0,1], [0,2], [1,2]]) sage: X.is_pure() True
Demonstration of the warning::
sage: S = SimplicialComplex([[0,1], [0]], maximality_check=False) sage: S.is_pure() False """
def h_vector(self): r""" The `h`-vector of this simplicial complex.
If the complex has dimension `d` and `(f_{-1}, f_0, f_1, ..., f_d)` is its `f`-vector (with `f_{-1} = 1`, representing the empty simplex), then the `h`-vector `(h_0, h_1, ..., h_d, h_{d+1})` is defined by
.. MATH::
\sum_{i=0}^{d+1} h_i x^{d+1-i} = \sum_{i=0}^{d+1} f_{i-1} (x-1)^{d+1-i}.
Alternatively,
.. MATH::
h_j = \sum_{i=-1}^{j-1} (-1)^{j-i-1} \binom{d-i}{j-i-1} f_i.
EXAMPLES:
The `f`- and `h`-vectors of the boundary of an octahedron are computed in :wikipedia:`Simplicial_complex`::
sage: square = SimplicialComplex([[0,1], [1,2], [2,3], [0,3]]) sage: S0 = SimplicialComplex([[0], [1]]) sage: octa = square.join(S0) # boundary of an octahedron sage: octa.f_vector() [1, 6, 12, 8] sage: octa.h_vector() [1, 3, 3, 1] """
def g_vector(self): r""" The `g`-vector of this simplicial complex.
If the `h`-vector of the complex is `(h_0, h_1, ..., h_d, h_{d+1})` -- see :meth:`h_vector` -- then its `g`-vector `(g_0, g_1, ..., g_{[(d+1)/2]})` is defined by `g_0 = 1` and `g_i = h_i - h_{i-1}` for `i > 0`.
EXAMPLES::
sage: S3 = simplicial_complexes.Sphere(3).barycentric_subdivision() sage: S3.f_vector() [1, 30, 150, 240, 120] sage: S3.h_vector() [1, 26, 66, 26, 1] sage: S3.g_vector() [1, 25, 40] """
def face(self, simplex, i): """ The `i`-th face of ``simplex`` in this simplicial complex
INPUT:
- ``simplex`` -- a simplex in this simplicial complex - ``i`` -- integer
EXAMPLES::
sage: S = SimplicialComplex([[0,1,4], [0,1,2]]) sage: S.face(Simplex((0,2)), 0) (2,)
sage: S.face(Simplex((0,3)), 0) Traceback (most recent call last): ... ValueError: this simplex is not in this simplicial complex """ else:
def f_triangle(self): r""" Compute the `f`-triangle of ``self``.
The `f`-triangle is given by `f_{i,j}` being the number of faces `F` of size `j` such that `i = \max_{G \subseteq F} |G|`.
EXAMPLES::
sage: X = SimplicialComplex([[1,2,3], [3,4,5], [1,4], [1,5], [2,4], [2,5]]) sage: X.f_triangle() ## this complex is not pure [[0], [0, 0], [0, 0, 4], [1, 5, 6, 2]]
A complex is pure if and only if the last row is nonzero::
sage: X = SimplicialComplex([[1,2,3], [3,4,5], [1,4,5]]) sage: X.f_triangle() [[0], [0, 0], [0, 0, 0], [1, 5, 8, 3]] """
def h_triangle(self): r""" Compute the `h`-triangle of ``self``.
The `h`-triangle of a simplicial complex `\Delta` is given by
.. MATH::
h_{i,j} = \sum_{k=0}^j (-1)^{j-k} \binom{i-k}{j-k} f_{i,k},
where `f_{i,k}` is the `f`-triangle of `\Delta`.
EXAMPLES::
sage: X = SimplicialComplex([[1,2,3], [3,4,5], [1,4], [1,5], [2,4], [2,5]]) sage: X.h_triangle() [[0], [0, 0], [0, 0, 4], [1, 2, -1, 0]] """ for k in range(j+1))
def flip_graph(self): """ If ``self`` is pure, then it returns the flip graph of ``self``, otherwise, it returns ``None``.
The flip graph of a pure simplicial complex is the (undirected) graph with vertices being the facets, such that two facets are joined by an edge if they meet in a codimension `1` face.
The flip graph is used to detect if ``self`` is a pseudomanifold.
EXAMPLES::
sage: S0 = simplicial_complexes.Sphere(0) sage: G = S0.flip_graph() sage: G.vertices(); G.edges(labels=False) [(0,), (1,)] [((0,), (1,))]
sage: G = (S0.wedge(S0)).flip_graph() sage: G.vertices(); G.edges(labels=False) [(0,), ('L1',), ('R1',)] [((0,), ('L1',)), ((0,), ('R1',)), (('L1',), ('R1',))]
sage: S1 = simplicial_complexes.Sphere(1) sage: S2 = simplicial_complexes.Sphere(2) sage: G = (S1.wedge(S1)).flip_graph() sage: G.vertices(); G.edges(labels=False) [(0, 'L1'), (0, 'L2'), (0, 'R1'), (0, 'R2'), ('L1', 'L2'), ('R1', 'R2')] [((0, 'L1'), (0, 'L2')), ((0, 'L1'), (0, 'R1')), ((0, 'L1'), (0, 'R2')), ((0, 'L1'), ('L1', 'L2')), ((0, 'L2'), (0, 'R1')), ((0, 'L2'), (0, 'R2')), ((0, 'L2'), ('L1', 'L2')), ((0, 'R1'), (0, 'R2')), ((0, 'R1'), ('R1', 'R2')), ((0, 'R2'), ('R1', 'R2'))]
sage: (S1.wedge(S2)).flip_graph() is None True
sage: G = S2.flip_graph() sage: G.vertices(); G.edges(labels=False) [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)] [((0, 1, 2), (0, 1, 3)), ((0, 1, 2), (0, 2, 3)), ((0, 1, 2), (1, 2, 3)), ((0, 1, 3), (0, 2, 3)), ((0, 1, 3), (1, 2, 3)), ((0, 2, 3), (1, 2, 3))]
sage: T = simplicial_complexes.Torus() sage: G = T.suspension(4).flip_graph() sage: len(G.vertices()); len(G.edges(labels=False)) 46 161 """ # go through all codim 1 faces to build the edge
def is_pseudomanifold(self): """ Return True if self is a pseudomanifold.
A pseudomanifold is a simplicial complex with the following properties:
- it is pure of some dimension `d` (all of its facets are `d`-dimensional) - every `(d-1)`-dimensional simplex is the face of exactly two facets - for every two facets `S` and `T`, there is a sequence of facets
.. MATH::
S = f_0, f_1, ..., f_n = T
such that for each `i`, `f_i` and `f_{i-1}` intersect in a `(d-1)`-simplex.
By convention, `S^0` is the only 0-dimensional pseudomanifold.
EXAMPLES::
sage: S0 = simplicial_complexes.Sphere(0) sage: S0.is_pseudomanifold() True sage: (S0.wedge(S0)).is_pseudomanifold() False sage: S1 = simplicial_complexes.Sphere(1) sage: S2 = simplicial_complexes.Sphere(2) sage: (S1.wedge(S1)).is_pseudomanifold() False sage: (S1.wedge(S2)).is_pseudomanifold() False sage: S2.is_pseudomanifold() True sage: T = simplicial_complexes.Torus() sage: T.suspension(4).is_pseudomanifold() True """ # is each (d-1)-simplex is the face of exactly two facets? # construct a graph with one vertex for each facet, one edge # when two facets intersect in a (d-1)-simplex, and see # whether that graph is connected.
def product(self, right, rename_vertices=True, is_mutable=True): """ The product of this simplicial complex with another one.
:param right: the other simplicial complex (the right-hand factor)
:param rename_vertices: If this is False, then the vertices in the product are the set of ordered pairs `(v,w)` where `v` is a vertex in ``self`` and `w` is a vertex in ``right``. If this is ``True``, then the vertices are renamed as "LvRw" (e.g., the vertex (1,2) would become "L1R2"). This is useful if you want to define the Stanley-Reisner ring of the complex: vertex names like (0,1) are not suitable for that, while vertex names like "L0R1" are.
:type rename_vertices: boolean; optional, default ``True``
:param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
The vertices in the product will be the set of ordered pairs `(v,w)` where `v` is a vertex in self and `w` is a vertex in right.
.. WARNING::
If ``X`` and ``Y`` are simplicial complexes, then ``X*Y`` returns their join, not their product.
EXAMPLES::
sage: S = SimplicialComplex([[0,1], [1,2], [0,2]]) # circle sage: K = SimplicialComplex([[0,1]]) # edge sage: S.product(K).vertices() # cylinder ('L0R0', 'L0R1', 'L1R0', 'L1R1', 'L2R0', 'L2R1') sage: S.product(K, rename_vertices=False).vertices() ((0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)) sage: T = S.product(S) # torus sage: T Simplicial complex with 9 vertices and 18 facets sage: T.homology() {0: 0, 1: Z x Z, 2: Z}
These can get large pretty quickly::
sage: T = simplicial_complexes.Torus(); T Minimal triangulation of the torus sage: K = simplicial_complexes.KleinBottle(); K Minimal triangulation of the Klein bottle sage: T.product(K) # long time: 5 or 6 seconds Simplicial complex with 56 vertices and 1344 facets """
def join(self, right, rename_vertices=True, is_mutable=True): """ The join of this simplicial complex with another one.
The join of two simplicial complexes `S` and `T` is the simplicial complex `S*T` with simplices of the form `[v_0, ..., v_k, w_0, ..., w_n]` for all simplices `[v_0, ..., v_k]` in `S` and `[w_0, ..., w_n]` in `T`.
:param right: the other simplicial complex (the right-hand factor)
:param rename_vertices: If this is True, the vertices in the join will be renamed by the formula: vertex "v" in the left-hand factor --> vertex "Lv" in the join, vertex "w" in the right-hand factor --> vertex "Rw" in the join. If this is false, this tries to construct the join without renaming the vertices; this will cause problems if the two factors have any vertices with names in common.
:type rename_vertices: boolean; optional, default ``True``
:param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
EXAMPLES::
sage: S = SimplicialComplex([[0], [1]]) sage: T = SimplicialComplex([[2], [3]]) sage: S.join(T) Simplicial complex with vertex set ('L0', 'L1', 'R2', 'R3') and 4 facets sage: S.join(T, rename_vertices=False) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(1, 3), (1, 2), (0, 2), (0, 3)}
The notation '*' may be used, as well::
sage: S * S Simplicial complex with vertex set ('L0', 'L1', 'R0', 'R1') and 4 facets sage: S * S * S * S * S * S * S * S Simplicial complex with 16 vertices and 256 facets """
# Use * to mean 'join': __mul__ = join
def cone(self, is_mutable=True): """ The cone on this simplicial complex.
:param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
The cone is the simplicial complex formed by adding a new vertex `C` and simplices of the form `[C, v_0, ..., v_k]` for every simplex `[v_0, ..., v_k]` in the original simplicial complex. That is, the cone is the join of the original complex with a one-point simplicial complex.
EXAMPLES::
sage: S = SimplicialComplex([[0], [1]]) sage: S.cone() Simplicial complex with vertex set ('L0', 'L1', 'R0') and facets {('L0', 'R0'), ('L1', 'R0')} """ rename_vertices = True)
def suspension(self, n=1, is_mutable=True): r""" The suspension of this simplicial complex.
:param n: positive integer -- suspend this many times.
:type n: optional, default 1
:param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
The suspension is the simplicial complex formed by adding two new vertices `S_0` and `S_1` and simplices of the form `[S_0, v_0, ..., v_k]` and `[S_1, v_0, ..., v_k]` for every simplex `[v_0, ..., v_k]` in the original simplicial complex. That is, the suspension is the join of the original complex with a two-point simplicial complex.
If the simplicial complex `M` happens to be a pseudomanifold (see :meth:`is_pseudomanifold`), then this instead constructs Datta's one-point suspension (see [Dat2007]_, p. 434): choose a vertex `u` in `M` and choose a new vertex `w` to add. Denote the join of simplices by "`*`". The facets in the one-point suspension are of the two forms
- `u * \alpha` where `\alpha` is a facet of `M` not containing `u`
- `w * \beta` where `\beta` is any facet of `M`.
EXAMPLES::
sage: S0 = SimplicialComplex([[0], [1]]) sage: S0.suspension() == simplicial_complexes.Sphere(1) True sage: S3 = S0.suspension(3) # the 3-sphere sage: S3.homology() {0: 0, 1: 0, 2: 0, 3: Z}
For pseudomanifolds, the complex constructed here will be smaller than that obtained by taking the join with the 0-sphere: the join adds two vertices, while this construction only adds one. ::
sage: T = simplicial_complexes.Torus() sage: T.join(S0).vertices() # 9 vertices ('L0', 'L1', 'L2', 'L3', 'L4', 'L5', 'L6', 'R0', 'R1') sage: T.suspension().vertices() # 8 vertices (0, 1, 2, 3, 4, 5, 6, 7) """ raise ValueError("n must be non-negative.") return self # Use one-point compactification of Datta. The # construction is a bit slower, but the resulting # complex is smaller. else: rename_vertices = True)
def disjoint_union(self, right, rename_vertices=True, is_mutable=True): """ The disjoint union of this simplicial complex with another one.
:param right: the other simplicial complex (the right-hand factor)
:param rename_vertices: If this is True, the vertices in the disjoint union will be renamed by the formula: vertex "v" in the left-hand factor --> vertex "Lv" in the disjoint union, vertex "w" in the right-hand factor --> vertex "Rw" in the disjoint union. If this is false, this tries to construct the disjoint union without renaming the vertices; this will cause problems if the two factors have any vertices with names in common.
:type rename_vertices: boolean; optional, default True
EXAMPLES::
sage: S1 = simplicial_complexes.Sphere(1) sage: S2 = simplicial_complexes.Sphere(2) sage: S1.disjoint_union(S2).homology() {0: Z, 1: Z, 2: Z} """
def wedge(self, right, rename_vertices=True, is_mutable=True): """ The wedge (one-point union) of this simplicial complex with another one.
:param right: the other simplicial complex (the right-hand factor)
:param rename_vertices: If this is ``True``, the vertices in the wedge will be renamed by the formula: first vertex in each are glued together and called "0". Otherwise, each vertex "v" in the left-hand factor --> vertex "Lv" in the wedge, vertex "w" in the right-hand factor --> vertex "Rw" in the wedge. If this is ``False``, this tries to construct the wedge without renaming the vertices; this will cause problems if the two factors have any vertices with names in common.
:type rename_vertices: boolean; optional, default ``True``
:param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
.. NOTE::
This operation is not well-defined if ``self`` or ``other`` is not path-connected.
EXAMPLES::
sage: S1 = simplicial_complexes.Sphere(1) sage: S2 = simplicial_complexes.Sphere(2) sage: S1.wedge(S2).homology() {0: 0, 1: Z, 2: Z} """
else: facets = self._facets + right._facets
@rename_keyword(deprecation=20723, check_diffs='check') def chain_complex(self, subcomplex=None, augmented=False, verbose=False, check=False, dimensions=None, base_ring=ZZ, cochain=False): """ The chain complex associated to this simplicial complex.
:param dimensions: if ``None``, compute the chain complex in all dimensions. If a list or tuple of integers, compute the chain complex in those dimensions, setting the chain groups in all other dimensions to zero. :param base_ring: commutative ring :type base_ring: optional, default ``ZZ`` :param subcomplex: a subcomplex of this simplicial complex. Compute the chain complex relative to this subcomplex. :type subcomplex: optional, default empty :param augmented: If ``True``, return the augmented chain complex (that is, include a class in dimension `-1` corresponding to the empty cell). This is ignored if ``dimensions`` is specified. :type augmented: boolean; optional, default ``False`` :param cochain: If ``True``, return the cochain complex (that is, the dual of the chain complex). :type cochain: boolean; optional, default ``False`` :param verbose: If ``True``, print some messages as the chain complex is computed. :type verbose: boolean; optional, default ``False`` :param check: If ``True``, make sure that the chain complex is actually a chain complex: the differentials are composable and their product is zero. :type check: boolean; optional, default ``False``
.. NOTE::
If subcomplex is nonempty, then the argument ``augmented`` has no effect: the chain complex relative to a nonempty subcomplex is zero in dimension `-1`.
The rows and columns of the boundary matrices are indexed by the lists given by the :meth:`n_cells` method, which by default are sorted.
EXAMPLES::
sage: circle = SimplicialComplex([[0,1], [1,2], [0, 2]]) sage: circle.chain_complex() Chain complex with at most 2 nonzero terms over Integer Ring sage: circle.chain_complex()._latex_() '\\Bold{Z}^{3} \\xrightarrow{d_{1}} \\Bold{Z}^{3}' sage: circle.chain_complex(base_ring=QQ, augmented=True) Chain complex with at most 3 nonzero terms over Rational Field """ # initialize subcomplex else: # subcomplex is not empty, so don't augment the chain complex # Use an immutable copy of the subcomplex sort_facets=False, is_mutable=False) # now construct the range of dimensions in which to compute else: # in the chain complex, compute the first dimension by hand, # and don't cache it: it may be differ from situation to # situation because of boundary effects. [1]*len(current)) else: [1]*len(current)) else: # first > 0 print(" starting dimension %s" % n) else: print(" boundary matrix (cached): it's %s by %s." % (mat.nrows(), mat.ncols())) else: # 'current' is the list of faces in dimension n # # 'old' is a dictionary, with keys the faces in the # previous dimension (dim n-1 for the chain complex, # n+1 for the cochain complex), values the integers 0, # 1, 2, ... (the index of the face). finding an entry # in a dictionary seems to be faster than finding the # index of an entry in a list. else: # construct matrix. it is easiest to construct it as # a sparse matrix, specifying which entries are # nonzero via a dictionary. else: print(" boundary matrix computed: it's %s by %s." % (mat.nrows(), mat.ncols())) # now for the cochain complex, compute the last dimension by # hand, and don't cache it. # finally, return the chain complex base_ring=base_ring, check=check) else: base_ring=base_ring, check=check)
def _homology_(self, dim=None, base_ring=ZZ, subcomplex=None, cohomology=False, enlarge=True, algorithm='pari', verbose=False, reduced=True): """ The (reduced) homology of this simplicial complex.
:param dim: If ``None``, then return the homology in every dimension. If ``dim`` is an integer or list, return the homology in the given dimensions. (Actually, if ``dim`` is a list, return the homology in the range from ``min(dim)`` to ``max(dim)``.)
:type dim: integer or list of integers or ``None``; optional, default ``None``
:param base_ring: commutative ring. Must be ``ZZ`` or a field.
:type base_ring: optional, default ``ZZ``
:param subcomplex: a subcomplex of this simplicial complex. Compute homology relative to this subcomplex.
:type subcomplex: optional, default ``None``
:param cohomology: If ``True``, compute cohomology rather than homology.
:type cohomology: boolean; optional, default ``False``
:param enlarge: If ``True``, find a new subcomplex homotopy equivalent to, and probably larger than, the given one.
:type enlarge: boolean; optional, default ``True``
:param algorithm: The options are ``'auto'``, ``'dhsw'``, ``'pari'`` or ``'no_chomp'``. If ``'auto'``, first try CHomP, then use the Dumas, Heckenbach, Saunders, and Welker elimination algorithm for large matrices, Pari for small ones. If ``'no_chomp'``, then don't try CHomP, but behave the same otherwise. If ``'pari'``, then compute elementary divisors using Pari. If ``'dhsw'``, then use the DHSW algorithm to compute elementary divisors. (As of this writing, ``'pari'`` is the fastest standard option. The optional CHomP package may be better still.)
:type algorithm: string; optional, default ``'pari'``
:param verbose: If ``True``, print some messages as the homology is computed.
:type verbose: boolean; optional, default ``False``
:param reduced: If ``True``, return the reduced homology.
:type reduced: boolean; optional, default ``True``
Algorithm: if ``subcomplex`` is ``None``, replace it with a facet -- a contractible subcomplex of the original complex. Then as long as ``enlarge`` is ``True``, no matter what ``subcomplex`` is, replace it with a subcomplex `L` which is homotopy equivalent and as large as possible. Compute the homology of the original complex relative to `L`: if `L` is large, then the relative chain complex will be small enough to speed up computations considerably.
EXAMPLES::
sage: circle = SimplicialComplex([[0,1], [1,2], [0, 2]]) sage: circle._homology_() {0: 0, 1: Z} sage: sphere = SimplicialComplex([[0,1,2,3]]) sage: sphere.remove_face([0,1,2,3]) sage: sphere Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (0, 1, 2), (1, 2, 3), (0, 1, 3)} sage: sphere._homology_() {0: 0, 1: 0, 2: Z} sage: sphere._homology_(reduced=False) {0: Z, 1: 0, 2: Z} sage: sphere._homology_(base_ring=GF(2), reduced=False) {0: Vector space of dimension 1 over Finite Field of size 2, 1: Vector space of dimension 0 over Finite Field of size 2, 2: Vector space of dimension 1 over Finite Field of size 2}
Another way to get a two-sphere: take a two-point space and take its three-fold join with itself::
sage: S = SimplicialComplex([[0], [1]]) sage: (S*S*S)._homology_(dim=2, cohomology=True) Z
The same computation, done without finding a contractible subcomplex::
sage: (S*S*S)._homology_(dim=2, cohomology=True, enlarge=False) Z
Relative homology::
sage: T = SimplicialComplex([[0,1,2]]) sage: U = SimplicialComplex([[0,1], [1,2], [0,2]]) sage: T._homology_(subcomplex=U) {0: 0, 1: 0, 2: Z} """
else: else:
print("starting calculation of the homology of this") print("%s-dimensional simplicial complex" % self.dimension()) print("Constructing contractible subcomplex...") print("Done finding contractible subcomplex.") vec = [len(self.faces(subcomplex=L)[n-1]) for n in range(self.dimension()+2)] print("The difference between the f-vectors is:") print(" %s" % vec) else: else: print("Enlarging subcomplex...") print("Done enlarging subcomplex:") else: L = subcomplex
print("Computing the chain complex...") cochain=cohomology, base_ring=base_ring, subcomplex=L, verbose=verbose) print(" Done computing the chain complex. ") print("Now computing homology...") algorithm=algorithm)
# Fix non-reduced answer. else:
# This is cached for speed reasons: it can be very slow to run # this function. @cached_method def algebraic_topological_model(self, base_ring=None): r""" Algebraic topological model for this simplicial complex with coefficients in ``base_ring``.
The term "algebraic topological model" is defined by Pilarczyk and Réal [PR2015]_.
INPUT:
- ``base_ring`` - coefficient ring (optional, default ``QQ``). Must be a field.
Denote by `C` the chain complex associated to this simplicial complex. The algebraic topological model is a chain complex `M` with zero differential, with the same homology as `C`, along with chain maps `\pi: C \to M` and `\iota: M \to C` satisfying `\iota \pi = 1_M` and `\pi \iota` chain homotopic to `1_C`. The chain homotopy `\phi` must satisfy
- `\phi \phi = 0`, - `\pi \phi = 0`, - `\phi \iota = 0`.
Such a chain homotopy is called a *chain contraction*.
OUTPUT: a pair consisting of
- chain contraction ``phi`` associated to `C`, `M`, `\pi`, and `\iota` - the chain complex `M`
Note that from the chain contraction ``phi``, one can recover the chain maps `\pi` and `\iota` via ``phi.pi()`` and ``phi.iota()``. Then one can recover `C` and `M` from, for example, ``phi.pi().domain()`` and ``phi.pi().codomain()``, respectively.
EXAMPLES::
sage: RP2 = simplicial_complexes.RealProjectivePlane() sage: phi, M = RP2.algebraic_topological_model(GF(2)) sage: M.homology() {0: Vector space of dimension 1 over Finite Field of size 2, 1: Vector space of dimension 1 over Finite Field of size 2, 2: Vector space of dimension 1 over Finite Field of size 2} sage: T = simplicial_complexes.Torus() sage: phi, M = T.algebraic_topological_model(QQ) sage: M.homology() {0: Vector space of dimension 1 over Rational Field, 1: Vector space of dimension 2 over Rational Field, 2: Vector space of dimension 1 over Rational Field} """ base_ring = QQ
def alexander_whitney(self, simplex, dim_left): r""" Subdivide this simplex into a pair of simplices.
If this simplex has vertices `v_0`, `v_1`, ..., `v_n`, then subdivide it into simplices `(v_0, v_1, ..., v_{dim})` and `(v_{dim}, v_{dim + 1}, ..., v_n)`.
See :meth:`Simplex.alexander_whitney` for more details. This method just calls that one.
INPUT:
- ``simplex`` -- a simplex in this complex - ``dim`` -- integer between 0 and one more than the dimension of this simplex
OUTPUT: a list containing just the triple ``(1, left, right)``, where ``left`` and ``right`` are the two simplices described above.
EXAMPLES::
sage: s = Simplex((0,1,3,4)) sage: X = SimplicialComplex([s]) sage: X.alexander_whitney(s, 0) [(1, (0,), (0, 1, 3, 4))] sage: X.alexander_whitney(s, 2) [(1, (0, 1, 3), (3, 4))] """
def add_face(self, face): """ Add a face to this simplicial complex.
:param face: a subset of the vertex set
This *changes* the simplicial complex, adding a new face and all of its subfaces.
EXAMPLES::
sage: X = SimplicialComplex([[0,1], [0,2]]) sage: X.add_face([0,1,2,]); X Simplicial complex with vertex set (0, 1, 2) and facets {(0, 1, 2)} sage: Y = SimplicialComplex(); Y Simplicial complex with vertex set () and facets {()} sage: Y.add_face([0,1]) sage: Y.add_face([1,2,3]) sage: Y Simplicial complex with vertex set (0, 1, 2, 3) and facets {(1, 2, 3), (0, 1)}
If you add a face which is already present, there is no effect::
sage: Y.add_face([1,3]); Y Simplicial complex with vertex set (0, 1, 2, 3) and facets {(1, 2, 3), (0, 1)}
TESTS:
Check that the bug reported at :trac:`14354` has been fixed::
sage: T = SimplicialComplex([range(1,5)]).n_skeleton(1) sage: T.homology(algorithm='no_chomp') {0: 0, 1: Z x Z x Z} sage: T.add_face([1,2,3]) sage: T.homology(algorithm='no_chomp') {0: 0, 1: Z x Z, 2: 0}
Check that the ``_faces`` cache is treated correctly (:trac:`20758`)::
sage: T = SimplicialComplex([range(1,5)]).n_skeleton(1) sage: _ = T.faces() # populate the _faces attribute sage: _ = T.homology() # add more to _faces sage: T.add_face((1,2,3)) sage: all(Simplex((1,2,3)) in T._faces[L][2] for L in T._faces) True
Check that the ``__enlarged`` cache is treated correctly (:trac:`20758`)::
sage: T = SimplicialComplex([range(1,5)]).n_skeleton(1) sage: T.homology(algorithm='no_chomp') # to populate the __enlarged attribute {0: 0, 1: Z x Z x Z} sage: T.add_face([1,2,3]) sage: len(T._SimplicialComplex__enlarged) > 0 True
Check we've fixed the bug reported at :trac:`14578`::
sage: t0 = SimplicialComplex() sage: t0.add_face(('a', 'b')) sage: t0.add_face(('c', 'd', 'e')) sage: t0.add_face(('e', 'f', 'c')) sage: t0.homology() {0: Z, 1: 0, 2: 0}
Check that we've fixed the bug reported at :trac:`22880`::
sage: X = SimplicialComplex([[0], [1]]) sage: temp = X.faces(SimplicialComplex(())) sage: X.add_face([0,1]) """
else:
# remove any old facets which are no longer maximal # add new_face to facet list
# Update the vertex set
# Update self._faces. else: else: # update self._graph if necessary d = new_face.dimension()+1 for i in range(d): for j in range(i + 1, d): self._graph.add_edge(new_face[i], new_face[j])
def remove_face(self, face): """ Remove a face from this simplicial complex and return the resulting simplicial complex.
:param face: a face of the simplicial complex
This *changes* the simplicial complex.
ALGORITHM:
The facets of the new simplicial complex are the facets of the original complex not containing ``face``, together with those of ``link(face)*boundary(face)``.
EXAMPLES::
sage: S = range(1,5) sage: Z = SimplicialComplex([S]); Z Simplicial complex with vertex set (1, 2, 3, 4) and facets {(1, 2, 3, 4)} sage: Z.remove_face([1,2]) sage: Z Simplicial complex with vertex set (1, 2, 3, 4) and facets {(1, 3, 4), (2, 3, 4)}
sage: S = SimplicialComplex([[0,1,2],[2,3]]) sage: S Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 1, 2), (2, 3)} sage: S.remove_face([0,1,2]) sage: S Simplicial complex with vertex set (0, 1, 2, 3) and facets {(1, 2), (2, 3), (0, 2), (0, 1)}
TESTS:
Check that the ``_faces`` cache is treated properly: see :trac:`20758`::
sage: T = SimplicialComplex([range(1,5)]).n_skeleton(1) sage: _ = T.faces() # populate the _faces attribute sage: _ = T.homology(algorithm='no_chomp') # add more to _faces sage: T.add_face((1,2,3)) sage: T.remove_face((1,2,3)) sage: len(T._faces) 2 sage: T.remove_face((3,4)) sage: len(T._faces) 1 """
# face is not in self: nothing to remove return self # join_facets is the list of facets in the join bdry(face) * link(face)
# Check to see if there are any non-maximal faces # build set of facets # if no maximal faces, add the empty face as a facet self._facets.append(Simplex(-1))
# Recreate the vertex set
# Update self._faces. # Note: can't iterate over self._faces, because the dictionary # size may change during iteration. # Update self._graph if necessary. # Only if removing a 1 or 2 dim face will the graph be affected if len(face) == 1: self._graph.delete_vertex(face[0]) self._graph.add_vertex(face[0]) elif len(face) == 2: self._graph.delete_edge(face[0], face[1])
def connected_sum(self, other, is_mutable=True): """ The connected sum of this simplicial complex with another one.
:param other: another simplicial complex :param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True`` :return: the connected sum ``self # other``
.. WARNING::
This does not check that ``self`` and ``other`` are manifolds, only that their facets all have the same dimension. Since a (more or less) random facet is chosen from each complex and then glued together, this method may return random results if applied to non-manifolds, depending on which facet is chosen.
Algorithm: a facet is chosen from each surface, and removed. The vertices of these two facets are relabeled to ``(0,1,...,dim)``. Of the remaining vertices, the ones from the left-hand factor are renamed by prepending an "L", and similarly the remaining vertices in the right-hand factor are renamed by prepending an "R".
EXAMPLES::
sage: S1 = simplicial_complexes.Sphere(1) sage: S1.connected_sum(S1.connected_sum(S1)).homology() {0: 0, 1: Z} sage: P = simplicial_complexes.RealProjectivePlane(); P Minimal triangulation of the real projective plane sage: P.connected_sum(P) # the Klein bottle Simplicial complex with 9 vertices and 18 facets
The notation '+' may be used for connected sum, also::
sage: P + P # the Klein bottle Simplicial complex with 9 vertices and 18 facets sage: (P + P).homology()[1] Z x C2 """ self.dimension() == other.dimension()): raise ValueError("Complexes are not pure of the same dimension.") # first find a top-dimensional simplex to remove from each surface # construct the set of vertices: # construct the set of facets: for v in face] for face in left] + [[rename_vertex(v, keep=list(keep_right), left=False) for v in face] for face in right]) # return the new surface
__add__ = connected_sum
def link(self, simplex, is_mutable=True): """ The link of a simplex in this simplicial complex.
The link of a simplex `F` is the simplicial complex formed by all simplices `G` which are disjoint from `F` but for which `F \cup G` is a simplex.
:param simplex: a simplex in this simplicial complex. :param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
EXAMPLES::
sage: X = SimplicialComplex([[0,1,2], [1,2,3]]) sage: X.link(Simplex([0])) Simplicial complex with vertex set (1, 2) and facets {(1, 2)} sage: X.link([1,2]) Simplicial complex with vertex set (0, 3) and facets {(3,), (0,)} sage: Y = SimplicialComplex([[0,1,2,3]]) sage: Y.link([1]) Simplicial complex with vertex set (0, 2, 3) and facets {(0, 2, 3)} """
def star(self, simplex, is_mutable=True): """ Return the star of a simplex in this simplicial complex.
The star of ``simplex`` is the simplicial complex formed by all simplices which contain ``simplex``.
INPUT:
- ``simplex`` -- a simplex in this simplicial complex - ``is_mutable`` -- (default: ``True``) boolean; determines if the output is mutable
EXAMPLES::
sage: X = SimplicialComplex([[0,1,2], [1,2,3]]) sage: X.star(Simplex([0])) Simplicial complex with vertex set (0, 1, 2) and facets {(0, 1, 2)} sage: X.star(Simplex([1])) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 1, 2), (1, 2, 3)} sage: X.star(Simplex([1,2])) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 1, 2), (1, 2, 3)} sage: X.star(Simplex([])) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 1, 2), (1, 2, 3)} """
def is_cohen_macaulay(self, base_ring=QQ, ncpus=0): r""" Return ``True`` if ``self`` is Cohen-Macaulay.
A simplicial complex `\Delta` is Cohen-Macaulay over `R` iff `\tilde{H}_i(\mathrm{lk}_\Delta(F);R) = 0` for all `F \in \Delta` and `i < \dim\mathrm{lk}_\Delta(F)`. Here, `\Delta` is ``self`` and `R` is ``base_ring``, and `\mathrm{lk}` denotes the link operator on ``self``.
INPUT:
- ``base_ring`` -- (default: ``QQ``) the base ring.
- ``ncpus`` -- (default: 0) number of cpus used for the computation. If this is 0, determine the number of cpus automatically based on the hardware being used.
For finite simplicial complexes, this is equivalent to the statement that the Stanley-Reisner ring of ``self`` is Cohen-Macaulay.
EXAMPLES:
Spheres are Cohen-Macaulay::
sage: S = SimplicialComplex([[1,2],[2,3],[3,1]]) sage: S.is_cohen_macaulay(ncpus=3) True
The following example is taken from Bruns, Herzog - Cohen-Macaulay rings, Figure 5.3::
sage: S = SimplicialComplex([[1,2,3],[1,4,5]]) sage: S.is_cohen_macaulay(ncpus=3) ... False
The choice of base ring can matter. The real projective plane `\RR P^2` has `H_1(\RR P^2) = \ZZ/2`, hence is CM over `\QQ` but not over `\ZZ`. ::
sage: X = simplicial_complexes.RealProjectivePlane() sage: X.is_cohen_macaulay() True sage: X.is_cohen_macaulay(ZZ) False """
S = self.link(F) H = S.homology(base_ring=base_ring) if base_ring.is_field(): return all( H[j].dimension() == 0 for j in range(S.dimension()) ) else: return not any( H[j].invariants() for j in range(S.dimension()) )
def all_homologies_in_list_vanish(Fs): return all( all_homologies_vanish(F) for F in Fs )
def generated_subcomplex(self, sub_vertex_set, is_mutable=True): """ Returns the largest sub-simplicial complex of ``self`` containing exactly ``sub_vertex_set`` as vertices.
:param sub_vertex_set: The sub-vertex set. :param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
EXAMPLES::
sage: S = simplicial_complexes.Sphere(2) sage: S Minimal triangulation of the 2-sphere sage: S.generated_subcomplex([0,1,2]) Simplicial complex with vertex set (0, 1, 2) and facets {(0, 1, 2)}
""" raise ValueError("input must be a subset of the vertex set") is_mutable=is_mutable)
def is_shelling_order(self, shelling_order, certificate=False): r""" Return if the order of the facets given by ``shelling_order`` is a shelling order for ``self``.
A sequence of facets `(F_i)_{i=1}^N` of a simplicial complex of dimension `d` is a *shelling order* if for all `i = 2, 3, 4, \ldots`, the complex
.. MATH::
X_i = \left( \bigcup_{j=1}^{i-1} F_j \right) \cap F_i
is pure and of dimension `\dim F_i - 1`.
INPUT:
- ``shelling_order`` -- an ordering of the facets of ``self`` - ``certificate`` -- (default: ``False``) if ``True`` then returns the index of the first facet that violate the condition
.. SEEALSO::
:meth:`is_shellable`
EXAMPLES::
sage: facets = [[1,2,5],[2,3,5],[3,4,5],[1,4,5]] sage: X = SimplicialComplex(facets) sage: X.is_shelling_order(facets) True
sage: b = [[1,2,5], [3,4,5], [2,3,5], [1,4,5]] sage: X.is_shelling_order(b) False sage: X.is_shelling_order(b, True) (False, 1)
A non-pure example::
sage: facets = [[1,2,3], [3,4], [4,5], [5,6], [4,6]] sage: X = SimplicialComplex(facets) sage: X.is_shelling_order(facets) True
REFERENCES:
- [BW1996]_ """ # Quick check by Lemma 2.2 in [BW1996] return False
# The shelling condition is precisely that intersection is # a pure complex of one dimension less and stop if this fails
@cached_method def is_shellable(self, certificate=False): r""" Return if ``self`` is shellable.
A simplicial complex is shellable if there exists a shelling order.
.. NOTE::
1. This method can check all orderings of the facets by brute force, hence can be very slow.
2. This is shellability in the general (nonpure) sense of Bjorner and Wachs [BW1996]_. This method does not check purity.
.. SEEALSO::
:meth:`is_shelling_order`
INPUT:
- ``certificate`` -- (default: ``False``) if ``True`` then returns the shelling order (if it exists)
EXAMPLES::
sage: X = SimplicialComplex([[1,2,5], [2,3,5], [3,4,5], [1,4,5]]) sage: X.is_shellable() True sage: order = X.is_shellable(True); order ((2, 3, 5), (1, 2, 5), (1, 4, 5), (3, 4, 5)) sage: X.is_shelling_order(order) True
sage: X = SimplicialComplex([[1,2,3], [3,4,5]]) sage: X.is_shellable() False
Examples from Figure 1 in [BW1996]_::
sage: X = SimplicialComplex([[1,2,3], [3,4], [4,5], [5,6], [4,6]]) sage: X.is_shellable() True
sage: X = SimplicialComplex([[1,2,3], [3,4], [4,5,6]]) sage: X.is_shellable() False
REFERENCES:
- :wikipedia:`Shelling_(topology)` """
else: # Non-pure complex
except StopIteration: # Backtrace if not cur_order: return False it.pop() facets.add(cur_order.pop()) cur_complex = SimplicialComplex(cur_order) continue
# First facet must be top dimensional continue
# The shelling condition is precisely that intersection is # a pure complex of one dimension less and stop if this fails
or F.dimension() - 1 != intersection.dimension()):
def restriction_sets(self, order): """ Return the restriction sets of the facets according to ``order``.
A restriction set of a shelling order is the sequence of smallest new faces that are created during the shelling order.
.. SEEALSO::
:meth:`is_shelling_order`
EXAMPLES::
sage: facets = [[1,2,5], [2,3,5], [3,4,5], [1,4,5]] sage: X = SimplicialComplex(facets) sage: X.restriction_sets(facets) [(), (3,), (4,), (1, 4)]
sage: b = [[1,2,5], [3,4,5], [2,3,5], [1,4,5]] sage: X.restriction_sets(b) Traceback (most recent call last): ... ValueError: not a shelling order """ # It starts with the first empty
# Each time we hit a facet, the complement goes to the restriction # The shelling condition is precisely that intersection is # a pure complex of one dimension less and stop if this fails
def _complement(self, simplex): """ Return the complement of a simplex in the vertex set of this simplicial complex.
:param simplex: a simplex (need not be in the simplicial complex)
OUTPUT: its complement: the simplex formed by the vertices not contained in ``simplex``.
Note that this only depends on the vertex set of the simplicial complex, not on its simplices.
EXAMPLES::
sage: X = SimplicialComplex([[0,1,2,3,4,5]]) sage: X._complement([1,2,3]) (0, 4, 5) sage: X._complement([0,1,3,4]) (2, 5) sage: X._complement([0,4,1,3]) (2, 5) """
def _transpose_simplices(self, *simplices): """ Given tuple ``L`` of simplices, returns new list, where each simplex is formed by taking a vertex from each simplex from ``L``.
:param simplices: a bunch of simplices
If ``simplices`` consists of `(f_0, f_1, f_2, ...)`, then the output consists of all possible simplices of the form `(v_0, v_1, v_2, ...)`, where `v_i` is a vertex of `f_i`. If a vertex appears more than once in such a simplex, remove all but one of its appearances. If such a simplex contains others already produced, then ignore that larger simplex -- the output should be a list of minimal simplices constructed in this way.
This is used in computing the minimal nonfaces and hence the Stanley-Reisner ring.
Note that this only depends on the vertex set of the simplicial complex, not on its simplices.
I don't know if there is a standard name for this, but it looked sort of like the transpose of a matrix; hence the name for this method.
EXAMPLES::
sage: X = SimplicialComplex() sage: X._transpose_simplices([1,2]) [(1,), (2,)] sage: X._transpose_simplices([1,2], [3,4]) [(1, 3), (1, 4), (2, 3), (2, 4)]
In the following example, one can construct the simplices ``(1,2)`` and ``(1,3)``, but you can also construct ``(1,1) = (1,)``, which is a face of both of the others. So the answer omits ``(1,2)`` and ``(1,3)``::
sage: X._transpose_simplices([1,2], [1,3]) [(1,), (2, 3)] """ else: simplices_to_delete.append(already) answer.remove(x)
def minimal_nonfaces(self): """ Set consisting of the minimal subsets of the vertex set of this simplicial complex which do not form faces.
Algorithm: Proceeds through the faces of the complex increasing the dimension, starting from dimension 0, and add the faces that are not contained in the complex and that are not already contained in a previously seen minimal non-face.
This is used in computing the :meth:`Stanley-Reisner ring<stanley_reisner_ring>` and the :meth:`Alexander dual<alexander_dual>`.
EXAMPLES::
sage: X = SimplicialComplex([[1,3],[1,2]]) sage: X.minimal_nonfaces() {(2, 3)} sage: Y = SimplicialComplex([[0,1], [1,2], [2,3], [3,0]]) sage: Y.minimal_nonfaces() {(1, 3), (0, 2)}
TESTS::
sage: SC = SimplicialComplex([(0,1,2),(0,2,3),(2,3,4),(1,2,4), \ (1,4,5),(0,3,6),(3,6,7),(4,5,7)]) sage: SC.minimal_nonfaces() # This was taking a long time before :trac:`20078` {(3, 4, 7), (0, 7), (0, 4), (0, 5), (3, 5), (1, 7), (2, 5), (5, 6), (1, 3), (4, 6), (2, 7), (2, 6), (1, 6)}
"""
def _stanley_reisner_base_ring(self, base_ring=ZZ): """ The polynomial algebra of which the Stanley-Reisner ring is a quotient.
:param base_ring: a commutative ring :type base_ring: optional, default ``ZZ`` :return: a polynomial algebra with coefficients in base_ring, with one generator for each vertex in the simplicial complex.
See the documentation for :meth:`stanley_reisner_ring` for a warning about the names of the vertices.
EXAMPLES::
sage: X = SimplicialComplex([[1,2], [0], [3]]) sage: X._stanley_reisner_base_ring() Multivariate Polynomial Ring in x0, x1, x2, x3 over Integer Ring sage: Y = SimplicialComplex([['a', 'b', 'c']]) sage: Y._stanley_reisner_base_ring(base_ring=QQ) Multivariate Polynomial Ring in a, c, b over Rational Field """
def stanley_reisner_ring(self, base_ring=ZZ): """ The Stanley-Reisner ring of this simplicial complex.
:param base_ring: a commutative ring :type base_ring: optional, default ``ZZ`` :return: a quotient of a polynomial algebra with coefficients in ``base_ring``, with one generator for each vertex in the simplicial complex, by the ideal generated by the products of those vertices which do not form faces in it.
Thus the ideal is generated by the products corresponding to the minimal nonfaces of the simplicial complex.
.. WARNING::
This may be quite slow!
Also, this may behave badly if the vertices have the 'wrong' names. To avoid this, define the simplicial complex at the start with the flag ``name_check`` set to ``True``.
More precisely, this is a quotient of a polynomial ring with one generator for each vertex. If the name of a vertex is a non-negative integer, then the corresponding polynomial generator is named ``'x'`` followed by that integer (e.g., ``'x2'``, ``'x3'``, ``'x5'``, ...). Otherwise, the polynomial generators are given the same names as the vertices. Thus if the vertex set is ``(2, 'x2')``, there will be problems.
EXAMPLES::
sage: X = SimplicialComplex([[0,1], [1,2], [2,3], [0,3]]) sage: X.stanley_reisner_ring() Quotient of Multivariate Polynomial Ring in x0, x1, x2, x3 over Integer Ring by the ideal (x1*x3, x0*x2) sage: Y = SimplicialComplex([[0,1,2,3,4]]); Y Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 2, 3, 4)} sage: Y.add_face([0,1,2,3,4]) sage: Y.stanley_reisner_ring(base_ring=QQ) Multivariate Polynomial Ring in x0, x1, x2, x3, x4 over Rational Field """
def alexander_dual(self, is_mutable=True): """ The Alexander dual of this simplicial complex: according to the Macaulay2 documentation, this is the simplicial complex whose faces are the complements of its nonfaces.
Thus find the minimal nonfaces and take their complements to find the facets in the Alexander dual.
:param is_mutable: Determines if the output is mutable :type is_mutable: boolean; optional, default ``True``
EXAMPLES::
sage: Y = SimplicialComplex([[i] for i in range(5)]); Y Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(4,), (2,), (3,), (0,), (1,)} sage: Y.alexander_dual() Simplicial complex with vertex set (0, 1, 2, 3, 4) and 10 facets sage: X = SimplicialComplex([[0,1], [1,2], [2,3], [3,0]]) sage: X.alexander_dual() Simplicial complex with vertex set (0, 1, 2, 3) and facets {(1, 3), (0, 2)} """
def barycentric_subdivision(self): """ The barycentric subdivision of this simplicial complex.
See :wikipedia:`Barycentric_subdivision` for a definition.
EXAMPLES::
sage: triangle = SimplicialComplex([[0,1], [1,2], [0, 2]]) sage: hexagon = triangle.barycentric_subdivision() sage: hexagon Simplicial complex with 6 vertices and 6 facets sage: hexagon.homology(1) == triangle.homology(1) True
Barycentric subdivisions can get quite large, since each `n`-dimensional facet in the original complex produces `(n+1)!` facets in the subdivision::
sage: S4 = simplicial_complexes.Sphere(4) sage: S4 Minimal triangulation of the 4-sphere sage: S4.barycentric_subdivision() Simplicial complex with 62 vertices and 720 facets """
def stellar_subdivision(self, simplex, inplace=False, is_mutable=True): """ Return the stellar subdivision of a simplex in this simplicial complex.
The stellar subdivision of a face is obtained by adding a new vertex to the simplicial complex ``self`` joined to the star of the face and then deleting the face ``simplex`` to the result.
INPUT:
- ``simplex`` -- a simplex face of ``self`` - ``inplace`` -- (default: ``False``) boolean; determines if the operation is done on ``self`` or on a copy - ``is_mutable`` -- (default: ``True``) boolean; determines if the output is mutable
OUTPUT:
- A simplicial complex obtained by the stellar subdivision of the face ``simplex``
EXAMPLES::
sage: SC = SimplicialComplex([[0,1,2],[1,2,3]]) sage: F1 = Simplex([1,2]) sage: F2 = Simplex([1,3]) sage: F3 = Simplex([1,2,3]) sage: SC.stellar_subdivision(F1) Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 4), (1, 3, 4), (2, 3, 4), (0, 2, 4)} sage: SC.stellar_subdivision(F2) Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 2), (2, 3, 4), (1, 2, 4)} sage: SC.stellar_subdivision(F3) Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(1, 3, 4), (0, 1, 2), (2, 3, 4), (1, 2, 4)} sage: SC.stellar_subdivision(F3, inplace=True);SC Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(1, 3, 4), (0, 1, 2), (2, 3, 4), (1, 2, 4)}
The simplex to subdivide should be a face of self::
sage: SC = SimplicialComplex([[0,1,2],[1,2,3]]) sage: F4 = Simplex([3,4]) sage: SC.stellar_subdivision(F4) Traceback (most recent call last): ... ValueError: the face to subdivide is not a face of self
One can not modify an immutable simplicial complex::
sage: SC = SimplicialComplex([[0,1,2],[1,2,3]], is_mutable=False) sage: SC.stellar_subdivision(F1, inplace=True) Traceback (most recent call last): ... ValueError: this simplicial complex is not mutable """
else:
else:
working_complex.set_immutable()
def graph(self): """ The 1-skeleton of this simplicial complex, as a graph.
.. WARNING::
This may give the wrong answer if the simplicial complex was constructed with ``maximality_check`` set to ``False``.
EXAMPLES::
sage: S = SimplicialComplex([[0,1,2,3]]) sage: G = S.graph(); G Graph on 4 vertices sage: G.edges() [(0, 1, None), (0, 2, None), (0, 3, None), (1, 2, None), (1, 3, None), (2, 3, None)] """ else:
def delta_complex(self, sort_simplices=False): r""" Returns ``self`` as a `\Delta`-complex. The `\Delta`-complex is essentially identical to the simplicial complex: it has same simplices with the same boundaries.
:param sort_simplices: if ``True``, sort the list of simplices in each dimension :type sort_simplices: boolean; optional, default ``False``
EXAMPLES::
sage: T = simplicial_complexes.Torus() sage: Td = T.delta_complex() sage: Td Delta complex with 7 vertices and 43 simplices sage: T.homology() == Td.homology() True """
def is_flag_complex(self): """ Returns ``True`` if and only if ``self`` is a flag complex.
A flag complex is a simplicial complex that is the largest simplicial complex on its 1-skeleton. Thus a flag complex is the clique complex of its graph.
EXAMPLES::
sage: h = Graph({0:[1,2,3,4],1:[2,3,4],2:[3]}) sage: x = h.clique_complex() sage: x Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 4), (0, 1, 2, 3)} sage: x.is_flag_complex() True
sage: X = simplicial_complexes.ChessboardComplex(3,3) sage: X.is_flag_complex() True """
def n_skeleton(self, n): """ The `n`-skeleton of this simplicial complex.
The `n`-skeleton of a simplicial complex is obtained by discarding all of the simplices in dimensions larger than `n`.
:param n: non-negative integer
EXAMPLES::
sage: X = SimplicialComplex([[0,1], [1,2,3], [0,2,3]]) sage: X.n_skeleton(1) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(2, 3), (0, 2), (1, 3), (1, 2), (0, 3), (0, 1)} sage: X.set_immutable() sage: X.n_skeleton(2) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (1, 2, 3), (0, 1)} sage: X.n_skeleton(4) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (1, 2, 3), (0, 1)} """ # make sure it's a list (it will be a tuple if immutable)
def _contractible_subcomplex(self, verbose=False): """ Find a contractible subcomplex `L` of this simplicial complex, preferably one which is as large as possible.
:param verbose: If ``True``, print some messages as the simplicial complex is computed. :type verbose: boolean; optional, default ``False``
Motivation: if `K` is the original complex and if `L` is contractible, then the relative homology `H_*(K,L)` is isomorphic to the reduced homology of `K`. If `L` is large, then the relative chain complex will be a good deal smaller than the augmented chain complex for `K`, and this leads to a speed improvement for computing the homology of `K`.
This just passes an immutable subcomplex consisting of a facet to the method ``_enlarge_subcomplex``.
.. NOTE::
Thus when the simplicial complex is empty, so is the resulting 'contractible subcomplex', which is therefore not technically contractible. In this case, that doesn't matter because the homology is computed correctly anyway.
EXAMPLES::
sage: sphere = SimplicialComplex([[0,1,2,3]]) sage: sphere.remove_face([0,1,2,3]) sage: sphere Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (0, 1, 2), (1, 2, 3), (0, 1, 3)} sage: L = sphere._contractible_subcomplex(); L Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (1, 2, 3), (0, 1, 3)} sage: L.homology() {0: 0, 1: 0, 2: 0} """
def _enlarge_subcomplex(self, subcomplex, verbose=False): """ Given a subcomplex `S` of this simplicial complex `K`, find a subcomplex `L`, as large as possible, containing `S` which is homotopy equivalent to `S` (so that `H_{*}(K,S)` is isomorphic to `H_{*}(K,L)`). This way, the chain complex for computing `H_{*}(K,L)` will be smaller than that for computing `H_{*}(K,S)`, so the computations should be faster.
:param subcomplex: a subcomplex of this simplicial complex :param verbose: If ``True``, print some messages as the simplicial complex is computed. :type verbose: boolean; optional, default ``False`` :return: a complex `L` containing ``subcomplex`` and contained in ``self``, homotopy equivalent to ``subcomplex``.
Algorithm: start with the subcomplex `S` and loop through the facets of `K` which are not in `S`. For each one, see whether its intersection with `S` is contractible, and if so, add it. This is recursive: testing for contractibility calls this routine again, via ``_contractible_subcomplex``.
EXAMPLES::
sage: T = simplicial_complexes.Torus(); T Minimal triangulation of the torus
Inside the torus, define a subcomplex consisting of a loop::
sage: S = SimplicialComplex([[0,1], [1,2], [0,2]], is_mutable=False) sage: S.homology() {0: 0, 1: Z} sage: L = T._enlarge_subcomplex(S) sage: L Simplicial complex with vertex set (0, 1, 2, 3, 4, 5, 6) and 8 facets sage: L.facets() {(0, 1, 5), (1, 3, 6), (1, 2), (1, 2, 4), (1, 3, 4), (0, 2), (1, 5, 6), (0, 1)} sage: L.homology()[1] Z """ # Make the subcomplex immutable if not maximality_check=False, sort_facets=False, is_mutable=False)
print(" looping through %s facets" % len(faces)) intersection == intersection._contractible_subcomplex()): print(" added %s facets" % len(remove_these)) print(" now constructing a simplicial complex with %s vertices and %s facets" % (len(self.vertices()), len(new_facets))) sort_facets=False, is_mutable=self._is_mutable)
def _cubical_(self): r""" Cubical complex constructed from ``self``.
ALGORITHM:
The algorithm comes from a paper by Shtan'ko and Shtogrin, as reported by Bukhshtaber and Panov. Let `I^m` denote the unit `m`-cube, viewed as a cubical complex. Let `[m] = \{1, 2, ..., m\}`; then each face of `I^m` has the following form, for subsets `I \subset J \subset [m]`:
.. MATH::
F_{I \subset J} = \{ (y_1,...,y_m) \in I^m \,:\, y_i =0 \text{ for } i \in I, y_j = 1 \text{ for } j \not \in J\}.
If `K` is a simplicial complex on vertex set `[m]` and if `I \subset [m]`, write `I \in K` if `I` is a simplex of `K`. Then we associate to `K` the cubical subcomplex of `I^m` with faces
.. MATH::
\{F_{I \subset J} \,:\, J \in K, I \neq \emptyset \}
The geometric realization of this cubical complex is homeomorphic to the geometric realization of the original simplicial complex.
REFERENCES:
- [BP2000]_ - [SS1992]_
EXAMPLES::
sage: T = simplicial_complexes.Torus() sage: T.homology() {0: 0, 1: Z x Z, 2: Z} sage: Tc = T._cubical_() sage: Tc Cubical complex with 42 vertices and 168 cubes sage: Tc.homology() {0: 0, 1: Z x Z, 2: Z} """ # dictionary to translate vertices to the numbers 1, ..., embed # loop over indices from 1 to embed. if equal to i, # set to 0. if not in J, set to 1. Otherwise, range # from 0 to 1 else:
def connected_component(self, simplex=None): """ Return the connected component of this simplicial complex containing ``simplex``. If ``simplex`` is omitted, then return the connected component containing the zeroth vertex in the vertex list. (If the simplicial complex is empty, raise an error.)
EXAMPLES::
sage: S1 = simplicial_complexes.Sphere(1) sage: S1 == S1.connected_component() True sage: X = S1.disjoint_union(S1) sage: X == X.connected_component() False sage: v0 = X.vertices()[0] sage: v1 = X.vertices()[-1] sage: X.connected_component(Simplex([v0])) == X.connected_component(Simplex([v1])) False
sage: S0 = simplicial_complexes.Sphere(0) sage: S0.vertices() (0, 1) sage: S0.connected_component() Simplicial complex with vertex set (0,) and facets {(0,)} sage: S0.connected_component(Simplex((1,))) Simplicial complex with vertex set (1,) and facets {(1,)}
sage: SimplicialComplex([[]]).connected_component() Traceback (most recent call last): ... ValueError: the empty simplicial complex has no connected components. """ else:
def fundamental_group(self, base_point=None, simplify=True): r""" Return the fundamental group of this simplicial complex.
INPUT:
- ``base_point`` (optional, default None) -- if this complex is not path-connected, then specify a vertex; the fundamental group is computed with that vertex as a base point. If the complex is path-connected, then you may specify a vertex or leave this as its default setting of ``None``. (If this complex is path-connected, then this argument is ignored.)
- ``simplify`` (bool, optional True) -- if False, then return a presentation of the group in terms of generators and relations. If True, the default, simplify as much as GAP is able to.
Algorithm: we compute the edge-path group -- see :wikipedia:`Fundamental_group`. Choose a spanning tree for the 1-skeleton, and then the group's generators are given by the edges in the 1-skeleton; there are two types of relations: `e=1` if `e` is in the spanning tree, and for every 2-simplex, if its edges are `e_0`, `e_1`, and `e_2`, then we impose the relation `e_0 e_1^{-1} e_2 = 1`.
EXAMPLES::
sage: S1 = simplicial_complexes.Sphere(1) sage: S1.fundamental_group() Finitely presented group < e | >
If we pass the argument ``simplify=False``, we get generators and relations in a form which is not usually very helpful. Here is the cyclic group of order 2, for instance::
sage: RP2 = simplicial_complexes.RealProjectiveSpace(2) sage: C2 = RP2.fundamental_group(simplify=False) sage: C2 Finitely presented group < e0, e1, e2, e3, e4, e5, e6, e7, e8, e9 | e0, e3, e4, e7, e9, e5*e2^-1*e0, e7*e2^-1*e1, e8*e3^-1*e1, e8*e6^-1*e4, e9*e6^-1*e5 > sage: C2.simplified() Finitely presented group < e1 | e1^2 >
This is the same answer given if the argument ``simplify`` is True (the default)::
sage: RP2.fundamental_group() Finitely presented group < e1 | e1^2 >
You must specify a base point to compute the fundamental group of a non-connected complex::
sage: K = S1.disjoint_union(RP2) sage: K.fundamental_group() Traceback (most recent call last): ... ValueError: this complex is not connected, so you must specify a base point. sage: v0 = list(K.vertices())[0] sage: K.fundamental_group(base_point=v0) Finitely presented group < e | > sage: v1 = list(K.vertices())[-1] sage: K.fundamental_group(base_point=v1) Finitely presented group < e1 | e1^2 >
Some other examples::
sage: S1.wedge(S1).fundamental_group() Finitely presented group < e0, e1 | > sage: simplicial_complexes.Torus().fundamental_group() Finitely presented group < e1, e4 | e4^-1*e1^-1*e4*e1 > sage: simplicial_complexes.MooreSpace(5).fundamental_group() Finitely presented group < e0 | e0^5 > """
return gap.TrivialGroup()
else: else:
@rename_keyword(deprecation=21111, certify='certificate') def is_isomorphic(self, other, certificate=False): r""" Check whether two simplicial complexes are isomorphic.
INPUT:
- ``certificate`` -- if ``True``, then output is ``(a, b)``, where ``a`` is a boolean and ``b`` is either a map or ``None``
This is done by creating two graphs and checking whether they are isomorphic.
EXAMPLES::
sage: Z1 = SimplicialComplex([[0,1],[1,2],[2,3,4],[4,5]]) sage: Z2 = SimplicialComplex([['a','b'],['b','c'],['c','d','e'],['e','f']]) sage: Z3 = SimplicialComplex([[1,2,3]]) sage: Z1.is_isomorphic(Z2) True sage: Z1.is_isomorphic(Z2, certificate=True) (True, {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f'}) sage: Z3.is_isomorphic(Z2) False
We check that :trac:`20751` is fixed::
sage: C1 = SimplicialComplex([[1,2,3], [1,2,4], [1,3,4]]) sage: C2 = SimplicialComplex([['j','k','l'], ['j','l','m'], ['j','k','m']]) sage: C1.is_isomorphic(C2, certificate=True) (True, {1: 'j', 2: 'k', 3: 'l', 4: 'm'})
TESTS::
sage: Z1 = SimplicialComplex([[0,1],[1,2],[2,3,4],[4,5]]) sage: Z2 = SimplicialComplex([['a','b'],['b','c'],['c','d','e'],['e','f']]) sage: Z1.is_isomorphic(Z2, certify=True) doctest...: DeprecationWarning: use the option 'certificate' instead of 'certify' See http://trac.sagemath.org/21111 for details. (True, {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f'}) """ # Check easy invariants agree != sorted(x.dimension() for x in other._facets) or len(self._vertex_set) != len(other._vertex_set)): for v in self._vertex_set) for v in other._vertex_set)
def automorphism_group(self): r""" Return the automorphism group of the simplicial complex.
This is done by creating a bipartite graph, whose vertices are vertices and facets of the simplicial complex, and computing its automorphism group.
.. WARNING::
Since :trac:`14319` the domain of the automorphism group is equal to the graph's vertex set, and the ``translation`` argument has become useless.
EXAMPLES::
sage: S = simplicial_complexes.Simplex(3) sage: S.automorphism_group().is_isomorphic(SymmetricGroup(4)) True
sage: P = simplicial_complexes.RealProjectivePlane() sage: P.automorphism_group().is_isomorphic(AlternatingGroup(5)) True
sage: Z = SimplicialComplex([['1','2'],['2','3','a']]) sage: Z.automorphism_group().is_isomorphic(CyclicPermutationGroup(2)) True sage: group = Z.automorphism_group() sage: group.domain() {'1', '2', '3', 'a'}
Check that :trac:`17032` is fixed::
sage: s = SimplicialComplex([[(0,1),(2,3)]]) sage: s.automorphism_group().cardinality() 2 """
[f.tuple() for f in self.facets()]])
if c[0] in self.vertices()] for g in group.gens()]
def fixed_complex(self, G): r""" Return the fixed simplicial complex `Fix(G)` for a subgroup `G`.
INPUT:
- ``G`` -- a subgroup of the automorphism group of the simplicial complex or a list of elements of the automorphism group
OUTPUT:
- a simplicial complex `Fix(G)`
Vertices in `Fix(G)` are the orbits of `G` (acting on vertices of ``self``) that form a simplex in ``self``. More generally, simplices in `Fix(G)` correspond to simplices in ``self`` that are union of such orbits.
A basic example::
sage: S4 = simplicial_complexes.Sphere(4) sage: S3 = simplicial_complexes.Sphere(3) sage: fix = S4.fixed_complex([S4.automorphism_group()([(0,1)])]) sage: fix Simplicial complex with vertex set (0, 2, 3, 4, 5) and 5 facets sage: fix.is_isomorphic(S3) True
Another simple example::
sage: T = SimplicialComplex([[1,2,3],[2,3,4]]) sage: G = T.automorphism_group() sage: T.fixed_complex([G([(1,4)])]) Simplicial complex with vertex set (2, 3) and facets {(2, 3)}
A more sophisticated example::
sage: RP2 = simplicial_complexes.ProjectivePlane() sage: CP2 = simplicial_complexes.ComplexProjectivePlane() sage: G = CP2.automorphism_group() sage: H = G.subgroup([G([(2,3),(5,6),(8,9)])]) sage: CP2.fixed_complex(H).is_isomorphic(RP2) True """ else:
if all(sorted([sigma(j) for j in u]) == sorted(list(u)) for sigma in gens)] for f in invariant_f])
def _Hom_(self, other, category=None): """ Return the set of simplicial maps between simplicial complexes ``self`` and ``other``.
EXAMPLES::
sage: S = simplicial_complexes.Sphere(1) sage: T = simplicial_complexes.Sphere(2) sage: H = Hom(S,T) # indirect doctest sage: H Set of Morphisms from Minimal triangulation of the 1-sphere to Minimal triangulation of the 2-sphere in Category of finite simplicial complexes sage: f = {0:0,1:1,2:3} sage: x = H(f) sage: x Simplicial complex morphism: From: Minimal triangulation of the 1-sphere To: Minimal triangulation of the 2-sphere Defn: 0 |--> 0 1 |--> 1 2 |--> 3
sage: S._Hom_(T, Objects()) Traceback (most recent call last): ... TypeError: Category of objects is not a subcategory of SimplicialComplexes() sage: type(Hom(S, T, Objects())) <class 'sage.categories.homset.Homset_with_category_with_equality_by_id'> """
# @cached_method when we switch to immutable SimplicialComplex def _is_numeric(self): """ Test whether all vertices are labeled by integers
OUTPUT:
Boolean. Whether all vertices are labeled by (not necessarily consecutive) integers.
EXAMPLES::
sage: s = SimplicialComplex() sage: s._is_numeric() True sage: s.add_face(['a', 'b', 123]) sage: s._is_numeric() False """ for v in self._vertex_set)
# @cached_method when we switch to immutable SimplicialComplex def _translation_to_numeric(self): """ Return a dictionary enumerating the vertices
See also :meth:`_translation_from_numeric`, which returns the inverse map.
OUTPUT:
A dictionary. The keys are the vertices, and the associated values are integers from 0 to number of vertices - 1.
EXAMPLES::
sage: s = SimplicialComplex() sage: s._translation_to_numeric() {} sage: s.add_face(['a', 'b', 123]) sage: s._translation_to_numeric() # random output {'a': 1, 123: 0, 'b': 2} sage: set(s._translation_to_numeric().keys()) == set(['a', 'b', 123]) True sage: sorted(s._translation_to_numeric().values()) [0, 1, 2] """
# @cached_method when we switch to immutable SimplicialComplex def _translation_from_numeric(self): """ Return a dictionary mapping vertex indices to vertices
See also :meth:`_translation_to_numeric`, which returns the inverse map.
OUTPUT:
A dictionary. The keys are integers from 0 to the number of vertices - 1. The associated values are the vertices.
EXAMPLES::
sage: s = SimplicialComplex() sage: s._translation_from_numeric() {} sage: s.add_face(['a', 'b', 123]) sage: s._translation_from_numeric() # random output {0: 123, 1: 'a', 2: 'b'} sage: sorted(s._translation_from_numeric().keys()) [0, 1, 2] sage: set(s._translation_from_numeric().values()) == set(['a', 'b', 123]) True """
def _chomp_repr_(self): r""" String representation of ``self`` suitable for use by the CHomP program. This lists each facet on its own line, and makes sure vertices are listed as numbers.
EXAMPLES::
sage: S = SimplicialComplex([(0,1,2), (2,3,5)]) sage: print(S._chomp_repr_()) (2, 3, 5) (0, 1, 2)
A simplicial complex whose vertices are tuples, not integers::
sage: S = SimplicialComplex([[(0,1), (1,2), (3,4)]]) sage: S._chomp_repr_() '(0, 1, 2)\n' """ else:
# this function overrides the standard one for GenericCellComplex, # because it lists the maximal faces, not the total number of faces. def _repr_(self): """ Print representation.
If there are only a few vertices or faces, they are listed. If there are lots, the number is given.
EXAMPLES::
sage: X = SimplicialComplex([[0,1], [1,2]]) sage: X._repr_() 'Simplicial complex with vertex set (0, 1, 2) and facets {(1, 2), (0, 1)}' sage: SimplicialComplex([[i for i in range(16)]]) Simplicial complex with 16 vertices and 1 facets """
def set_immutable(self): """ Make this simplicial complex immutable.
EXAMPLES::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S.is_mutable() True sage: S.set_immutable() sage: S.is_mutable() False """
def is_mutable(self): """ Return ``True`` if mutable.
EXAMPLES::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S.is_mutable() True sage: S.set_immutable() sage: S.is_mutable() False sage: S2 = SimplicialComplex([[1,4], [2,4]], is_mutable=False) sage: S2.is_mutable() False sage: S3 = SimplicialComplex([[1,4], [2,4]], is_mutable=False) sage: S3.is_mutable() False """
def is_immutable(self): """ Return ``True`` if immutable.
EXAMPLES::
sage: S = SimplicialComplex([[1,4], [2,4]]) sage: S.is_immutable() False sage: S.set_immutable() sage: S.is_immutable() True """
def cone_vertices(self): r""" Return the list of cone vertices of ``self``.
A vertex is a cone vertex if and only if it appears in every facet.
EXAMPLES::
sage: SimplicialComplex([[1,2,3]]).cone_vertices() [1, 2, 3] sage: SimplicialComplex([[1,2,3], [1,3,4], [1,5,6]]).cone_vertices() [1] sage: SimplicialComplex([[1,2,3], [1,3,4], [2,5,6]]).cone_vertices() [] """
def decone(self): r""" Return the subcomplex of ``self`` induced by the non-cone vertices.
EXAMPLES::
sage: SimplicialComplex([[1,2,3]]).decone() Simplicial complex with vertex set () and facets {()} sage: SimplicialComplex([[1,2,3], [1,3,4], [1,5,6]]).decone() Simplicial complex with vertex set (2, 3, 4, 5, 6) and facets {(3, 4), (2, 3), (5, 6)} sage: X = SimplicialComplex([[1,2,3], [1,3,4], [2,5,6]]) sage: X.decone() == X True """
def is_balanced(self, check_purity=False, certificate=False): r""" Determine whether ``self`` is balanced.
A simplicial complex `X` of dimension `d-1` is balanced if and only if its vertices can be colored with `d` colors such that every face contains at most one vertex of each color. An equivalent condition is that the 1-skeleton of `X` is `d`-colorable. In some contexts, it is also required that `X` be pure (i.e., that all maximal faces of `X` have the same dimension).
INPUT:
- ``check_purity`` -- (default: ``False``) if this is ``True``, require that ``self`` be pure as well as balanced
- ``certificate`` -- (default: ``False``) if this is ``True`` and ``self`` is balanced, then return a `d`-coloring of the 1-skeleton.
EXAMPLES:
A 1-dim simplicial complex is balanced iff it is bipartite::
sage: X = SimplicialComplex([[1,2],[1,4],[3,4],[2,5]]) sage: X.is_balanced() True sage: X.is_balanced(certificate=True) [[2, 4], [1, 3, 5]] sage: X = SimplicialComplex([[1,2],[1,4],[3,4],[2,4]]) sage: X.is_balanced() False
Any barycentric division is balanced::
sage: X = SimplicialComplex([[1,2,3],[1,2,4],[2,3,4]]) sage: X.is_balanced() False sage: X.barycentric_subdivision().is_balanced() True
A non-pure balanced complex::
sage: X=SimplicialComplex([[1,2,3],[3,4]]) sage: X.is_balanced(check_purity=True) False sage: X.is_balanced(certificate=True) [[2], [1, 4], [3]] """ else:
def is_partitionable(self, certificate=False): r""" Determine whether ``self`` is partitionable.
A partitioning of a simplicial complex `X` is a decomposition of its face poset into disjoint Boolean intervals `[R,F]`, where `F` ranges over all facets of `X`.
The method sets up an integer program with:
- a variable `y_i` for each pair `(R,F)`, where `F` is a facet of `X` and `R` is a subface of `F`
- a constraint `y_i+y_j \leq 1` for each pair `(R_i,F_i)`, `(R_j,F_j)` whose Boolean intervals intersect nontrivially (equivalent to `(R_i\subseteq F_j and R_j\subseteq F_i))`
- objective function equal to the sum of all `y_i`
INPUT:
- ``certificate`` -- (default: ``False``) If ``True``, and ``self`` is partitionable, then return a list of pairs `(R,F)` that form a partitioning.
EXAMPLES:
Simplices are trivially partitionable::
sage: X = SimplicialComplex([ [1,2,3,4] ]) sage: X.is_partitionable() True sage: X.is_partitionable(certificate=True) [((), (1, 2, 3, 4), 4)]
Shellable complexes are partitionable::
sage: X = SimplicialComplex([ [1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5] ]) sage: X.is_partitionable() True sage: P = X.is_partitionable(certificate=True) sage: n_intervals_containing = lambda f: len([ RF for RF in P if RF[0].is_face(f) and f.is_face(RF[1]) ]) sage: all( n_intervals_containing(f)==1 for k in X.faces().keys() for f in X.faces()[k] ) True
A non-shellable, non-Cohen-Macaulay, partitionable example, constructed by Björner::
sage: X = SimplicialComplex([ [1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,5,6] ]) sage: X.is_partitionable() True
The bowtie complex is not partitionable::
sage: X = SimplicialComplex([ [1,2,3],[1,4,5] ]) sage: X.is_partitionable() False """ for f in self.facets() for r in Set(f).subsets()] pair1[0].is_face(pair0[1])): else:
def intersection(self,other): r""" Calculate the intersection of two simplicial complexes.
EXAMPLES:
sage: X = SimplicialComplex([[1,2,3],[1,2,4]]) sage: Y = SimplicialComplex([[1,2,3],[1,4,5]]) sage: Z = SimplicialComplex([[1,2,3],[1,4],[2,4]]) sage: X.intersection(Y).facets() {(1, 4), (1, 2, 3)} sage: X.intersection(X) == X True sage: X.intersection(Z) == X False sage: X.intersection(Z) == Z True """
# Miscellaneous utility functions.
# The following two functions can be used to generate the facets for # the corresponding examples in sage.homology.examples. These take a # few seconds to run, so the actual examples have the facets # hard-coded. Thus the following functions are not currently used in # the Sage library.
def facets_for_RP4(): """ Return the list of facets for a minimal triangulation of 4-dimensional real projective space.
We use vertices numbered 1 through 16, define two facets, and define a certain subgroup `G` of the symmetric group `S_{16}`. Then the set of all facets is the `G`-orbit of the two given facets.
See the description in Example 3.12 in Datta [Dat2007]_.
EXAMPLES::
sage: from sage.homology.simplicial_complex import facets_for_RP4 sage: A = facets_for_RP4() # long time (1 or 2 seconds) sage: SimplicialComplex(A) == simplicial_complexes.RealProjectiveSpace(4) # long time True """ # Define the group: from sage.groups.perm_gps.permgroup import PermutationGroup g1 = '(2,7)(4,10)(5,6)(11,12)' g2 = '(1, 2, 3, 4, 5, 10)(6, 8, 9)(11, 12, 13, 14, 15, 16)' G = PermutationGroup([g1, g2]) # Define the two simplices: t1 = (1, 2, 4, 5, 11) t2 = (1, 2, 4, 11, 13) # Apply the group elements to the simplices: facets = [] for g in G: d = g.dict() for t in [t1, t2]: new = tuple([d[j] for j in t]) if new not in facets: facets.append(new) return facets
def facets_for_K3(): """ Returns the facets for a minimal triangulation of the K3 surface.
This is a pure simplicial complex of dimension 4 with 16 vertices and 288 facets. The facets are obtained by constructing a few facets and a permutation group `G`, and then computing the `G`-orbit of those facets.
See Casella and Kühnel in [CK2001]_ and Spreer and Kühnel [SK2011]_; the construction here uses the labeling from Spreer and Kühnel.
EXAMPLES::
sage: from sage.homology.simplicial_complex import facets_for_K3 sage: A = facets_for_K3() # long time (a few seconds) sage: SimplicialComplex(A) == simplicial_complexes.K3Surface() # long time True """ from sage.groups.perm_gps.permgroup import PermutationGroup G = PermutationGroup([[(1,3,8,4,9,16,15,2,14,12,6,7,13,5,10)], [(1,11,16),(2,10,14),(3,12,13),(4,9,15),(5,7,8)]]) return ([tuple([g(i) for i in (1,2,3,8,12)]) for g in G] +[tuple([g(i) for i in (1,2,5,8,14)]) for g in G]) |