DISCRETE MATHEMATICS (weeks 1--4) 2005

Instructor: Laszlo Babai

Groups, graphs, matrices, avalanches, and more: The Abelian Sandpile Model

Originating in statistical physics and nearly simultaneously and independently introduced in algebraic graph theory and in theoretical computer science in the 1990s, the Abelian Sandpile Model associates a variety of structures with a diffusion process on finite graphs. The model gives rise to a remarkably rich theory which connects the fields of graph theory, stochastic processes, commutative semigroups and groups, matrices and determinants, lattices in n-dimensional space, algorithms, number theory, fractals, and more. In the context of the Abelian Sandpile Model we shall learn about cyclotomic polynomials, the Jordan-Holder Theorem, the Laplacian and the matrix-tree theorem, and a lot more.

Open problems abound, covering all areas mentioned - you can pick your favorite.

This is a fun topic. We shall learn most prerequisites along the way.

PQ: Basic linear algebra and discrete math, or consent of instructor.

DISCRETE MATHEMATICS (weeks 5--8) 2005

Instructor: Laszlo Babai

The course covers topics in number theory, geometry, combinatorial structures, linear algebra, and discrete probability, highlighting surprising interactions between these areas. Students will discover the field through solving sequences of challenging problems. A number of open problems will also be discussed. The overlap with recent years will be minimal.

PQ: Basic linear algebra and discrete math, or consent of instructor.

Students interested in either module are strongly encouraged to take Math-28400, a.k.a. CS-27400, Honors Combinatorics and Probability, offered in Spring, see http://www.cs.uchicago.edu/courses/descriptions.php. That course is offered in alternate years only.