# Discrete Mathematics REU, Summer 2005

## Potpourri (weeks 5--8)

We discuss an assortment of problems connecting combinatorics, geometry, number theory, and linear algebra. The lead theme will be "polynomials." We shall also discuss some of the problems left over from Miklós Abért's problem sheets. DVI, PS, PDF
If you wish to present a solution or discuss your approach, please send the instructor email.
• Lecture Notes Jul 18 (last updated Aug 2): Two-distance sets, Bollobás' problem. DVI, PS, PDF
• Lecture Notes Jul 20 (last updated Aug 2): Sperner's theorem and Bollobás' inequality. DVI, PS, PDF
• Lecture Notes Jul 22(last updated Aug 2): Spectral properties of graphs: recap of 2-distance sets, interlacing, Chebyshev's polynomials. DVI, PS, PDF
• Lecture Notes Jul 25(last updated Aug 2): Eigenvalues of graphs: powers of the adjacency matrix, eigenvalues and node degrees, the interleaving theorem, isoperimetric inequality. DVI, PS, PDF

## Lecture Notes on Sandpile Model (weeks 1--4)

• Lecture Notes Jun 21 (last updated Jun 22): The determinant, permutations and cycle notation, lattices, polynomials, semigroups. DVI, PS, PDF
• Lecture Notes Jun 22 Morning Class (last updated Jun 22): Semigroups continued, monoids, ideals, the Rees quotient, linear combinations. DVI, PS, PDF
• Lecture Notes Jun 22 Afternoon Class (last updated Jun 22): Groups, arithmetic functions: the Euler function and the Moebius function, subgroups and orders, Lagrange's theorem, Fermat's Little Theorem, roots of unity, the nth cyclotomic polynomial. DVI, PS, PDF
• Lecture Notes Jun 23 Morning Class (last updated Jun 27): Polynomials, digraphs and adjacency matrices, Kirchhoff's theorem, Cayley's formula, some exercises on semigroups. DVI, PS, PDF
• Lecture Notes Jun 23 Afternoon Class (last updated Jun 27): Proof of Cayley's formula continued, ideals in semigroups, the chip-firing game, the Abelian Sandpile Model, group quotients, generators and relations in commutative models, the Sandpile monoid. DVI, PS, PDF
• Lecture Notes Jun 27 (last updated Jun 30): Group presentations, the Sandpile monoid, the "big cycle" example, the structure of finitely generated abelian groups. DVI, PS, PDF
• Lecture Notes Jun 30 (last updated Jul 13): The inclusion-exclusion theorem, full proof of the matrix-tree theorem, some binomial coefficient identities, the confluence theorem. DVI, PS, PDF
• Lecture Notes Jul 6 (last updated Jul 8): Invertible matrices, Smith equivalence and the Smith normal form, using Smith matrices to prove the Fundamental Theorem of Finitely Generated Abelian Groups (left partially as exercise). DVI, PS, PDF
• Lecture Notes Jul 8 (last updated Jul 11): Monoids, the Sandpile group, complete proof of FToFGAG's, the rank of the ranks of groups. DVI, PS, PDF
• Lecture Notes Jul 11 (last updated Jul 13): Algorithmic problems: the four main problem, the length of an avalanche, open questions, the burning algorithm. DVI, PS, PDF