Summer 2007 REU

Discrete Mathematics (full program)

Linear Algebra and Number Theory (apprentice program)

Instructor: László Babai

What's New? | Course Info | Puzzle sheets and Handouts | DM Class Notes | Apprentice Class Notes

What's New?

"Transfinite Combinatorics" (TC) (second module of Discrete Mathematics) started on Monday, July 23

TC: Class 9 notes posted (proofread by instructor)

TC: Class 8 notes posted (proofread by instructor)

TC: Class 7 notes posted (NOT proofread by instructor)

TC: Class 6 notes posted (proofread by instructor)

TC: Class 5 notes posted (proofread by instructor)

TC: Class 4 notes posted (proofread by instructor)

TC: Class 3 notes posted (proofread by instructor)

TC: Class 2 notes posted (NOT proofread by instructor)

TC: UPDATED Class 1 notes posted (partially proofread by instructor)

Old News

Puzzle solutions to be discussed both in the remaining apprentice classes (Thu and Fri, July 12 and 13) and in the DM class (Thu, July 12). Come prepared with solutions, attempts, questions.

DM: Class 10 notes posted (class Tue 7-10, notes posted 7-12, 12:45am)

Appr: Class 12 notes posted (Wed 7-11)

Appr: Class 11 notes posted (Tue 7-10)

DM: Class 9 notes posted (class Fri 7-6, notes posted 7-8, 3am)

Appr: COMPLETE NOTES of Class 9 notes posted (Class Fri 7-6, first part of notes posted 7-6, 9:30 pm; complete notes posted 7-7, 1:20 am)

Apprentice puzzle problem sheet posted. Last updated July 5, 3:55pm. Solutions discussed Monday, July 9, 1:30-2:30.

Appr: INCOMPLETE yet greatly expanded Class 4 notes posted; the notes now include a large portion of the proof of the Matrix-Tree Theorem. (Posted Fri 6-29, 6:45 pm.)

Puzzle sheets and Handouts

• Apprentice puzzle problems (PDF) (posted July 4; solutions will be discussed on Monday, July 9, 1:30 - 2:30 - come prepared to present a solution, or an idea, an approach, a question. The session is open to all REU participants)
• Second set of puzzle problems (PDF) (June 19)
• First set of puzzle problems (PDF) (June 18)
• Discrete Mathematics Lecture Notes (PDF)

Class Notes: Transfinite Combinatorics: the world of Paul Erdős (weeks 6-8 of Discrete Math)

• Day 9 notes (PDF) (Fri, Aug 10)
• Day 8 notes (PDF) (Wed, Aug 8)
• Day 7 notes (PDF) (Mon, Aug 6) NOT proofread by instructor
• Day 6 notes (PDF) (Fri, Aug 3)
• Day 5 notes (PDF) (Wed, Aug 1)
• Day 4 notes (PDF) (Mon, July 30)
• Day 3 notes (PDF) (Fri, July 27)
• Day 2 notes (PDF) (Wed, July 25) NOT proofread by instructor
• Day 1 notes (PDF) (Mon, July 23) updated Jul 26, partially proofread by instructor

Class Notes: Discrete Math - first 4 weeks (Combinatorics, linear algebra, and group theory, culminating in a theorem of T. Gowers)

• Day 10 notes (PDF) (Tue, July 10)
• Day 9 notes (PDF) (Fri, July 6)
• Day 8 notes (PDF) (Tue, July 3)
• Day 7 notes (PDF) (Thu, June 28)
• Day 6 notes (PDF) (Tue, June 26)
• Day 5 notes (PDF) (Fri, June 22) same reduced to half size (PDF)
• Day 4 notes (PDF) (Thu, June 21)
• Day 3 notes (PDF) (Wed, June 20)
• Day 2 notes (PDF) (Tue, June 19)
• Day 1 notes (PDF) (Mon, June 18)

Class Notes: Apprentice Program (Determinants and Linear Algebra, with surprising applications to combinatorics)

• Day 12 notes (PDF) (Wed, July 11) rational roots of polynomials with integer coefficients, the Hoffmann - Singleton Theorem: a mthematical gem; Helly's Theorem; the minimal polynomial of matrioces and linear transformations
• Day 11 notes (PDF) (Tue, July 10) dimension of spaces of multivariate polynomials, g.c.d. of integers and of polynomials; the resultant in Sylvester's determinant form, Blokhuis's proof of Bollobas's Theorem via resultants
• Day 10 notes (PDF) (Mon, July 9) Laplace expansion and Bollobá's Theorem
• Day 9 notes (PDF) (Fri, July 6) circulants, their common eigenbasis, eigenvalues; Hermitian spaces, Gram-Schmidt orthogonalization, unitary matrices, complex Spectral Theorem, normal matrices
• Day 8 notes (PDF) (Thu, July 5) the Cayley-Hamilton Theorem
• Day 7 notes (PDF) (Tue, July 3) geometry: the determinant as volume, angle between subspaces; the Binet-Cauchy formula
• Day 6 notes (PDF) (Mon, July 2) affine and convex combinations; basic linear algebra: linear independence, "miracle #1"
• Day 5 notes (PDF) (Fri, June 29) matrices vs linear maps, change of basis, Euclidean/Hermitian spaces, orthonormal bases, the Spectral Theorem, proof, Rayleigh's principle
• Day 4 INCOMPLETE notes (PDF) (Thu, June 28) inclusion-exclusion, 2nd proof; proof of the matrix-tree theorem
• Day 3 notes (PDF) (Wed, June 27) Laplace expansion of determinant, the Bollobás inequality in extremal combinatorics stated, the matrix-tree theorem (Kirchhoff), inclusion-exclusion
• Day 2 COMPLETE notes (PDF) (Tue, June 26. Complete version posted June 28, 1:30am) an n x n determinant, multivariate polynomials, Vandermonde determinant, eigenvalues, eigenbases, circulant
• Day 1 notes (PDF) (Mon, June 25) permutations, cycle decomposition, parity, determinant, permanent