Lefschetz Complex Functions

create_lefschetz_gf2(defcellbnd)

Create a Lefschetz complex over GF(2) by specifying its essential cells and boundaries.

The input argument defcellbnd has to be a vector of vectors. Each entry defcellbnd[k] has to be of one of the following two forms:

• [String, Int, String, String, ...]: The first String contains the label for the cell k, followed by its dimension in the second entry. The remaining entries are for the labels of the cells which make up the boundary.
• [String, Int]: This shorther form is for cells with empty boundary. The first entry denotes the cell label, and the second its dimension.

The cells of the resulting Lefschetz complex correspond to the union of all occurring labels. Cell labels that only occur in the boundary specification are assumed to have empty boundary, and they do not have to be specified separately in the second form above. However, if their boundary is not empty, they have to be listed via the above first form as well.

Examples

julia> defcellbnd = [["A",0], ["a",1,"B","C"], ["b",1,"B","C"]];

julia> push!(defcellbnd, ["c",1,"B","C"]);

julia> push!(defcellbnd, ["alpha",2,"b","c"]);

julia> lc = create_lefschetz_gf2(defcellbnd);

julia> lc.labels
7-element Vector{String}:
 "A"
 "B"
 "C"
 "a"
 "b"
 "c"
 "alpha"

julia> homology(lc)
3-element Vector{Int64}:
 2
 1
 0

lefschetz_subcomplex(lc::LefschetzComplex, subcomp::Vector{Int})

Extract a subcomplex from a Lefschetz complex. The subcomplex has to be locally closed, and is given by the collection of cells in subcomp.

lefschetz_subcomplex(lc::LefschetzComplex, subcomp::Vector{String})

Extract a subcomplex from a Lefschetz complex. The subcomplex has to be locally closed, and is given by the collection of cells in subcomp.

lefschetz_closed_subcomplex(lc::LefschetzComplex, subcomp::Vector{Int})

Extract a closed subcomplex from a Lefschetz complex. The subcomplex is the closure of the collection of cells given in subcomp.

lefschetz_closed_subcomplex(lc::LefschetzComplex, subcomp::Vector{String})

Extract a closed subcomplex from a Lefschetz complex. The subcomplex is the closure of the collection of cells given in subcomp.

lefschetz_reduction(lc::LefschetzComplex, redpairs::Vector{Vector{Int}})

Apply a sequence of elementary reductions to a Lefschetz complex.

The reduction pairs have to be specified in the argument redpairs. Each entry has to be a vector of length two which contains an elementary reduction pair in index form. In particular, the dimensions of the two cells in the pair have to differ by one, and once the pair is reached in the reduction sequence, one cell has to be a face of the other. The function returns a new Lefschetz complex, where all cells in redpairs have been removed.

lefschetz_reduction(lc::LefschetzComplex, redpairs::Vector{Vector{String}})

Apply a sequence of elementary reductions to a Lefschetz complex.

The reduction pairs have to be specified in the argument redpairs. Each entry has to be a vector of length two which contains an elementary reduction pair in label form. In particular, the dimensions of the two cells in the pair have to differ by one, and once the pair is reached in the reduction sequence, one cell has to be a face of the other. The function returns a new Lefschetz complex, where all cells in redpairs have been removed.

lefschetz_reduction(lc::LefschetzComplex, r1::Int, r2::Int)

Apply a single elementary reduction to a Lefschetz complex.

This method expects that the two cells r1 and r2 which form the reduction pair are given in index form. The function returns the reduced Lefschetz complex.

lefschetz_reduction(lc::LefschetzComplex, r1::String, r2::String)

Apply a single elementary reduction to a Lefschetz complex.

This method expects that the two cells r1 and r2 which form the reduction pair are given in label form. The function returns the reduced Lefschetz complex.

lefschetz_reduction_maps(lc::LefschetzComplex, redpairs::Vector{Vector{Int}})

Apply a sequence of elementary reductions to a Lefschetz complex and return the associated chain maps.

The reduction pairs have to be specified in the argument redpairs. Each entry has to be a vector of length two which contains an elementary reduction pair in index form. In particular, the dimensions of the two cells in the pair have to differ by one, and once the pair is reached in the reduction sequence, one cell has to be a face of the other. The function returns a new Lefschetz complex, where all cells in redpairs have been removed, as well as the associated chain maps.

The return values are as follows:

• lcred: The first variable contains the reduced Lefschetz complex.
• pp: This is a sparse matrix representation of the chain equivalence between the original complex and the reduced one.
• jj: This is a sparse matrix representation of the chain equivalence between the reduced complex and the original one.
• hh: This is a sparse matrix representation of the chain homotopy which shows that the composition jj * pp is chain homotopic to the identity.

Examples

julia> labels = ["a","b","c","d"];

julia> simplices = [["a","b"], ["b","c"], ["c","d"]];

julia> sc = create_simplicial_complex(labels, simplices, p=0);

julia> redpairs = [["b", "bc"], ["d", "cd"]];

julia> scr, pp, jj, hh = lefschetz_reduction_maps(sc,redpairs);

julia> bnd = deepcopy(sc.boundary);

julia> bndr = deepcopy(scr.boundary);

julia> ii = sparse_identity(sc.ncells, p=0);

julia> sparse_nz_count(pp*bnd - bndr*pp)
0

julia> sparse_nz_count(jj*bndr - bnd*jj)
0

julia> full_from_sparse(pp*jj)
3×3 Matrix{Rational{Int64}}:
 1  0  0
 0  1  0
 0  0  1

julia> full_from_sparse(jj*pp)
7×7 Matrix{Rational{Int64}}:
 1  0  0  0  0  0  0
 0  0  0  0  0  0  0
 0  1  1  1  0  0  0
 0  0  0  0  0  0  0
 0  0  0  0  1  0  0
 0  0  0  0  1  0  0
 0  0  0  0  0  0  0

julia> sparse_nz_count(ii + bnd*hh + hh*bnd - jj*pp)
0

lefschetz_reduction_maps(lc::LefschetzComplex, redpairs::Vector{Vector{String}})

Apply a sequence of elementary reductions to a Lefschetz complex and return the chain maps.

The reduction pairs have to be specified in the argument redpairs. Each entry has to be a vector of length two which contains an elementary reduction pair in label form. In particular, the dimensions of the two cells in the pair have to differ by one, and once the pair is reached in the reduction sequence, one cell has to be a face of the other. The function returns a new Lefschetz complex, where all cells in redpairs have been removed, as well as the involved chain maps.

lefschetz_reduction_maps(lc::LefschetzComplex, r1::Int, r2::Int)

Apply a single elementary reduction to a Lefschetz complex and return the chain maps.

This method expects that the two cells r1 and r2 which form the reduction pair are given in index form. The function returns the reduced Lefschetz complex, as well as the involved chain maps.

lefschetz_reduction_maps(lc::LefschetzComplex, r1::String, r2::String)

Apply a single elementary reduction to a Lefschetz complex and return the chain maps.

This method expects that the two cells r1 and r2 which form the reduction pair are given in label form. The function returns the reduced Lefschetz complex, as well as the involved chain maps.

lefschetz_newbasis(lc::LefschetzComplex, basis::SparseMatrix; maps::Bool=false)

Create a new Lefschetz complex via change of basis.

The new basis has to be specified in the sparse matrix basis, whose columns represent the new basis in terms of the existing one. This matrix has to respect the grading by dimension, i.e., the cells which are used to form a new basis chain have to have the same dimensions as the cell which is being replaced. The function returns the new Lefschetz complex lcnew. If the optional parameter maps = true is passed, the the function also returns the chain maps pp and jj which are the isomorphisms from lc to lcnew, and vice versa, as well as the zero chain homotopy hh.

lefschetz_newbasis_maps(lc::LefschetzComplex, basis::SparseMatrix)

Create a new Lefschetz complex via change of basis and return the associated chain maps.

The new basis has to be specified in the sparse matrix basis, whose columns represent the new basis in terms of the existing one. This matrix has to respect the grading by dimension, i.e., the cells which are used to form a new basis chain have to have the same dimensions as the cell which is being replaced. The function returns the new Lefschetz complex lcnew, as well as the chain maps pp and jj which are the isomorphisms from lc to lcnew, and vice versa.

compose_reductions(pp1::SparseMatrix, jj1::SparseMatrix, hh1::SparseMatrix, 
                   pp2::SparseMatrix, jj2::SparseMatrix, hh2::SparseMatrix)

Combine the chain maps and chain homotopies of two reductions.

The function expects the chain maps and chain homotopies of two Lefschetz complex reductions, and computes the chain maps and chain homotopy for the composition of both. The maps ppX, jjX, and hhX can be obtained via either lefschetz_reduction_maps or lefschetz_newbasis_maps.

permute_lefschetz_complex(lc::LefschetzComplex,
                          permutation::Vector{Int})

Permute the indices of a Lefschetz complex.

The vector permutation contains a permutation of the indices for the given Lefschetz complex lc. If no permutation is specified, or if the length of the vector is not correct, then a randomly generated one will be used. Note that the permutation has to respect the ordering of the cells by dimension, otherwise an error is raised. In other words, the permutation has to decompose into permutations within each dimension. This is automatically done if no permutation is explicitly specified.

lefschetz_information(lc::LefschetzComplex)

Extract basic information about a Lefschetz complex.

The input argument lc contains the Lefschetz complex. The function returns the information in the form of a Dict{String,Any}. You can use the command keys to see the keyset of the return dictionary:

• "Dimension": Dimension of the Lefschetz complex
• "Coefficient field": Underlying coefficient field
• "Euler characteristic": Euler characteristic of the complex
• "Homology": Betti numbers of the Lefschetz complex
• "Boundary sparsity": Sparsity percentage of the boundary matrix
• "Number of cells": Total number of cells in the complex
• "Cell counts by dim": Cell counts by dimension

In the last case, the dictionary entry is a vector of pairs (dimension, cell count).

lefschetz_cell_count(lc::LefschetzComplex; bounds::Bool=false)

Returns the number of cells in each dimension.

The function returns the number of cells in each dimension. The return variable is of type Vector{Int}, has length lc.dim + 1, and its k-th entry contains the number of cells in dimension k-1. If the optional parameter bounds=true is passed, then the function also returns two integer vectors lo and hi. These contain the beginning and end indices of the cells in each dimension.

fieldstr = lefschetz_field(lc::LefschetzComplex)

Returns the Lefschetz complex coefficient field.

lefschetz_is_closed(lc::LefschetzComplex, subcomp::Vector{Int})

Determine whether a Lefschetz complex subset is closed.

lefschetz_is_closed(lc::LefschetzComplex, subcomp::Vector{String})

Determine whether a Lefschetz complex subset is closed.

lefschetz_is_locally_closed(lc::LefschetzComplex, subcomp::Vector{Int})

Determine whether a Lefschetz complex subset is locally closed.

lefschetz_is_locally_closed(lc::LefschetzComplex, subcomp::Vector{String})

Determine whether a Lefschetz complex subset is locally closed.

validate_lefschetz_complex(lc::LefschetzComplex)

Check whether the boundary matrix of lc satisfies ∂² = 0.

Returns true if the complex is valid. Throws an error if the boundary matrix does not square to zero, indicating an incorrectly assembled complex.

This function is the explicit counterpart to the validate=true keyword argument of the LefschetzComplex constructor. It is useful for checking a complex that was not validated at construction time.

Examples

julia> lc = create_simplicial_complex(["A","B","C"], [["A","B"],["B","C"]]);

julia> validate_lefschetz_complex(lc)
true

lefschetz_boundary(lc::LefschetzComplex, cellI::Int)

Compute the support of the boundary of a Lefschetz complex cell.

This method returns the boundary support as a Vector{Int}.

lefschetz_boundary(lc::LefschetzComplex, cellS::String)

Compute the support of the boundary of a Lefschetz complex cell.

This method returns the boundary support as a Vector{String}.

lefschetz_coboundary(lc::LefschetzComplex, cellI::Int)

Compute the support of the coboundary of a Lefschetz complex cell.

This method returns the boundary support as a Vector{Int}.

lefschetz_coboundary(lc::LefschetzComplex, cellS::String)

Compute the support of the coboundary of a Lefschetz complex cell.

This method returns the boundary support as a Vector{String}.

lefschetz_closure(lc::LefschetzComplex, subcomp::Vector{Int})

Compute the closure of a Lefschetz complex subset.

lefschetz_closure(lc::LefschetzComplex, subcomp::Vector{String})

Compute the closure of a Lefschetz complex subset.

lefschetz_interior(lc::LefschetzComplex, subcomp::Vector{Int})

Compute the interior of a Lefschetz complex subset.

lefschetz_interior(lc::LefschetzComplex, subcomp::Vector{String})

Compute the interior of a Lefschetz complex subset.

lefschetz_topboundary(lc::LefschetzComplex, subcomp::Vector{Int})

Compute the topological boundary of a Lefschetz complex subset.

In contrast to the algebraic boundary defined via the boundary operator, this function computes the boundary of the Lefschetz complex subset specified in subcomp if the Lefschetz complex is interpreted as a finite topological space. In other words, the topological boundary is the set difference of the closure and the interior of the subset.

lefschetz_topboundary(lc::LefschetzComplex, subcomp::Vector{String})

Compute the topological boundary of a Lefschetz complex subset.

In contrast to the algebraic boundary defined via the boundary operator, this function computes the boundary of the Lefschetz complex subset specified in subcomp if the Lefschetz complex is interpreted as a finite topological space. In other words, the topological boundary is the set difference of the closure and the interior of the subset.

lefschetz_openhull(lc::LefschetzComplex, subcomp::Vector{Int})

Compute the open hull of a Lefschetz complex subset.

lefschetz_openhull(lc::LefschetzComplex, subcomp::Vector{String})

Compute the open hull of a Lefschetz complex subset.

lefschetz_lchull(lc::LefschetzComplex, subcomp::Vector{Int})

Compute the locally closed hull of a Lefschetz complex subset.

The locally closed hull is the smallest locally closed set which contains the given cells. It is the intersection of the closure and the open hull.

lefschetz_lchull(lc::LefschetzComplex, subcomp::Vector{String})

Compute the locally closed hull of a Lefschetz complex subset.

The locally closed hull is the smallest locally closed set which contains the given cells. It is the intersection of the closure and the open hull.

lefschetz_clomopair(lc::LefschetzComplex, subcomp::Vector{Int})

Determine the closure-mouth-pair associated with a Lefschetz complex subset.

The function returns the pair (closure,mouth).

lefschetz_clomopair(lc::LefschetzComplex, subcomp::Vector{String})

Determine the closure-mouth-pair associated with a Lefschetz complex subset.

The function returns the pair (closure,mouth).

lefschetz_neighbors(lc::LefschetzComplex, subcomp::Vector{Int})

Find all cells neighboring a Lefschetz complex subset.

The function returns all cells which are not contained in subcomp, but which are either in the closure or the open hull of subcomp. In other words, if one adds a neighbor to the set subcomp, then the number of connected components of the combined set does not increase. It could, however, decrease.

lefschetz_neighbors(lc::LefschetzComplex, subcomp::Vector{String})

Find all cells neighboring a Lefschetz complex subset.

The function returns all cells which are not contained in subcomp, but which are either in the closure or the open hull of subcomp. In other words, if one adds a neighbor to the set subcomp, then the number of connected components of the combined set does not increase. It could, however, decrease.

lefschetz_skeleton(lc::LefschetzComplex, subcomp::Vector{Int}, skdim::Int)

Compute the skdim-dimensional skeleton of a Lefschetz complex subset.

The computed skeleton is for the closure of the subcomplex given by subcomp.

lefschetz_skeleton(lc::LefschetzComplex, subcomp::Vector{String}, skdim::Int)

Compute the skdim-dimensional skeleton of a Lefschetz complex subset.

The computed skeleton is for the closure of the subcomplex given by subcomp.

lefschetz_skeleton(lc::LefschetzComplex, skdim::Int)

Compute the skdim-dimensional skeleton of a Lefschetz complex.

The computed skeleton is for the full Lefschetz complex.

manifold_boundary(lc::LefschetzComplex)

Extract the manifold boundary from a Lefschetz complex.

The function expects a Lefschetz complex which represents a compact d-dimensional manifold with boundary. It returns a list of all cells which lie on the topological boundary of the manifold, in the form of a Vector{Int}.

create_random_filter(lc::LefschetzComplex)

Create a random injective filter on a Lefschetz complex.

The function creates a random injective filter on a Lefschetz complex. The filter is created by assigning integers to cell groups, increasing with dimension. Within each dimension the assignment is random, but all filter values of cells of dimension k are less than all filter values of cells with dimension k+1. The function returns the filter as Vector{Int}, with indices corresponding to the cell indices in the Lefschetz complex.

filter_shallow_pairs(lc::LefschetzComplex, phi)

Find all shallow pairs for a filter.

This function finds all shallow pairs for the filter phi. These are face-coface pairs (x,y) whose dimensions differ by one, and such that y has the smallest filter value on the coboundary of x, and x has the largest filter value on the boundary of y.

If the filter is injective, these pairs give rise to a Forman vector field on the underlying Lefschetz complex. For noninjective filters this is not true in general.

filter_induced_mvf(lc::LefschetzComplex, phi)

Compute the multivector field induced by a filter.

This function returns the smallest multivector field which has the property that every shallow pair is contained in a multivector. For injective filters this is a Forman vector field, but in the noninjective case it can be a general multivector field.

lefschetz_filtration(lc::LefschetzComplex, fvalues::Vector{Int})

Compute a filtration on a Lefschetz subset.

The considered Lefschetz complex is given in lc. The vector fvalues assigns an integer between 0 and N to every cell in lc. For every k the complex L_k is given by the closure of all cells with values between 1 and k. The function returns the following variables:

• lcsub: The subcomplex L_N
• fvalsub: The filtration on the subcomplex with values 1,...,N

Example

julia> labels = ["A","B","C","D","E","F","G"];

julia> simplices = [["A","B","D"],["B","D","E"],["B","C","E"],["C","E","F"],["F","G"]];

julia> sc = create_simplicial_complex(labels,simplices);

julia> filtration = [0,0,0,0,0,0,0,1,1,0,1,2,0,4,2,4,0,5,3,7,6];

julia> lcsub, fvalsub = lefschetz_filtration(sc,filtration);

julia> phinf, phint = persistent_homology(lcsub,fvalsub);

julia> phinf
3-element Vector{Vector{Int64}}:
 [1]
 []
 []

julia> phint
3-element Vector{Vector{Tuple{Int64, Int64}}}:
 []
 [(1, 5), (2, 7), (4, 6)]
 []

lefschetz_filtration(lc::LefschetzComplex, strfilt::Vector{Vector{String}})

Compute a filtration on a Lefschetz subset.

The considered Lefschetz complex is given in lc. The vector of string vectors strfilt contains the necessary simplices to build the filtration. The list strfilt[k] contains the simplices that are added at the k-th step, together with their closures. Thus, for every k the complex L_k is given by the closure of all cells listed in strfilt[i] for i between 1 and k. The function returns the following variables:

• lcsub: The subcomplex L_N, where N = length(strfilt)
• fvalsub: The filtration on the subcomplex with values 1,...,N

Example

julia> labels = ["A","B","C","D","E","F","G"];

julia> simplices = [["A","B","D"],["B","D","E"],["B","C","E"],["C","E","F"],["F","G"]];

julia> sc = create_simplicial_complex(labels,simplices);

julia> strfiltration = [["AB","AD","BD"],["BE","DE"],["BCE"],["CF","EF"],["ABD"],["CEF"],["BDE"]];

julia> lcsub, fvalsub = lefschetz_filtration(sc, strfiltration);

julia> phinf, phint = persistent_homology(lcsub,fvalsub);

julia> phinf
3-element Vector{Vector{Int64}}:
 [1]
 []
 []

julia> phint
3-element Vector{Vector{Tuple{Int64, Int64}}}:
 []
 [(1, 5), (2, 7), (4, 6)]
 []

lefschetz_filtration_mvf(lc::LefschetzComplex, fvalues::Vector{Int})

Compute the multivector field associated with a Lefschetz complex filtration.

For the Lefschetz complex lc, and the filtration fvalues given on the Lefschetz complex, this function determines the multivector field generated by the filtration in the following way. For every filtration value k, the cells which are assigned this value form a locally closed set, which can be decomposed into connected components that are all locally closed. The union of all these connected components, as k ranges from 1 to N, forms the multivector field mvf that is returned by the function. The filtration should be generated by the function lefschetz_filtration.

lcgfp = lefschetz_gfp_conversion(lc::LefschetzComplex, p::Int)

Convert a Lefschetz complex to the same complex over a finite field.

It is expected that the boundary matrix of the given Lefschetz complex lc is defined over the rationals, and that the target characteristic p is a prime.