Autumn 2008: 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.
[C] Combinatorics by Peter J Cameron. Cambridge. [J] Extremal Combinatorics by Stasys Jukna. Springer. [AS] The Probabilistic Method by N Alon and and J Spencer. Wiley.

Outline

The goal of this course is to introduce first year students in the School of Technology and Computer Science to mathematical structures and the types of reasoning that one might encounter in Computer Science research papers. 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 [H]. The idea is to formally review the 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 [A] 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, Turan'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, students will be expected complete some proofs themselves. There will be regular homework assignments.

You can choose from the following list. [The first person who sends me email claiming the paper, gets to present that paper! Let us try to schedule the talks for 15 January 2009.] 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. Inclusion-exclusion: exact and approximate by J. Kahn, N. Linial and A. Samorodnitsky. [PS]
  3. Perfect matchings in balanced hypergraphs by Michele Conforti, Gerard Cornuejols, Ajai Kapoor and Kristina Vuscaronkovic. [PDF]
  4. Frobenius Theorem on the space of operators that commute with a given linear operator. [PDF]. Pages 204-207 of Jacobson's Algebra I. The argument there is stated in the language of PID's but easy to specialize to the case of linear operators.
  5. Applications of Konig's lemma. Pages 311-317 of Cameron's Combinatorics book. [PDF]
  6. The ballot problem. From Feller's probability book.
  7. Solution to the Problème de ménages: Doyle's solution.
  8. The Miller-Rabin randomized algorithm for primality testing from Kozen's algorithms book.
  9. Orthogonal antichains: pages 32-36, 40--43 of [An] [PDF]

Lectures

Week 1
4, 6, 8 Aug 08
Combinatorics: Basic counting, sets, multisets, Suggested reading: pages 1--20 of [S].
Set Theory: Basic axioms. Suggested reading pages 1--11 of [H]
Algebra: Matrices, row-echelon form. Suggested reading: pages 1-35 of [A]; try the exercises.
Week 2
11, 13 Aug 08
Combinatorics: Permutations, cycle structure, standard form, the Stirling numbers of the first kind. Homework (due 25 Aug 08): [PDF].
Set Theory: Unions, intersections, ordered pairs. Suggested reading: pages 12-25 of [H]. Homework (due 3 Sep 08): attempt the exercises on page 10, page 16, page 25 and the `non-trivial' exercise on page 23 of [H].
Week 3
18, 20, 22 Aug 08
Combinatorics: Cycle structure, inversions.
Set Theory: Cartesian products, relations, functions. Suggested reading: pages 16--33 of [H].
Algebra: Determinants. Homework (due 12 Sep 08): [PDF].
Week 4
25, 27, 29 Aug 08
Combinatorics: permutations and trees, counting functions.
Set Theory: families, inverses, compositions, natural numbers. Suggested reading: pages 34--45 of [H].
Algebra: Permutation matrices, Cramer's rule, Groups. Suggested reading Chapter 2 of [A].
Week 5
1, 5 Sep 08
Combinatorics: Inclusion-exclusion.
Set Theory: Holiday Suggested reading: pages 34--45 of [H].
Algebra: Subgroups, homomorphisms, isomorphism, kernel, image.
Week 6
8, 10, 12 Sep 08
Combinatorics: Inclusion-exclusion formula, graph reconstruction, derangements. Homework (due 25 Sep 08): [PDF].
Set Theory: Natural Numbers, Peano's axioms. Suggested reading: pages 46--49 of [H].
Algebra: Modular arithmetic, cosets, quotient groups, normal subgroups.
Week 7
17, 19 Sep 08
Combinatorics: Mobius inversion (Amitava Bhattacharya was the guest lecturer while Jaikumar was away).
Week 8
22, 24, 26 Sep 08
Set theory: Recursion theorem. Suggested reading: Homework (due 22 Oct 08): Bottom of page 49, bottom of 53 of [H]. Suggested reading: pages 51--53 of [H].
Algebra: Products of groups, Quotient groups, first isomorphism theorem.
Week 9
29 Sep 08
1, 3 Oct 08
Combinatorics: Hall's theorem. Homework (due 3 November 08): [PDF]
Set Theory: Arithmetic, order in natural numbers. Suggested reading: 54--57 of [H].
Algebra: Chinese remainder theorem. Homework (assigned 1 Nov 08, due 14 Nov 08): problem 11 on page 70, problems 12 and 14 on page 71, problem 8 on page 75, problem 6 page 76, problem 4 on page 77 (all from [A]).
Week 10
6, 8, 10 Oct 08
Combinatorics: Homework, Linear codes.
Set Theory: Axiom of choice. Suggested reading: 59--61 of [H].
Algebra: Vector Spaces. Suggested reading: pages 78--103 of [A].
Week 11
13 Sep 08
Combinatorics: Group actions, orbits, the orbit counting lemma.
Week 12
20, 22 Oct 08
Combinatorics: Counting objects under symmetry, cycle index polynomial.
Set theory: Zorn's lemma. Suggested reading pages 62--65 of [H].
Week 13
3, 5, 7 Nov 08
Combinatorics:
Set theory:
Algebra