Math 412

General information

Fall 2010

David Perkinson

L316, ext. 7417

Office hours

Course Description

This is a course on the abelian sandpile model. Besides the basic theory, it will cover some of the following topics:

• matrix tree theorem
• tilings
• algebraic geometry of the Laplacian lattice ideal
• graph-theoretic Riemann-Roch
• complexity (constructing a Turing machine from sandpiles)
• sandpile algorithms
• self-organized criticality
• rotor-routers
• tropical geometry
• duality

Prequisite: Math 332

Text

There is no formal text on this subject. Notes will be posted online after each class. (In fact, it is hoped that the notes for this course will grow into a book.) The following paper is a good introduction: Chip-Firing and Rotor-Routing on Directed Graphs.

Projects

Each student will complete a final project for the course. Most likely, the project will involve creating original mathematics. Here is a link to some ideas for projects.

This Week

• Monday. Critical group of an oriented matroid.
• Wednesday. Talk about final papers.
• Friday. No class.

Assignments

• HW 1, due 9/3: handout.
• HW 2, due 9/10: handout.
• HW 3, due 9/17: handout.
• HW 4, due 9/24: handout.
• HW 5, due 10/1: handout.
• HW 6, due 10/8: handout.
• HW 7, due 10/29: handout. Solutions.
• HW 8, due 11/8: handout. Solutions.

Handouts

• Chip-Firing and Rotor-Routing on Directed Graphs.
• What is a Sandpile?
• Review of modules.
• Proof of the matrix-tree theorem.
• Algebraic geometry of sandpiles.
• Riemann-Roch.
• Wilmes’ thesis.
• Class group versus the critical group.
• HW 5, problem 9.

Sandpile Catalog

Here is a list of all connected undirected graphs with at most 7 vertices, along with some information about their sandpile groups.

Sage

Sage is a free open-source mathematical software system. It can plot functions, take derivatives and limits, integrate, and solve equations (among many other things). Check out the Sage website if you are interested. You can use it from your web browser or download it for free onto your own computer (Linux, Mac, or Windows). For tips on using Sage, click here.

The Sage package, sandpile.sage (right-click to download), performs sandpile calculations. The manual is here.

Miscellaneous Links

• Reed College Mathematics Colloquium
• Smith Normal form

Class Summary

Week 1

• Monday. Configurations of sand; the Laplacian of a graph.
• Wednesday. The reduced Laplacian. Stabilization. Definition of the sandpile group.
• Friday. The sandpile group is a group isomorphic to .

HW

• HW 1, due 9/3: handout

Week 2

• Wednesday. Smith normal form.
• Friday. Matrix-tree theorem.

HW

• HW 2, due 9/10: handout

Week 3

• Monday. Matrix-tree theorem consequences. Conjectures from last week’s homework.
• Wednesday. Rotor-routers. Burning configurations.
• Friday. Burning configurations.

HW

• HW 3, due 9/17: handout

Week 4

• Monday. Kernel of the Laplacian. Proof of conjecture from HW 2.
• Wednesday. Dependence of the sandpile group on the choice of sink.
• Friday. Sandpiles as discrete Riemann surfaces.

HW

• HW 4, due 9/24: handout

Week 5

• Monday. Riemann-Roch: introduction.
• Wednesday. Riemann-Roch: equivalent conditions.
• Friday. Superstables.

HW

• HW 5, due 10/1: handout

Week 6

• Monday. Minimal effective divisors and minimal effective scripts.
• Wednesday. Minimal alive divisors, minimal recurrents, and minimal effective divisors.
• Friday. Riemann-Roch for undirected graphs.

HW

• HW 6, due 10/8: handout

Week 7

• Monday. Lattice ideals. The toppling ideal.
• Wednesday. Groebner bases.
• Friday. Buchberger algorithm. Groebner bases for toppling ideals.

HW

• HW 7, due 10/29: handout

Week 8

• Monday. Groebner basis for the toppling ideal.
• Wednesday. Cycles and cuts.
• Friday. Cycles, cuts, the Laplacian, and dual graphs.
  • HW 7, due 10/29: handout

Week 9

• Monday. The sandpile group of the dual graph.
• Wednesday. The sandpile group of the dual graph.
• Friday. No class. Project groups meet.

HW

• HW 8, due 11/8: handout

Week 10

• Monday. Matroids and the Tutte polynomial.
• Wednesday. Merino’s theorem.
• Friday. Group presentations. The Bombay trick. Acyclic orientations.

Week 11

• Monday. Acyclic orientations.
• Wednesday. Acyclic orientations.
• Friday. Duals of graphs on surfaces.

Week 12

• Monday. Integer points in polyhedra.
• Wednesday. Duals of graphs on surfaces.
• Friday. No class. Thanksgiving break.

Week 13

• Monday. Saturation of the toppling ideal.
• Wednesday. Oriented matroids.
• Friday. Critical group of an oriented matroid.

Homework and Grades

Your grade will be based on the weekly homework, class participation, and final project. When I return your homework, I will put numbers next to each problem according to the following scheme:

5 - perfect
4 - minor mistakes
3 - major mistake, right idea
2 - wrong but contains a significant idea
1 - wrong but contains a relevant idea
0 - none of the above

NOTES:

• Homework is due each Friday at the beginning of class.
• Late assigments (i.e., turned in after class on Friday), if complete, may be given half-credit, but it is unlikely you will get written comments on your work.
• If you miss an assignment or quiz due to an illness, please inform me as soon as possible.
• Note our final exam date before making airline reservations to leave at the end of the semester.
• Deadline to add classes or change sections: Friday, September 10.
• Deadline to drop spring semester classes without the grade of “W” (withdraw): Monday, October 4.
• Deadline to withdraw from spring semester classes: Monday, November 8.