Autumn 2006: graduate course

Name of the course: Mathematical Structures
Instructor: Jaikumar Radhakrishnan
jaikumar@tifr.res.in
Lecture timings:
Combinatorics:Mondays 9:30am to 10:30am
Set Theory:Wednesdays 9:30am to 10:30am
Algebra:Fridays 9:30am to 10:30am
Text books:
[H] Naive set theory by P Halmos, Springer-Verlag
[A] Algebra by M Artin, Prentice-Hall India. [HK] K Hoffman and R Kunze, Prentice-Hall India.
[An] Combinatorics of finite sets by I Anderson, Oxford Science Publications
[S] Enumerative combinatorics (Volume I) by RP Stanley
[B] Combinatorics by B Bollobás. Cambridge.

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 develop familiarity with the axiomatic development of the theory and concepts (e.g., the axiom of choice, Zorn's lemma, transfinite recursion, ordinal numbers, cardinal numbers etc.), that one is likely to encounter in the study of other subjects, 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 students will be expected complete some proofs themselves. There will be regular homework assignments.

The course grade will be based on homeworks and paper presentation. You can choose from the following list. [The first person who sends me email claiming the paper, gets to present that paper! Also, please pick one of the following dates 1, 5, 6, 7, 8 December afternoon 1:30pm to 3:30pm.] You will be responsible for a two hour detailed presentation with the necessary background. Please consult Bob Spillman and Ian Parberry's guides [Available here] for ideas about structuring your presentations.

  1. Kruskal's theorem and Nash-Williams theory by Ian Hodkinson and Wilfred Hodges [PDF]. A complete proof of Kruskal's theorem will be sufficient.
  2. Inclusion-exclusion: exact and approximate by J. Kahn, N. Linial and A. Samorodnitsky. [PS]
  3. Perfrect graphs (as presented in Section 5.5 of Diestel's Graph Theory). [ PDF]
  4. Perfect matchings in balanced hypergraphs by Michele Conforti, Gerard Cornuejols, Ajai Kapoor and Kristina Vuscaronkovic. [PDF]
  5. Sur l'etude algebrique de certains types de lois de mariage by Andre Weil (in French, I have the article). The book Finite Mathematics by Kemeny, Snell and Thompson has an section based partly on this article (I have issued the book from our library). You may present the original French article or the section from the book.
  6. I will add more ...

Lectures

Week 1
23, 25 Aug
Algebra: matrices, row operations, elementary matrices, row reduction, system of linear equations, the row echelon form of a matrix, inverses of square matrices. Invertible matrices, row-echelon form of invertible matrices, computing the inverse, left-inverse = right inverse. Suggested reading: pages 1--18 of [A] Lecturer: Pranab Sen.
Week 2
28, 30 Aug,
1 Sep		 Algebra: Determinants, axiomatic charecterization, determinant of a product of matrices, Cramer's rule. Elementary properties of permutation matrices. Suggested reading: pages 19--31 of [A]. Homework: Chapter 1, Sec 1 (16, 19), Sec 2 (18b, 19), Sec 3 (9, 12, 13) Sec 5 (3). (due 15 Sep 06)
Combinatorics: The inclusion-exclusion principle. Counting derangements. Suggested reading: Combinatorial Mathematics by H Ryser (Chapter 2). Lecturer: Pranab Sen.
Week 3
4, 6, 8 Sep 		Combinatorics: Applications of inclusion-exclusion: formula for Euler's totient function, Ryser's formula, determinant versus permanent function, Ryser's depth-three arithmetic circuit, Kaplansky's solution to the Problème des ménages, Lovász's graph reconstruction theorem. Suggested reading: Combinatorial Mathematics by H Ryser (Chapters 2 and 3). Lecturer: Pranab Sen.
Week 4
11, 13, 15 Sep 		Combinatorics: Homework (due 25 Sep).
Algebra: Definition of group, examples: GLn, SLn, Un, On, SOn. Subgroup, subgoups of Z, Euclid's GCD algorithm. Cyclic groups, classification, subgroups of cyclic groups. Homomorphisms (image, kernel), Normal subgroup, Cosets, Lagrange formula. Suggested reading: 38--59 from [A].
Week 5
18, 20, 22 Sep 03		 Combinatorics: Permutations, cycle representation, Stirling numbers of the first kind. Suggested reading: pages 1--20 of [S].
Set theory: Axiom of extension, axiom of specification, axiom of pairing. Suggested reading: chapters 1, 2, 3 and 4 of [H]. Homework: See page 13 of [H]. Show the following: A U empty = A, A U B = B U A, A U (B U C) = (A U B) U C, A U A = A, A subset B iff A U B = B (due 4 Oct).
Algebra: Products of groups, quotient groups. Suggested reading: pages 59--69 of [A].
Week 5
25, 27, 29 Sep 06		 Combinatorics: Combinatorial proofs for an identity involving the Striling number of the first kind.
Homework (due 9 Oct 06).
Set theory: Intersections, complements, ordering, ordered pairs, Cartesian products, projections. Suggested reading: chapters 5 and 6 of [H].
Algebra: Products of groups, Modular arithmetic, quotient groups.
Week 6
4, 6 Sep 06		 Set theory: Relations, equivalence relations, functions, families, inverses of functions. Suggested reading: Chapters 7,8, 9 and 10 of [H].
Algebra: The first isomorphism theorem for groups, Modular arithmetic, Fermat's little theorem, the Chinese Remainder Theorem. Homework: Chapter 2: Section 7: problems 3 and 8. Section 8: problems 8, 9, 11. (Due 20 October.)
Week 7
4, 6 Oct 06		 Combinatorics: Stirling number of the second kind. Counting functions where the elements of the domain or the range are considered indistinguishable. Group actions: orbits, stabilizers, fixed points.
Set theory: Numbers, the Axiom of Infinity, Peano's axioms, the recursion theorem. Suggested reading: Chapters 11, 12 of [H].
Algebra: Fields, Vector spaces.
Week 8
16, 18, 20 Oct 06		 Combinatorics: Groups acting on sets: Burnside's theorem.
Set theory: Arithmetic. Addition and order. Suggested reading: Chapter 13 of [H]. Homework: at the end of chapter 8 (i) & (ii); at the end of chapter 9; chapter 12. (due 1 Nov 2006)
Algebra: Bases, dimension, direct sum in vector spaces. Suggested reading: pages 87--104 of [A].
Week 8
23, 25, 27 Oct 06		 Combinatorics: Polya's counting theorem.
Set theory: Arithmetic. Suggested reading: Chapter 13 of [H].
Algebra: Linear transformations, matrix of a linear transformation, linear transformations and change of basis. Linear operators, similar matrices, invariant subspaces, the characteristic polynomial, the Cayley-Hamilton theorem.
Week 9
30 Oct, 1,3 Nov 06		 Combinatorics: The power set of [n], chains, antichains, Sperner's theorem. System of distinct representatives, Hall's matching theorem. Dilworth's theorem.
Set theory: Order, partially ordered sets, predecessors, successors, least upper bound, greatest lower bound, totally ordered set. The axiom of choice. Suggested reading: Chapters 14, 15 of [H].
Algebra: Triangulable matrices, every linear operator on a finite dimensional complex vector space is triangulable, characteristic polynomials of triangulable matrices. Diagonalizable matrices, eigen vectors corresponding to distinct eigen values are linearly independent. Suggested reading: Chapter 6 of [HK].
Week 10
6, 8, 10 Nov 06		 Combinatorics: Symmetric chain decomposition, the Littlewood-Offord problem, Kleitman's theorem. Suggested reading: Chapter 4 of [B]. Homework (due 20 Nov 06).
Set theory: Zorn's lemma, well-ordering. Suggested reading: Chapter 16, 17 of [H].
Algebra: Characteristic polynomials of diagonalizable matrices, commuting matrices.
Week 10
15, 16, 17 Nov 06		 Set theory: Well-ordering, transfinite induction. Suggested reading: [H]
Combinatorics: Kruskal-Katona theorem.
Algebra: Direct sum and projection operators: [HK].
Week 10
21, 22, 24 Nov 06		 Combinatorics: Erdos-Ko-Rado theorem, Vapnik-Chervonenkis dimension, Sauer-Shelah-Perles theorem.
Set theory: Transfinite recursion theorem, similarity between posets, ordinal number. Suggested reading: [H]
Algebra: Cyclic decomposition theorem. Suggested reading: [HK].
Week 10
27, 29 Nov, 1 Dec 06		 Combinatorics: Kruskal-Katona theorem
Set theory: Ordinal numbers, limit ordinals, equivalence of sets, Bernstein-Schroder theorem. Suggested reading: [H]
Algebra: Jordan canonical form. Suggested reading: [HK].
Week 10
5, 6, 8 Dec 06		 Combinatorics: Isoperimetric inequalities, Harper's theorem. Suggested reading: Harper [H].
Set theory: Cantor's theorem, Canrdinality, Cardinal numbers, Konig's lemma. Suggested reading: [H]
Combinatorics: Turan's theorem, Ramsey's theorem. Suggested reading: [HK].