Discrete Mathematics REU, Summer 2005
What's
New?
| Course
Info
| Handouts
| Sandpile lecture notes
| Linear Algebra
| Potpourri
- Course Description HTML
- Schedule (updated on June 26):
- For information about the entire REU program, see Peter
May's home page.
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 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
Click here to see
Miklós Abért's problem sets.
- Lecture 1 (June 27): Basic linear algebra, with vector spaces, linear combinations, linear independence, applications to the Fibonacci sequence, and Fisher's inequality.
DVI,
PS,
PDF
- Lecture 2 (June 29): Spanning vectors, properties of row and column rank, linear algebra methods in combinatorics, Eventown and Oddtown, fields.
DVI,
PS,
PDF
- Lecture 3 (July 6, revised Jul 8): Linear maps, geometric transformations, the rank and kernel of maps, systems of linear equations, orthogonality, isotropic vectors and spaces.
DVI,
PS,
PDF
- Lecture 4 (July 8): Recap of systems of equations, eigenvalues and eigenvectors, the Spectral Theorem, bases and linear transformations, change of basis, the Cayley-Hamilton theorem.
DVI,
PS,
PDF
- Lecture 5 (July 11): Bases and similarity, diagonizability and eigenbases, relations between the roots and coefficients of a polynomial, real roots of polynomials, orthonormality and sense-preservation.
DVI,
PS,
PDF
- Lecture 6 (July 13): Real Euclidean spaces, orthogonal polynomials, orthogonal transformations, Hadamard's inequality.
DVI,
PS,
PDF