REU 2004, Discrete Mathematics Sequence

First Series

• 1st Class, 6/21/2004 (pdf|html): Points in the plane; Games: on a chessboard, on even sets, on a pool table, and the divisor game; Ramsey numbers and Erdős-Rado arrow notation.
• 2nd Class, 6/22/2004 (pdf|html): Games continued: dominoes and triominoes, Knight's trail, chocolate bar, and others; decision trees and strategy functions; Hamilton cycles, bipartite graphs.
• 3rd Class, 6/23/2004 (pdf|html): Graph Theory: spanning trees, legal colorings, chromatic numbers; Jensen's inequality; Graphs without short cycles: Kővári-Sós-Turán theorem and a theorem by Erdős.
• 4th Class, 6/24/2004 (pdf|html): Graph theory continued: edge- and vertex-connectednees, Mengar's theorem; tiling puzzles; the game "Set" and Szemerédi's theorem, supermultiplicate functions.
• 5th Class, 6/25/2004 (pdf|html): Density versions of coloring theorems, hypergraphs, Steiner triple systems, projective planes, Galois planes, the Fundamental Theorem of Projective Geometry.
• 6th Class, 6/28/2004 (pdf): North-South game, number of unit distances in the plane < n^3/2, max distance occurs ≤ n times, fitting squares, tiliing rectangles by rectangles with at least one integer dimension.
• 7th Class, 6/30/2004 (pdf): Puzzles on lamp switches and prisoners, Fisherman's clubs, Ramsey theory.
• 8th Class, 7/2/2004 (pdf): Steiner triple systems, affine spaces, the order of a finite field, Euler's 36 officers problem.
• 9th Class, 7/7/2004 (pdf): Extremal set theory, Eventown and Oddtown, isotropic vectors and spaces.
• 10th Class, 7/9/2004 (pdf): Cauchy-Hilbert matrix, Cauchy's functional equation and Hamel bases, some problems in elementary number theory, Ramsey theory.
• 11th Class, 7/13/2004 (pdf): Totally unimodular matrices, Latin squares, counting perfect matchings in a bipartite graph: the permanent, doubly stochastic matrices.
• 12th Class, 7/15/2004 (pdf): Constructive proofs of negative results in Ramsey theory, bipartite Ramsey theory, Hadamard matrices, orthogonal matrices, upper and lower density.
• 13th Class, 7/20/2004 (pdf): the Gale-Berlekamp switching game.
• 14th Class, 7/22/2004 (pdf): Points in general position, pattern in proofs of inequalities using the linear algebra method, additional exercises in probability theory.
• 15th Class, 7/27/2004 (pdf): Bases for vector spaces of polynomials (and the cookie problem), projective representation of a graph.
• 16th Class, 7/29/2004 (pdf): Random variables, independenct events, conditional probability.
• 17th Class, 8/2/2004 (pdf): The Monty Hall paradox and the 2 envelope paradox, statistical vs linear independence, algorithms on conjuntive normal forms, algebraic coding theory.
• 18th Class, 8/4/2004 (pdf): Projective dimension of a graph continued, the Milnor-Thom theorem, implication of Warren's theorem.
• 19th Class, 8/6/2004 (pdf): Matrix rigidity, character tables.
• 20th Class, 8/9/2004 (pdf): Matrix rigidity continued.
• 21st Class, 8/11/2004 (pdf): Linear programming, Shannon capacity of a graph, Lovász's theta function.
• 22nd Class, 8/13/2004 (pdf): 0,1-measures, sign-rigidity.

• Logic, quantifiers, "Chapter 1" (lecture notes)
• Asymptotic Notation, "Chapter 2" (lecture notes)
• Graphs and Digraphs, "Chapter 6" (lecture notes)
• Finite Probability Spaces "Chapter 7" (lecture notes)

REU 2004, Linear Algebra Sequence

• 1st Class, 6/28/2004 (pdf): Vectore spaces and linear independence, dimension, basis, Fibonacci-type sequences.
• 2nd Class, 6/29/2004 (pdf): Subspaces, equivalence of bases, the Steinitz exchange principle, the equality of row and column rank, coordinates, linear maps and vector space isomorphisms, vector spaces over number fields, elementary operations.
• 3rd Class, 6/30/2004 (pdf): Rank, number fields and roots of unity, arithmetic functions, irreducible polynomials, Gauss' lemma, cyclotomic polynomials, algebraic numbers.
• 4th Class, 7/1/2004 (pdf): Linear maps, trace, determinant, the existence of nontrivial solutions.
• 5th Class, 7/2/2004 (pdf): Fields, latin squares, finite fields, greatest common divisors, polynomials and rational functions, field characteristic.
• 6th Class, 7/6/2004 (pdf): Inverse matrices, rank, the general linear group, similarity of matrices, the characteristic polynomial.
• 7th Class, 7/7/2004 (pdf): Change of basis, more on characteristic polynomials, the Cayley-Hamilton theorem, matrices of geometric tranformations, upper-triangular matrices, more on the determinant, permutations and parity, eigenvectors and eigenvalues.
• 8th Class, 7/8/2004 (pdf): The Cauchy-Hilbert matrix, perpendicularity, more on eigenvectors and eigenvalues.
• 9th Class, 7/9/2004 (pdf): The Vandermonde matrix, real symmetric matrices, inner products, orthonormality, the Spectral Theorem, invariant subspaces.
• 10th Class, 7/12/2004 (pdf): Recap of the Vandermonde matrix, real euclidean spaces and bilinear forms, the Cauchy-Schwarz inequality, orthogonal transformations.
• 11th Class, 7/13/2004 (pdf): MISSING
• 12th Class, 7/14/2004 (pdf): MISSING
• 13th Class, 7/15/2004 (pdf): Explicit form of the inverse matrix, Gram-Schmidt orthogonalization, algebraic numbers and minimal polynomials, the minimal polynomial of a matrix.
• 14th Class, 7/16/2004 (pdf): Rank inequalities, rings and ideals, the Gaussian integers, minimal polynomials and algebraic numbers, Jordan matrices.