Introduction to Computational Topology

COSC 49.09, Fall 2020

Main | Schedule | Homeworks | About

Course Schedule

Curves

9/14

When we could be diving for pearls
Fiona Ross, 9 3/4” x 6”, 2011
Micron ink on Denril paper

logistics; introductions; planar curves, representations, Jordan curve/polygon theorem [lecture video|scribbles]

• Erickson Chap 1
• Lazarus-Mesmay Sec 2.1.1
• Reference to Jordan curve theorem:
  • The Jordan-Schönflies Theorem and the Classification of Surfaces by Thomassen
  • Topology by Munkres, Sec 61 and 63

9/16

winding number, homotopy, invariance; regular homotopy, rotation number, Whitney-Graustein Theorem; Gauss signing, smoothings, Seifert decomposition [lecture video|scribbles]

• Erickson Chap 5
• Cool application of regular homotopy (no time): Mitchell-Thurston hex mesh theorem
• Picture-hanging puzzles by Demaine, Demaine, Minsky, Mitchell, Rivest, and Pătrașcu
• Untangling planar curves (shameless self-promotion)
• Reference to simplicial approximation theorem:
  • Chap 6 of lecture notes by Wilton (polished by Dexter Chua)
  • Elements of Algebraic Topology by Munkres, Sec 14-16

Surfaces

9/21

surfaces, triangulations, polygonal schemata, homeomorphism, classification of surfaces; surface graphs, rotation system, dual graphs, tree-cotree decomposition, Euler's formula [lecture video|scribbles]

• Lazarus-Mesmay Sec 3.1 and 3.2
• Conway's ZIP proof by Franci and Weeks
• Comics and fun videos about surfaces:
  • Topo the World by Jean-Pierre Petit, translated by John Murphy
  • Wind and Mr. Ug by Vi Hart
• Erickson Chap 6
• Reference to triangulation theorem:
  • The Jordan-Schönflies Theorem and the Classification of Surfaces by Thomassen

9/23

tree-cotree decomposition, Euler characteristic, Gauss-Bonnet theorem; mesh generation, Delaunay triangulations, flip algorithm, Bowyer-Watson refinement, Ruppert's algorithm [lecture video|scribbles]

• Erickson Chap 2
• Lazarus-Mesmay Sec 4.3
• Mesh Generation and Geometry Processing in Graphics, Engineering, and Modeling by Jonathan Shewchuk, Chap 2, 3, and 6.3
• Elementary Applied Topology by Robert Ghrist, Chap 3
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 1
• Discrete Differential Geometry: An Applied Introduction by Keenan Crane, Chap 5
• Ruppert's Delaunay Refinement Algorithm by Jonathan Shewchuk
• Surveys and open problems on mesh generation and edge flips:
  • Mesh Generation and Optimal triangulation by Bern and Eppstein
  • Flips in planar graphs by Bose and Hurtado

Homotopy

9/28

Prentententoonstelling (Print Gallery)
M.C. Escher, 1956
Middle hole patched by
Bart de Smit and Hendrik Lenstra

testing homotopy, crossing sequence, shortest homotopic path, funnel algorithm; covering spaces, fundamental groups, induced homomorphisms, Brouwer fixed-point theorem, retractions and homotopy equivalence, universal cover [lecture video|scribbles]

• Erickson Chap 3, Chap 4
• Algebraic Topology by Allen Hatcher, Chap 1
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 1.4, 3.1-3.3
• Lazarus-Mesmay Sec 4.1

9/30

homotopy groups of surfaces, group presentations, uniformization theorem, hyperbolic geometry; minimum (s,t)-cut in planar graphs, minimum homotopic cycle, Reif's algorithm, speedup [lecture video|scribbles]

• Lazarus-Mesmay Sec 3.4
• Erickson scribbles, Oct 17 2017
• Mozes lecture notes, Nov 14 2011
• Minimum s-t Cut of a Planar Undirected Network in O(n log^2(n)) Time, John H. Reif, 1981
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 4.1, 4.2.1
• Resource for hyperbolic geometry:
  • Non-Euclidean Geometry Explained - Hyperbolica Devlog #1 by CodeParade
  • A Primer on Mapping Class Groups by Farb and Margalit, Chap 1

Homology

10/5

Arrival Logograms
from scifi film Arrival (2016)
TheDael

complexes, Čech complex, nerve theorem, Vietoris-Rips complex, alpha shape and alpha complex; chain complex, boundary maps, cycles and boundaries, simplicial homology [lecture video|scribbles]

• Edelsbrunner lecture notes, Sec III and IV.2
• Algebraic Topology by Allen Hatcher, Chap 2
• Dey lecture notes, Sec 6-8
• Introduction to Alpha Shapes by Kaspar Fischer
• Computational Topology: An Introduction by Herbert Edelsbrunner and John L. Harer, Chap 3
• Nanda lecture notes, Lec 1-3
• Elementary Applied Topology by Robert Ghrist, Chap 2

10/7

homology theories and homotopy invariance, winding number/Euler characteristics redux, other fun examples [lecture video|scribbles]

• Lazarus-Mesmay Sec 6
• Algebraic Topology by Allen Hatcher, Chap 2
• Graphs, Surfaces and Homology by Peter Giblin, Chap 4-7
• Edelsbrunner lecture notes, Sec IV.2 and IV.3
• Computational Topology: An Introduction by Herbert Edelsbrunner and John L. Harer, Chap 4
• Nanda lecture notes, Lec 3-4
• Elementary Applied Topology by Robert Ghrist, Chap 4

10/12

An 11-by-11 Hex Board
from The Game of Hex and the
Brouwer Fixed-Point Theorem
David Gale, 1979

Brouwer's fixed point theorem, Sperner's lemma, PPAD complexity; Borsuk-Ulam theorem, ham sandwich theorem, fair partitioning [lecture video|scribbles]

• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg by Jesus A. De Loera, Xavier Goaoc, Frédéric Meunier, Nabil Mustafa, Sec 1, 2, 4, 7.1
• Using the Borsuk–Ulam Theorem by Jiří Matoušek, Chap 2-3
• Algebraic Topology by Allen Hatcher, Chap 2.B
• Elementary Applied Topology by Robert Ghrist, Chap 4 and 5
• Game of Hex
  • Have you play the Hex game before? If not, try it here.
  • The Game of Hex and the Brouwer Fixed-Point Theorem by David Gale

10/14

Persistent homology, barcodes, existence, computation, stability; applications in topological data analysis [lecture video|scribbles]

• Dey lecture notes on persistent homology
• Barcodes: The Persistent Topology of Data by Robert Ghrist
• Persistent Homology — a Survey by Herbert Edelsbrunner and John Harer
• A list of tools to compute persistent homology can be found on the course webpage by Yusu Wang
• Persistence Theory: From Quiver Representations to Data Analysis by Steve Y. Oudot

Cohomology

10/19

Appendix iv: Halcyon Court
from puzzle game Monument Valley (2014)
Ustwo Games

cohomology, flow and circulation, impossible objects, Čech cohomology; universal coefficient theorem, cup product, Borsuk-Ulam redux [lecture video|scribbles]

• Nanda lecture notes, Lec 5
• On the Cohomology of Impossible Figures by Tony Phillips, 2014
• The Topology of Impossible Spaces by Roger Penrose, 1992
• Algebraic Topology by Allen Hatcher, Chap 3.1 and 3.2
• Edelsbrunner lecture notes, Sec IV.4
• Elementary Applied Topology by Robert Ghrist, Chap 6.1 - 6.3, 6.10, 9.6

10/21

Künneth formula, Poincaré duality, Alexander duality, Helly theorem; graph Laplacians, positive semi-definite matrix, algebraic connectivity, graph cuts, electrical flows [lecture video|scribbles]

• Elementary Applied Topology by Robert Ghrist, Chap 6.4 - 6.6, 6.12
• Algebraic Topology by Allen Hatcher, Chap 3.3
• Lx = b: Laplacian Solvers and Their Algorithmic Applications by Nisheeth K. Vishnoi, 2013, Chap 1 - 4
• A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time by Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu, 2013
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems by Daniel A. Spielman and Shang-Hua Teng, 2004

Intermission

10/26

Let's chat and research together: how to find a topic, what does research look like, how to find references, and all that jazz

Advanced topics

Geometry

10/28

derivatives, differential forms, exterior calculus, de Rham cohomology, Stokes theorem; isolation lemma in planar graphs [lecture video|scribbles]

• Discrete Differential Geometry: An Applied Introduction by Keenan Crane, Chap 3, 4, 6, 8
• Elementary Applied Topology by Robert Ghrist, Chap 6.8 - 6.9, 6.12
• Green’s Theorem and Isolation in Planar Graphs by Raghunath Tewari and N. V. Vinodchandran, 2012
• Differential Forms by Victor Guillemin and Peter J. Haine, 2018

Optimization

11/2

multiple-source shortest paths: disk-tree lemma, parametric shortest paths, red-blue lemma; r-division: cycle separators, fundamental-cycle separator, BFS face levels, alternation [lecture video|scribbles]

• Multiple-Source Shortest Paths in Embedded Graphs by Sergio Cabello, Erin W. Chambers, and Jeff Erickson, 2013
• A Simple Algorithm for Computing a Cycle Separator by Sariel Har-Peled and Amir Nayyeri, 2018
• Optimization Algorithms for Planar Graphs by Philip Klein and Shay Mozes, Chap 5 and 7

11/4

dense-distance graphs, FR-Dijkstra, Monge property, Monge heap, fast min-cut in planar graphs [lecture video|scribbles]

• Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs by Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen, 2011
• Erickson lecture notes, Oct 20 2020

Morse theory

11/9

critical points, Morse functions, flow lines, Morse homology and inequalities; Reeb graphs, loop lemma, applications to shape analysis [lecture video|scribbles]

• Elementary Applied Topology by Robert Ghrist, Chap 7
• Morse theory by Shintaro Fushida-Hardy
• Edelsbrunner lecture notes, Sec V
• Graph Reconstruction by Discrete Morse Theory by Tamal K. Dey, Jiayuan Wang, and Yusu Wang, 2018
• Road Network Reconstruction from Satellite Images with Machine Learning Supported by Topological Methods by Tamal K. Dey, Jiayuan Wang, and Yusu Wang, 2019
• No time for today:
  • Loops in Reeb Graphs of 2-Manifolds by Kree Cole-McLaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascuc, 2019
  • Morse Theory for Filtrations and Efficient Computation of Persistent Homology by Konstantin Mischaikow and Vidit Nanda, 2013

11/11

discrete Morse theory: discrete gradient field, simplicial collapse, discrete flow line; evasiveness conjecture, lower bound on #evaders [lecture video|scribbles]

• Elementary Applied Topology by Robert Ghrist, Chap 7.8
• A User's Guide to Discrete Morse Theory by Robin Forman, 2002
• Evasiveness of Graph Properties and Topological Fixed-Point Theorems by Carl A. Miller, 2013
• A topological approach to evasiveness by Jeff Kahn, Michael Saks, and Dean Sturtevant, 1984

11/16

I'll give a 30-min talk in project presentation format, followed by an AMA session. Ask my anything!

Topics we didn't get to cover

3-manifolds: knots, normal surface theory

low-distortion routing: multi-commodity flows, L1 embeddings, planar embedding conjecture

topological graph theory: planar covers and Negami 1-2-infinity conjecture, theory of almost-planar graphs

linkages and foldings: universality, rigidity

combinatorics of curves: pseudolines, self-overlapping curves, electrical moves, Hanani-Tutte, weak embeddings

planar graph algorithms: disjoint paths, multi-terminal flows and cuts, diameter, matchings, distance oracles

differential topology: transversality, genericity, intersection theory

tools on planar graphs: circle-packing, Tutte spring embedding, Maxwell–Cremona correspondence, Schnyder woods