Apprentice Program, Summer 2012 REU
Linear Algebra and Combinatorics

Instructor: László Babai

Home | What's New? | Synopsis | Calendar | Problem sets | Notes | Further reading

What's New?

Press your browser's "refresh" button to get the current version of this page.

A second set of supplementary problems has been posted (7/6).

A set of supplementary problems has been posted. These problems are directly related to class and most of them have been stated in class.

Note changes in the schedules of Weeks 3, 4, 5 (see "Calendar" section below). Note especially that during these weeks, the Tuesday afternoon sessions begin at 4:30pm.


The course will develop the usual topics of linear algebra and illustrate them on highly unusual and often striking applications to combinatorics, discrete geometry, and discrete probability. Emphasis will be on creative problem solving and discovery.

The basic topics include permutations, determinants, linear transformations, the characteristic polynomial, Euclidean spaces, orthogonalization, the Spectral Theorem, linear algebra over finite fields. Application areas to be highlighted include, time permitting, extremal set theory, the spectral theory of graphs (expansion, mixing of random walks, independence number, Shannon capacity, etc.), k-wise independence of events, counting zero-patterns of polynomial maps, and more.

The course is peppered with a potpourri of fun problems.

Go to top

Teaching Assistants

The TAs conducting the problem sessions are Rita Jimenez-Rolland (week 1 only), Jonathan (Jonny) Gleason, Michael Smith, Vaidehee Thatte, Bobby Wilson, Matthew Wright (starting week 2), Casey Rodriguez (starting week 3).


Week 1: June 18-22 (MWF 9:30-noon classes by instructor, TTh 11-12, 5-6 problem sessions by TAs)
Week 2: June 25-29 (MWF 9:30-noon classes by instructor, TTh 11-12, 5-6 problem sessions by TAs)
Week 3: July 2-6 (All classes held by instructor: MF 9:30-12, TTh 11-12, 4:30-6. No class on Wed, July 4.)
Week 4: July 9-13 (Problem sessions by TAs MW 9:30-12, TTh 11-12, 4:30-6; class by instructor Fri 9:30-12)
Week 5: July 16-20 (MWF 9:30-noon classes by instructor, TTh 11-12, 4:30-6 problem sessions by TAs)

Problem sets

Your principal resources are the online problem sets listed here. Solutions are discussed in the problem sessions (schedule above). Send email to the instructor about the "AHA" problems.

The problem sessions are an integral part of the course; you are expected to attend and to participate by presenting your thoughts about the problems.

There is some overlap among these problem sets.

Class notes

Browse the class notes of the 2011 apprentice program. While this year's course is not identical with the 2011 course, there is a large overlap.

You find all prior years' notes here.

Go to top

Further reading

REU 2012 Home

László Babai's home page

Back to top