Autumn 2003: a graduate course on mathematical structures

Name of the course: Mathematical Structures
Instructor: Jaikumar Radhakrishnan
jaikumar@tifr.res.in
Lecture timings:
Combinatorics:Mondays 10:00am to 11:00am
Set Theory:Wednesdays 10:00am to 11:00am
Algebra:Saturdays 10:00am to 11:00am
We begin at 9:45am with a 15 minute review.
Text books:
[H] Naive set theory by P Halmos, Springer-Verlag
[A] Algebra by M Artin, Prentice-Hall India
[An] Combinatorics of finite sets by I Anderson, Oxford Science Publications
[S] Enumerative combinatorics (Volume I) by RP Stanley

Outline

The goal of this course is to introduce the audience to the mathematical structures and the types of reasoning that one might encounter in Computer Science. The topics will be divided into three broad streams: set theory, algebra and combinatorics. In set theory, we will be content with covering the topics given in the text. The idea is to introduce the audience the axiomatic development of the theory and some notions that they are likely to encounter in their study of other subjects, e.g., the axiom of choice, Zorn's lemma, transfinite recursion, ordinal numbers, cardinal numbers etc.. In algebra, we will study basic algebraic structures groups, rings, fields, vector spaces etc. We will be following the text book closely, covering about 10-15 pages every week. In combinatorics, we will study elementary counting methods such as the inclusion-exclusion method, generating functions, Polya's counting theorem and problems in extremal combinatorics such as Sperner's theorem, Dilworth's theorem, Erdos-Ko-Rado theorem, Kruskal-Katona theorem, Ramsey's theorem, combinatorial designs etc. Every now and then we will pick up material from journal papers and other sources, to illustrate how these combinatorial facts are applied.

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.

Lectures

Week 1
6, 8 Aug 03
Set theory: axiom of extension, axiom of specification, axiom of pairing. Suggested reading: chapters 1, 2 and 3 of [H]. Homework due on 13 Aug 03.
Algebra: matrices, row operations, elementary matrices, row reduction, system of linear equations, the row echelon form of a matrix, inverses of square matrices. Suggested reading: pages 1--15 of [A].
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.
Jaikumar Radhakrishnan
Last modified: Mon Nov 10 18:23:26 IST 2003