Computational Topology - Lecture Notes and Videos

Math 574 (Spring 2016)  - 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 12 syllabus, topology and connectivity, applications - drug design, geography scribe video
2 Jan 14 topological space \(\mathbb{X} = (X,T)\), interior \(\mathring{A}\), closure \(\bar{A}\), and boundary \(\partial A\) of \(A \in \mathbb{X}\), continuous funtion, homeomorphism, examples scribe video
3 Jan 19 \(\mathbb{S}^1 \not\approx\) annulus, \(\mathbb{S}^2 \approx \mathbb{R}^2 \cup \{\infty\}\), 2-manifold, orientation-reversing closed curve, nonorientable manifold, 0- and 1-manifold classifications scribe video
4 Jan 21 open cover, compact spaces, chart, Hausdorff, \(d\)-manifold, projective plane, Klein bottle, classification of \(2\)-manifolds, connected sum scribe video
5 Jan 26 combinations, linear (affine) independence, \(k\)-simplex, (co)face, simplcial complex \(K\), underlying space, abstract simplicial complex (ASC) scribe video
6 Jan 28 general position, isomorphic ASCs, examples of ASCs - cylinder, Möbius strip, torus, Klein bottle, rule to check triangulations of 2-manifolds scribe video
7 Feb  2 Euler characteristic \(\chi\), \(\chi(\mathbb{T}^2)=\chi(\mathbb{K}^2)=0\), \(\chi +\)orientation is complete invariant, genus, cross cap, \(\chi(g\mathbb{T}^2)=2-2g\), orientation of simplex scribe video
8 Feb  4 Homework 2 disucssion, induced orientation, consistently oriented simplices, (non-)orientable manifold, propagating orientation scribe video
9 Feb  9 subdivision, barycentric subdivision, subcomplex, star, closed star, link of (St, \(\rm{Cl}\,\rm{St}\), Lk) \(v \in K^0, \sigma \in K\), and \(X \subseteq K\), partial order, poset scribe video
10 Feb 11 simplicial complex as poset, \(\rm{St}(X)=X\) and everything above, homotopy, deformation retract, homotopy equivalence, contractible, nerve scribe video
11 Feb 16 Nerve theorem, Čech complex, \(r_i \leq r_j \Rightarrow \rm{Čech}(r_i) \subseteq \rm{Čech}(r_j)\), miniball, Vietoris-Rips (VR) complex, VR lemma: \(\rm{VR}(r) \subseteq \rm{Čech}(\sqrt{2}r)\) scribe video
12 Feb 18 Voronoi diagram, Delaunay trinagulation (DT), DT in Octave, general position, filtration, filtration ordering, signature, alpha complex scribe video
13 Feb 23 \(\rm{Alpha}(r) \subseteq \rm{Del}, \rm{Čech}(r)\), weighted/power distance, weighted alpha complex, empty circumsphere property of \(\rm{Del}\), weak and strong witness scribe video
14 Feb 25 witness complex, \(W_{\infty}(L,S) \subseteq \rm{Del}_L\), lazy witness complex, maxmin selection, review of groups, identity, inverse, subgroups scribe video
15 Mar  1 cosets, homomorphism, (epi/mono/iso)morphism, chains, group of \(p\)-chains \(C_p(K,\mathbf{Z}_2)\) or \(C_p(K,\mathbf{Z})\), elementary chains, \(p\)-chain as a vector scribe video
16 Mar  3 boundary of a \(p\)-simplex, \(\partial \mathbf{c} = \sum_i a_i \partial \sigma_i\), cycle and boundary groups \(Z_p(K),B_p(K)\), half of all \(0\)-cycles are \(0\)-boundaries, \(\partial_p \partial_{p+1} = 0\) scribe video
17 Mar  8 relations of \(C_p, Z_p, B_p\) over all \(p\), homology group \(H_p = Z_p / B_p\), examples, order\((C_p)\) and rank\((C_p)\) over \(\mathbf{Z}_2\), betti numbers \(\beta_p\) scribe video
18 Mar 10 betti number examples: torus, \(p\)-ball, Euler-Poincaré theorem: \(\chi = \sum_p (-1)^p \beta_p\), boundary matrix, boundary as a matrix-vector product scribe video
19 Mar 22 matrix representations of elementary operations, Smith normal form (SNF), computing \(z_p,b_p,\beta_p\) by reduction to SNF of \([\partial_p]\) for all \(p\) scribe video
20 Mar 24 reduction algorithm for SNF, reduced homology groups, \(\tilde{\beta}_0 = \beta_0 - 1\), relative homology, tracking \(\beta_1^{\ell}\) over a filtration \(\{K^{\ell}\}_0^m\) of gramicidin scribe video
21 Mar 29 persistence, lifetime of \(\sigma\), positive/negative simplex, incremental algo for \(\beta_j\) in \(\mathbf{S}^3\), example, checking cycle membership (union-find) scribe video
22 Mar 31 union-find example, persistence algo, canonical cycle, details of pairing \((\sigma^i_+,\sigma^j_-)\), youngest \(+\)-simplex in \(\Gamma\), index-persistence diagram scribe video
23 Apr   5 \(\beta_k^{\ell,p}=\) # \(k\)-triangles containing \((\ell,p)\), details of pairing, set \(T[i]:=j\) for pair \((\sigma^i,\sigma^j)\), finding youngest positive \(\sigma\) in \(\Gamma\), collision, illustration scribe video
24 Apr   7 homology over \(\mathbf{Z}\), optimal homologous chain problem (OHCP), \(H_1(K,\mathbf{Z})\) for \(K=\)Möbius, \(\mathbf{R}P^2, \mathbf{K}^2\), torsion subgroup, torsion coefficients scribe video
25 Apr 12 \(\mathbf{K}^2\) over \(\mathbf{Z}:\beta_1 = 1, t_1 =2\), OHCP as an integer program (IP), optimization intro, rounding may not work for IP, total unimodularity (TU) scribe video
26 Apr 14 \(A\) of OHCP LP is TU iff \(B=[\partial]\) is, \(B\) is TU when \(K\) is orientable manifold, Möbius cycle matrix, visualizing torsion, \(k\)-fold dunce hat scribe video
27 Apr 19 option for project (data), cases of TU \([\partial]\), orientable manifolds, \([\partial_d]\) for \(K \in \mathbb{R}^d\), NTU neutralized complexes, currents, flat norm scribe video
28 Apr 21 simplicial flat norm (SFN), as an LP, minimal surface problem on \(\mathbb{K}^2\), optimal bounding chain problem (OBCP) \(\equiv\) OHCP, SFN as \(\lambda \rightarrow 0\) scribe video
29 Apr 26 Reeb graph \(R(f)\) for \((\mathbb{X},f)\), Reeb graph for Morse functions, cover of \(\mathbb{X}\) using \(f^{-1}(U_{\alpha})\) for cover \(\{U_{\alpha}\}\) of \(Z\), for \(f:\mathbb{X} \rightarrow Z\), examples scribe video
30 Apr 28 implementation of mapper, interval length and overlap, clustering data points in each \(f^{-1}(U_{\alpha})\), simplicial complex representation scribe video

Last modified: Sat Jul 29 11:35:18 PDT 2017