Computational Topology - Lecture Notes and Videos

Math 574 (Spring 2018)  - Lecture Notes and Videos on Computational Topology

Scribes from all lectures so far (as a single big file)

Lec # Date Topic(s) Scribe Panopto
1 Jan  9 syllabus, topology and connectivity, examples of optimiztion in topology: tunnels in drug design, terrain smoothing in geography scribe video
2 Jan 11 no class
3 Jan 16 definition of topology, interior, closure, and boundary of sets, homeomorphism, circle $$\not\approx$$ annulus, $$\mathbb{S}^2 \approx \mathbb{R}^2 \cup \{\infty\}$$ scribe video
4 Jan 18 2-manifold (with boundary), (non-)orientable manifolds, 0-, 1-manifolds, compact, Hausdorff, $$d$$-manifold, torus, projective plane scribe video
5 Jan 23 connected sum, $$\mathbb{R}P^2 \# \mathbb{R}P^2 \approx \mathbb{K}^2$$, simplex, (co)face, simplicial complex, underlying space, abstract simplicial complex (ASC) scribe video
6 Jan 25 geometric realization theorem, triangulation, ASCs for surfaces, topological invariant, Euler characteristic $$\chi$$, $$\chi(\mathbb{T}^2)=\chi(\mathbb{K}^2)=0$$ scribe video
7 Jan 30 genus, cross cap, $$\chi(g\mathbb{T}^2)=2-2g,~ \chi(g\,\mathbb{R}P^2)=2-g$$, orientation of simplex, comparing orientation, orientable manifold scribe video
8 Feb   1 checking orientability, propagating orientation, subdivision, star St$$\,v$$ and link Lk$$\,v$$ of vertex $$v$$, St$$\,\sigma$$ of $$\sigma \in K$$, St $$X$$ of $$X \subset K$$ scribe video
9 Feb   6 example of St $$X$$, partial order, poset, principal simplices, homotopy, retract, deformation retract, homotopy equivalent, contractible scribe video
10 Feb   8 nerve theorem, Čech complex, $$r_i \leq r_j \Rightarrow {\rm Čech}(r_i) \subseteq {\rm Čech}(r_j)$$, Vietoris-Rips (VR) complex, VR lemma: $${\rm VR}(r) \subseteq {\rm Čech}(\sqrt{2}r)$$ scribe video
11 Feb 13 Voronoi diagram, Delaunay complex, general position, filtration, filtered complex, alpha complexes, $$\rm{Alpha}(r) \subseteq \rm{Del}, \rm{Čech}(r)$$, scribe video
12 Feb 15 power distance, power Voronoi/Delaunay complex, weighted alpha complex, empty circumsphere property, weak/strong witness scribe video
13 Feb 20 witness complex, $$W_{\infty}(L,S) \subseteq \mbox{Del}_L$$, laxy witness complex, random/maxmin selection of landmarks, groups and homomorphisms scribe video
14 Feb 22 $$p$$-chain, group of $$p$$-chains $$C_p$$, elementary chain, boundary, $$p$$-th boundary map $$\partial_p: C_p \to C_{p-1}$$, chain complex, $$p$$-cycle scribe video
15 Feb 27 $$p$$-boundary, half of 0-cycles are 0-boundaries, $$\partial \partial \mathbf{d} = 0$$, $$p$$-homology group $$H_p = Z_p/B_p$$, ord$$(C_p)$$, rank$$H_p = \beta_p$$: $$p$$-betti number scribe video
16 Mar  1 make-up lecture: examples of homology groups: torus, $$p$$-ball, Euler-Poincaré theorem: $$\chi = \sum_p (-1)^p \beta_p$$, boundary matrix $$\begin{bmatrix} \partial_p \end{bmatrix}$$ scribe video
17 Mar  6 EROs and ECOs, Smith normal form, SNF$$(\begin{bmatrix} \partial_p \end{bmatrix}) = U_{p-1} \begin{bmatrix} \partial_p \end{bmatrix} V_p$$, SNF$$(\begin{bmatrix} \partial_p \end{bmatrix})$$ gives $$z_p, b_{p-1}$$ and bases for $$Z_p, B_{p-1}$$, example scribe video
18 Mar  8 bases for $$Z_1, B_1, H_1$$ in example, SNF algorithm over $$\mathbb{Z}_2$$, reduced homology, augmentation map, $$\tilde{\beta}_0 = \beta_0-1$$, relative homology scribe video
19 Mar 20 $$p$$-persistent $$k$$-homology group of $$K^{\ell}$$, persistence of $$[\mathbb{z}]$$, creator and destroyer simplices, incremental algorithm for $$\beta_k$$'s in $$\mathbb{S}^3$$ scribe video
20 Mar 22 UNION-FIND data structure, persistence algorithm, canonical cycle, youngest positive simplex, example, details of pairing scribe video
21 Mar 27 index-persistence diagram, $$\beta_k^{\ell,p}$$ by counting triangles, implementation of pairing, $$T[i]=j$$ for pair $$(\sigma^i, \sigma^j)$$, collision, illustration scribe video
22 Mar 29 lecture canceled
23 Apr   3 more details of persistence, persistence diagram, fundamental lemma of persistent homology, matrix reduction, example scribe video
24 Apr   5 lowest ones independent of reduction, pairing lemma, persistence diagram, mapper algorithm, pullback and refined pullback scribe video
25 Apr 10 reeb graph, map of coverings, choices for covers in mapper, homology over $$\mathbb{Z}$$, optimal homologous cycle problem (OHCP) scribe video
26 Apr 12 cover intervals in mapper, homology over $$\mathbb{Z}$$: Möbius strip, projective plane, klein bottle, OHCP as an integer program (IP) scribe video
27 Apr 17 about Hw6, project, total unimodularity (TU), OHCP LP and TU, $$\begin{bmatrix} \partial_{p+1}(K) \end{bmatrix}$$ is TU for orientable $$(p+1)$$-manifold, MCM scribe video
28 Apr 19 $$[\partial_2(K)]$$ TU iff $$K$$ has no Möbius strip, $$[\partial(K)]$$ TU iff $$K$$ has no relative torsion, NTU Neutralized complex, currents, flat norm scribe video
29 Apr 24 multiscale simplicial flat norm (MSFN), MSFN LP and TU, integral decomposition of currents, counterexample on Klein bottle scribe video
30 Apr 26 optimal bounding chain problem (OBCP), OBCP and related OHCP, simplicial median shapes, integer solutions for non-TU cases scribe video