Lecture 5: Simplicial maps and filtrations#

  • To save time, all the exercises are solved already. So please read the code and the comments, run it, and play with the examples.

  • As in the previous notebooks, plotting and example data are in a separate python file: lecture5_helpers.py.

⚠️ Vertices IDs. To avoid confusing vertex ids with filtration values, we name vertices with letters, as in the lecture ⚠️. You should be mindful about this:

  • We will use SimplexTree which needs integers for its vertices, so we convert with two helpers: letter2int('A') is 0 ('B' is 1, …) and int2letter(0) is 'A'.

  • You have to be careful, as to insert a simplex you have to write: insert([letter2int('A'), letter2int('C'), letter2int('E')]), not insert(['A', 'C', 'E']). The same goes for assign_filtration, find and the other methods.

  • Similarly, you get back from a SimplexTree (e.g. from get_simplices()) has integer vertices: use int2letter to turn them back into letters.

import matplotlib.pyplot as plt
import gudhi

from lecture5_helpers import (
    letter2int, int2letter,           # 'A' -> 0 and 0 -> 'A': SimplexTree vertices are integers
    plot_map, plot_filtration,        # pictures of a vertex map and of a filtration
    K, K_COORDS, L, L_COORDS,         # slide 16: K sits inside L
    GRAPH_COORDS,                     # slides 5-9
)
plt.rcParams["figure.dpi"] = 110

1. Simplicial maps#

  • A vertex map \(f: V(K) \to V(L)\) is simplicial if every simplex of \(K\) goes to a simplex of \(L\).

  • In Python, we can represent such a map with a Dict, where the keys are the vertices of \(K\) and their values are their images \(f(K)\) (vertices in \(L\)).

  • We could also use a Python function, or other objects, to represent the map, but the Dict approach is simple and enough to get the job done for finite simplicial complexes (or complexes without “too many” simplices).

# Below is a function that checks whether a given map f: K -> L is simplicial.
# It uses SimplexTree from GUDHI to represent the simplicial complexes K and L.
# Read through the code to familiarize yourself with the definitions from the lecture and with the GUDHI library. 
def is_simplicial_map(K: gudhi.SimplexTree, L: gudhi.SimplexTree, f: dict[str, str]) -> bool:
    # we check the images of all simplices in K, and see if they are simplices in L
    for simplex, _ in K.get_simplices():
        # the image of the simplex: the images of its vertices, without repeats
        # the set data structure is useful here, because it automatically removes duplicates
        image = set() # image of the current simplex under f
        for v in simplex: # for each vertex in the current simplex (an int: SimplexTree stores integers)
                image_letter = f[int2letter(v)] # f works with letters
                image.add(letter2int(image_letter)) # back to an int, to look it up in L
        # check if the image of the simplex is a simplex in L
        if not L.find(list(image)):
            return False
    return True

We now visualize some maps using the helper plot_map that colours each vertex of \(K\) like its image in \(L\), and shadows in red the whole image of \(K\) in \(L\).

# Here is a collection of some maps for you to visualize and check whether they are valid simplicial maps.
maps = {
    "inclusion": {"A": "A", "B": "B", "C": "C", "D": "D", "E": "E"},
    "B goes to E": {"A": "A", "B": "E", "C": "C", "D": "D", "E": "E"},
    "swap A and B": {"A": "B", "B": "A", "C": "C", "D": "D", "E": "E"},
    # a constant map is always a simplicial map, whatever K, L and the vertex you pick.
    # you can try to write the proof on paper: it is short!
    "everything to F": {"A": "F", "B": "F", "C": "F", "D": "F", "E": "F"},
    # Your turn: add your own map following the pattern above (vertex in K: image in L).
}
for name in maps:
    f = maps[name]
    plot_map(K, K_COORDS, L, L_COORDS, f, title=f"{name}: simplicial? {is_simplicial_map(K, L, f)}")

2. Filtrations#

In the first notebook of the course we explained that every simplex in a SimplexTree carries a number that we have been ignoring: its filtration value, the second entry of each pair in st.get_simplices(). Now we use it.

Today we have finally learned that a filtration is a nested sequence of subcomplexes \(\emptyset = K_0 \subseteq K_1 \subseteq \dots \subseteq K_n = K\).

A function \(f:K\rightarrow\mathbb{R}\) induces a filtration, \(K_i = \{\sigma : f(\sigma) \le a_i\}\), if if it is monotone: \(f(\tau) \le f(\sigma)\) whenever \(\tau\) is a face of \(\sigma\).

We will use plot_filtration to visualize filtrations: It draws each \(K_i\) using grey to represent vertices are not in \(K_i\) yet. Here is the example from slide 6:

example_2 = gudhi.SimplexTree()
for v in ["A", "C", "D", "F", "G"]:
    example_2.insert([letter2int(v)], filtration=1)    # insert(simplex, filtration=value)
example_2.insert([letter2int("A"), letter2int("C")], filtration=2)
example_2.insert([letter2int("D"), letter2int("F")], filtration=3)
example_2.insert([letter2int("A"), letter2int("F")], filtration=4)
example_2.insert([letter2int("B")], filtration=5)
# vertex E which we did not explicitly add yet gets filtration=5 too
# Remember that in SimplexTree, insert adds missing faces with the same value
example_2.insert([letter2int("E"), letter2int("G")], filtration=5)     
example_2.insert([letter2int("A"), letter2int("D")], filtration=6)
plot_filtration(example_2, GRAPH_COORDS)

Is it monotone?#

Your turn: write the function is_monotone that checks that no face has a bigger value than its simplex.

TIP that for each simplex you can just compare its value to that of its faces with one vertex less, obtained with st.get_boundaries(simplex). Checking only this condition is enough, can you think of why?

def is_monotone(st: gudhi.SimplexTree) -> bool:
    raise NotImplementedError("Your turn: implement this function to check whether the filtration is monotone.")

print("example_2 is monotone:", is_monotone(example_2))

Solution hidden in this cell.#

Breaking it: We can use SimplexTree.assign_filtration(simplex, value) to change the value of a simplex that we already have in our complex.

  • assign_filtration checks nothing, so it can result in an invalid filtration (for example having an edge with lower value that some of its vertices).

  • We change two values of a copy of example_2, so it is no longer a filtration and visualize it. In red red you can see simplices that are in \(K_i\) while one of their faces is not yet.

broken = gudhi.SimplexTree(example_2)    # a copy, so that example_2 doesn't change
broken.assign_filtration([letter2int("A")], 7)                    # the vertex A now comes after its edges AC, AF and AD
broken.assign_filtration([letter2int("E"), letter2int("G")], 2)   # the edge EG now comes before its vertex E (value 5)
print("broken is monotone:", is_monotone(broken))
plot_filtration(broken, GRAPH_COORDS)

Values on the vertices, extended with max#

If we have a function that gives each vertex a real value, we can always induce a valid filtration by assigning each simplex the biggest value of all its vertices.

def extend_with_max(st: gudhi.SimplexTree, vertex_values: dict[str, float]) -> None:
    for simplex, value in st.get_simplices():
        values = [vertex_values[int2letter(v)] for v in simplex]    # the values of its vertices (vertex_values uses letters)
        st.assign_filtration(simplex, max(values))      # assign_filtration replaces the old value


# Your turn: any values work. These are the heights of the vertices, so L grows from the bottom up.
my_values = {"A": 0.32, "B": 0.71, "C": 0.21, "D": 0.0, "E": 0.65, "F": 0.49, "G": 0.06}
my_L = gudhi.SimplexTree(L)                 # a copy, so that L doesn't change
extend_with_max(my_L, my_values)
print("monotone:", is_monotone(my_L))
plot_filtration(my_L, L_COORDS)