Name of the course: | Mathematical Structures | ||||||
---|---|---|---|---|---|---|---|
Instructor: | Jaikumar Radhakrishnan jaikumar@tifr.res.in |
||||||
Lecture timings: |
|
||||||
Text books: |
|
There are no prerequisites for this course beyond high-school mathematics, but there will be a fair amount work involved outside the class. In particular, the audience will be expected complete some proofs themselves. There will be regular homework assignments.
The course grade will be based on homeworks.
Week 1 6, 8 Aug 03 |
|
||
Week 2 11, 13, 14 Aug 03 | Combinatorics: The inclusion-exclusion
principle. Kaplansky's solution to the Problème de
ménages, Lovász's graph reconstruction
theorem. Set theory: axiom of unions, axiom of powers. Suggested reading chapters 4 and 5 of [H]. Homework due 3 Sep 03. Algebra: Invertible matrices, row-echelon form of invertible matrices, computing the inverse, left-inverse = right inverse. Determinants. Suggested reading: pages 16--20 of [A]. Homework: page 32 problem 16, page 33 problem 19, page 34 problems 18, 19, page 36 problem 4 (due on 22 Aug 03). |
||
Week 3 18, 20, 22 Aug 03 |
Combinatorics:
Lovász's graph reconstruction theorem, Ryser's
formula. Homework (due on
25 Aug 03).
Set theory: Ordered pairs, Cartesian products, relations, equivalence relations and classes. Suggested reading: chapters 6 and 7 of [H]. Homework due on 3 Sep 03. Algebra: Determinants, uniqueness of determinants, determinant of the product of matrices, determinants of invertible matrices, Cramer's formula. Suggested reading: pages 21--31 of [A]. Homework: page 35 problems 9, 13 on determinants, page 35 problem 5 on permutation matrices, page 36 problem 3 on Cramer's rule (due on 12 Sep 03). |
||
Week 4 25, 27, 29 Aug 03 |
Combinatorics: Permutations, cycle representation,
Stirling numbers of the first kind. Suggested reading:
pages 1--20 of [S]. Set theory: Functions, characteristic functions, families of sets. Homework (due on 3 Sep 03). Suggested reading: chapters 8 and 9 of [H]. Algebra: Associative composition operations, groups, subgroups, isomorphism of groups. Suggested reading: pages 38--50 of [A]. |
||
Week 5 1, 3, 5 Sep 03 |
Combinatorics: Representations of permuations as trees.
Suggested reading:
pages 20--25 of [S]. Set theory: Inverses and compositions of functions, numbers, the axiom of infinity, uniqueness of omega. Suggested reading: chapters 10 and 11 of [H]. Algebra: Cosets, Lagrange's Theorem, order of an element, cyclic groups, groups of prime order, quotient groups. Suggested reading: pages 51--69 of [A]. Homework: page 70 problems 2, 10, 11, 12, 13, 14 (see above for problems on matrices, due on 12 Sep 03). |
||
Week 6 8, 10, 12 Sep 03 |
Combinatorics: The twelvefold way, the number of functions
from N to X (surjective, injective, with N indistinguishable,
with X indistinguishable), Striling numbers of the second
kind, Bell numbers, unordered
partitions. Homework
(due on 19 Sep 03) Set theory: Peano's axioms, recursion theorem. Suggested reading: chapter 12 of [H]. Algebra: Homomorphisms, The first isomorphism theorem. Suggested reading: pages 78--87 of [A]. |
||
Week 7 15, 17, 19 Sep 03 |
Combinatorics: linear recurrence relations and generating
functions.
Set theory: Arithmetic, cardinality of sets. Suggested reading: chapter 13 of [H]. Homework: page 37 bottom, page 41 bottom, page 49 bottom, page 52 second paragraph (due 26 Sep 03). Algebra: Abstract fields, vector spaces, linear combination, span, linear independence, basis. Suggested reading: chapter 3 of [A]. Homework: page 104 problem 10, page 105 problem 15. |
||
Week 8 22, 24, 26 Sep 03 |
Homework (due 13
October 2003).
Combinatorics: Catalan numbers, the ballot problem.
Set theory: Axiom of choice. Every infinite set has a subset equivalent to the set of natural numbers. Algebra: Basis, cardinalities of linearly independent sets and spanning sets, dimension of a vector space, the dimension of a subspace, change of basis. |
||
Week 9 29 Sep 03, 1 Oct 03 |
Combinatorics: Group actions on a set, stabilizers, fixed
points, Burnside-Frobenius theorem.
Set theory: Zorn's lemma |
||
Week 10 13, 15, 17 Oct 03 |
Combinatorics: Pólya's counting theorem.
Homework (due 24
October 2003).
Set theory: Well-ordering, transfinite-induction,
transfinite recursion theorem. Algebra: Change of basis, linear transformation, kernel, image, matrix of a linear transformation, rank-nullity theorem. |
||
Week 11 20, 22, 24 Oct 03 |
Combinatorics: The power set of [n]. Chains, antichains,
Sperner's theorem, chain decomposition of of P([n]).
Matchings in bipartite graphs: Hall's theorem.
Set theory: Axiom of substitution, ordinal numbers.
Homework announced in class (due 29 October).
Algebra: Linear operators, eigen values, the characteristic polynomial, the Cayley-Hamilton theorem. |
||
Week 12 27, 29, 31 Oct 03 |
Combinatorics: Symmetric chain decomposition of P([n]).
Dilworth's theorem, Erdös-Sekeres theorem.
Set theory: Sets of ordinal number, ordinal arithmetic. Algebra: Orthogonal matrices, rigid motion, orthogonal matrices with determinant 1 and rotations in 2 and 3 dimensions. Diagonalizable matrices. Homework from [A] (due 7 Nov 03): problem 6 (page 146, top), problem 6 (page 146, bottom), problem 8 (page 148, top), problem 9 (page 149). |
||
Week 13 3, 5, 7 Nov 03 |
Combinatorics: Shadows, Kruskal-Katona theorem,
Erdös-Ko-Rado theorem, reverse lexicographic order of sets.
Set theory: Schröder-Bernstein theorem, countable sets. Algebra: Minimal polynomials of matrices, diagonalizable matrices, a matrix is diagonalizable iff its minimal polynomial factors into distinct linear factors. |
||
Week 14 10, 12, 14 Nov 03 |
Combinatorics: Proofs of Kruskal-Katona theorem and
Erdös-Ko-Rado theorem. Homework (due 17
November 2003).
Set theory: Cardinal numbers
Algebra: Direct sum decompositions, projection operators, invariant direct sums |
||
Week 15 17, 19, 21 Nov 03 |
Combinatorics: Turan's theorem and Ramsey's theorem for graphs.
Combinatorics: General Ramsey's theorem
Algebra: Primary decomposition theorem. |
||
Week 16 24, 26, 28 Nov 03 |
Combinatorics: Erdos-Szekeres theorem: integer sequences,
points in the plane.
Algebra: Rational canonical Form
Algebra: Jordan canonical form |
||
Week 17 1, 3, 4 Dec 2003 |
Algebra:
Algebra:
Algebra: The spectral theorem: symmetric matrices, Hermitial matrices, normal matrices. Singular value decomposition. |