!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
Summer 2007 REU - Discrete Mathematics
Summer 2007 REU
Discrete Mathematics (full program)
Linear Algebra and Number Theory (apprentice program)
What's New?
| Course
Info
| Puzzle sheets and Handouts
| DM Class Notes
| Apprentice Class Notes
"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.)
- Day 9: axiomatisability of 3-colorability, Hamiltonicity, and finite graphs, the size of an ultraproduct, the random graph and Ramsey's theorem revisited, measurable implies strongly inaccessible (PDF) (Fri, Aug 10)
- Day 8: some Erdős-Rado arrows, random graphs, axiomatisability of graph theories with the application of ultraproducts (PDF) (Wed, Aug 8)
- Day 7: matchings and König-Hall obstacles, the Erdős-Hajnal theorem, countably additive (0,1)-measures (PDF) (Mon, Aug 6) NOT proofread by instructor
- Day 6: the Cantor-Bernstein-Schröder theorem, chromatic numbers, set theory and categoricity, topological sorts and Tychanoff's theorem, first-order logic with equality, proof of Erd&337s-de Bruijn via ultrafilters, ordinal Ramsey theory (PDF) (Fri, Aug 3)
- Day 5: the continuum hypothesis, transfinite induction, finitely additive (0,1)-measures revisited, Ramsey theory (PDF) (Wed, Aug 1)
- Day 4: König's path lemma and its applications to tilings and the Erdős-de Bruijn theorem, canonical notation for ordinals, Fodor's lemma, the slot machine revisited, puzzles using transfinite induction and recursion, finitely additive (0,1)-measures, filters and ultrafilters (PDF) (Mon, July 30)
- Day 3: Directed graphs, 3-cycles, Borsuk's theorem, more on cardinals and ordinals (ordinal prefixes, base-ω number system, Fodor's lemma) (PDF) (Fri, July 27)
- Day 2: Exercises on almost disjoint sets and T and L-shapes, pathological functions (w.r.t. continuity), transcendental numbers, the lemmas of Zorn and König (PDF) (Wed, July 25) NOT proofread by instructor
- Day 1: Dictator switches, numerical tilings, graph colorings, Erdős-Rado arrow symbol, cardinal and ordinal numbers, cardinal and ordinal arithmetic (PDF) (Mon, July 23) updated Jul 26,
partially proofread by instructor
- Day 10: Review of inequalities and means, characters and commutators, 1-dimensional representations, affine groups and their structure, proof of Frobenius' theorem (PDF) (Tue, July 10)
- Day 9: General and special linear groups, group representations, Frobenius' theorem, character theory, regular representations (PDF) (Fri, July 6)
- Day 8: Proof of Gower's theorem, corollaries of the quasirandomness theorem, eigenspaces (PDF) (Tue, July 3)
- Day 7: Another look at Berlekamp's switching game, Hadamard matrices, and Gower's theorem; the quasirandomness theorem (PDF) (Thu, June 28)
- Day 6: Finite probability spaces, Berlekamp's switching game, and Hadamard matrices (PDF) (Tue, June 26)
- Day 5: Puzzle problems on isomorphisms and Berlekamp's Switching Game, systems of linear equations, linear maps vs matrices, change of basis, characteristic polynomial, orthogonality and symmetric matrices, bipartite expansion (PDF) (Fri, June 22)
same reduced to half size (PDF)
- Day 4: Puzzle problems on finite groups; linear algebra: rank and basis; linear maps: kernel, image, quotient; systems of linear equations; matrix representation of linear maps; eigenvalues, eigenvectors, and eigenbases; orthogonality, isotropic subspaces, Eventown; Oddtown (PDF) (Thu, June 21)
- Day 3: Orders of group elements, congruences of the plane, finite fields, direct products of groups, torsion groups, and the fundamental theorem of finitely generated abelian groups (PDF) (Wed, June 20)
- Day 2: Relations on sets, Bell numbers, more on group theory (permutation groups), Sam Lloyd's "15" puzzle, the symmetries of Platonic solids, and the theorems of Frobenius, Cayley, and Frucht (PDF) (Tue, June 19)
- Day 1: Ideas in graphs, groups, linear algebra, and combinatorics (PDF) (Mon, June 18)
- Day 12 notes (PDF) (Wed, July 11) rational roots
of polynomials with integer coefficients, the Hoffmann - Singleton Theorem:
a mathematical 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
Back to top