MATH 496/696 (Spring 2016)
Instructor's contact information
Michael Robinson
226 Gray Hall
michaelr at american {dot} edu
Office hours: Mondays 11am-noon, 1-2pm, 5-6pm, Wednesdays and Thursdays 10am-noon, or by appointment (please contact me 24 hours in advance to make arrangements). Also, I'm usually around most days 10am-2pm. If the door is open, consider yourself invited!
My research website http://www.drmichaelrobinson.net/
Feel free to contact me with any questions (course-related or not)
Quick Links
Course description
Homework assignments and projects
Course schedule
Concerning programming in this course
Information about exams
Course policies
This course introduces the elements of homology theory for topological spaces, with a focus on computation and applications. The course covers attachment constructions (simplicial and CW complexes), chain complexes, homology (cellular and singular), and exact sequences. Students learn to construct and to compute with chain complexes of vector spaces as a general tool for understanding topological spaces. The course also highlights some of the recent trends in computational topology through computer programming projects.
Prerequisites: Linear algebra (MATH 310), Calculus of several variables (MATH 313)
There is no required course textbook, however there are several suggested texts:
- Elementary Applied Topology, by Robert Ghrist. Awesome. Many pictures! You can get it electronically (free) or in paperback from Amazon (cheap).
- Algebraic Topology, by Allen Hatcher. We'll be looking at material in Chapters 0, 2, and the Appendix. This book is the standard book in algebraic topology, but not focused on the computational aspects of the theory, but is a very good read. This book is also online (free!)
- Computational homology, by Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek. This book focuses heavily on cubical complexes, which is one way to control memory usage.
- Computational Topology: An introduction by Herbert Edelsbrunner and John Harer. This book describes the "main line" approach to computational topology -- a good reference if you want to study the field further, but is a little advanced.
- Topological Signal Processing, by Michael Robinson. We'll be working on material from Chapters 1, 2, 4, 5, though this book focuses on cohomology rather than homology. You can get a student discount on this book, so ask me before purchasing it!
- Finally, have a look at Jeff Erickson's massive reading list!
In this course, students will learn to
- model cellular spaces in software,
- compute homological invariants of these spaces,
- describe their interpretation,
- examine how robust they are when the spaces change, and
- discuss recent techniques in their computation.
There are two kinds of assignments to be completed in this course: homeworks (to be done by hand) and projects (to be done by writing software). Details of both kinds of assignments will be posted on BlackBoard.
The homework assignments are due according to the following schedule:
Homework 1 due January 25: Chain complexes, quotients, basic homology
Homework 2 due February 8: Chain maps, induced maps, chain homotopies
Homework 3 due February 29: Cell complexes, Vietoris Rips complexes, geometric realizations
Homework 4 due March 17: Computing homology of simplicial complexes
Homework 5 due April 11: Computing persistence by hand
The programming projects will consist of some preliminary and background theory questions along with a set of guided programming exercises. The projects are cumulative, in that you will be building a computational topology library. Instructions and submission of all assignments will be electronic via the course BlackBoard page! Check there often for updates.
Get started on Project 1 early!
Project 1 due February 22: Chain complexes and homology
Project 2 due April 4: Simplicial homology
Project 3 due April 25: Persistent homology
I've produced quite a bit of video content that's relevant for this course, and I'll probably record other videos, too. Much of this was produced for the DARPA Sheaf Tutorial, which I created August 2015. The following lectures are most relevant (they're also listed in the course schedule below...):
This will take you far afield of what's covered in this course, but will also give you a feeling for the extent of its applications outside mathematics. If you're interested, that's great! Please let me know, and I can set you up with a research project.
Giving cogent technical talks is an important skill for all scholars. The sooner and more often you present and defend technical ideas in front of an audience, the better. As part of your training, the final exam in this course consists of presenting a recent research paper from the applied topology community. Dr. Robinson will help you select the paper to read and will coach your presentation. The final presentations will be recorded and (with your permission) will be made available to the scientific community to help other young researchers learn this material!
To get you started, here are several good topics:
- Algorithms for computing zig-zag homology,
- Persistent cohomology
- Discrete Morse theory, and reductions inspired by it
- Extensions to Gabriel's theorem
- Non-mathematical applications of computational topology
Here are the parameters for your presentation:
- I will grade your presentation against three criteria:
- Technical accuracy
- Organization
- How well you link the paper you're presenting to what we've learned
- You must work with me to select a topic and a date: either the last day of class (April 25) or the final exam day (April 27). Please make your selection by the end of February.
- You may present the material using slides, or the whiteboard, or both. It's your choice. (A word of advice: proofs are important, but enlightening examples and computations are much more important! Spend time gathering or creating examples. Fully understand them in advance.)
- Since the class is highly interactive -- even energetic -- you'll have to be ready defend whatever you present. I'll help you if you get stuck -- so you should not feel apprehensive -- but expect to get questions from the audience.
- You should limit your presentation to 15 minutes, and plan for about 5 minutes of additional questions afterwards. I will enforce this time limit strictly!
- At your option, I can record the presentation and post it to YouTube. This is great publicity for you if you want it!
- Please show up for others' presentations as well
Unit 1: Chain complexes
After this unit, you should be able to
- Verify that a sequence of linear maps is (or is not) a chain complex, and describe the category of chain complexes,
- Describe exactness and how homology measures the failure of exactness, and
- Perform computations involving homology.
January 11: Chain complexes and linear algebra
January 13: Homology and exactness
January 20: Linear algebra in Python
Homework 1 due January 25: Chain complexes, quotients, basic homology
January 25: (No office hours) Chain maps, induced maps
January 27: (Robinson possibly out) Chain homotopies
February 1: (Robinson out, watch sheaf tutorial lecture 1: (https://www.youtube.com/watch?v=b1Wu8kTngoE) and lecture 5: (https://www.youtube.com/watch?v=TUJQ1MpmDFE, skip ahead to around 30 minutes))
February 3: Functors and categories
Unit 2: Homology
After this unit, you should be able to
- Explain the meaning of a homology space relative to its computation from a chain complex
- Explain how cellular maps induce linear maps on the homology spaces and implement them in software
Some time during this unit (preferably earlier rather than later), watch the sheaf tutorial lecture 2 (https://www.youtube.com/watch?v=G3rWz2LgzZY) and lecture 6 (https://www.youtube.com/watch?v=l60OMKWSeoI).
Homework 2 due February 8: Chain maps, induced maps, chain homotopies
February 8: Simplicial complexes, Vietoris-Rips complexes
February 10: CW complexes, geometric realizations
February 15: Simplicial homology
February 17: Interpretation of simplicial homology
Project 1 due February 22: Chain complexes and homology
February 22: Simplicial maps
February 24: Simplicial homotopies
Homework 3 due February 29: Cell complexes, Vietoris Rips complexes, geometric realizations
By this point in the course, you should discuss plans for your final presentation with Dr. Robinson.
February 29: Relative homology and the snake lemma
March 2: Midterm exam
March 7: (Spring break)
March 9: (Spring break)
March 14: Equivalence of singular and simplicial homology
Unit 3: Persistence
After this unit, you should be able to
- Construct the persistence module from a filtration of cell complexes
- Compute persistence and barcode diagrams from a persistence module
- Interpret the meaning of barcode and persistence diagrams
Homework 4 due March 16: Computing homology of simplicial complexes
March 16: Filtered spaces and persistence diagrams
March 21: (Robinson out, watch lecture 8 (https://www.youtube.com/watch?v=TZpA8E5U4CE))
March 23: (Robinson out)
March 28: Computing persistent homology
March 30: Jordan canonical forms
Project 2 due April 4: Simplicial homology
April 4: Practical computation of persistent homology
April 6: Persistence modules and Gabriel's theorem
Homework 5 due April 11: Computing persistence by hand
April 11: Zig-zag persistence
April 13: Elementary collapses
April 18: Relative homology
April 20: Local homology
Project 3 due April 25: Persistent homology
April 25: Final presentations
April 27: Final exam (more presentations): 5:30pm-8:00pm
Knowledge of the general techniques of programming
is expected, but I don't expect you to know the specifics of any
particular language at the beginning of the course. There will be
extensive programming required on the projects -- so you will be expected
to know some basic programming when the course finishes.
This course will focus on developing a Python-based computational topology library. Therefore, you will be expected to learn Python as the course progresses. Work on the projects well in advance of the due dates to give yourself ample time to learn!
Absences
You are generally expected to attend the lectures, though they will be recorded and made available online. Please contact me in advance if you will be unable to attend.
Grading
The course grade will be determined as follows:
10% Programming project 1
10% Programming project 2
10% Programming project 3
30% Homework assignments
20% Midterm exam
20% Final presentation
Late homeworks and projects will not be accepted, unless there is an official (University-approved) reason for doing so.
Academic dishonesty
Academic dishonesty is a serious offense. Read our University
policies.
You may work together on homeworks and projects, but the work you turn in must be your own.
There is to be no collaboration with other people using any means during an exam. Doing so risks starting academic dishonesty proceedings. However, you may ask me questions during an exam, which I may answer at my discretion.
You may collaborate with other students in this class on homeworks, but the
work you turn in must be your own. You may not collaborate with others outside of the class on homeworks without my express permission.
At a minimum, honesty consists of presenting your ideas clearly and in your own words, possibly orally. On the other hand, the creation and writing of software, proofs, examples, or counterexamples is a creative process. Here are a few typical cases that are relevant for homework:
- If you happen to create an example, counterexample, or proof for your work on your own, you need not notate it as such. (It is expected that you will rediscover standard examples, and these will not cause any concern.)
- If a colleague shows you an example, counterexample, or proof that you like, please credit that person by name in your write-up. You should expect that I may challenge you to explain your writing in your own words, possibly orally.
- If you write an example, counterexample, or proof as part of a group, please credit all members of your group by name in your write-up. You should expect that I may challenge you to explain your writing in your own words, possibly orally.
The mathematics community has a unique perspective on academic honesty and priority. The mathematics community has strict social guidelines for assigning credit, which I expect you'll adhere to. Due to the canonicity of certain mathematical results and constructions, sometimes well-intentioned people end up in priority disputes when they independently discover something. If you have any questions on this matter, you are expected to consult me directly for advice.