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 highschool 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.
Week 1 23, 25 Aug 


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 1931 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 inclusionexclusion principle. Counting derangements. Suggested reading: Combinatorial Mathematics by H Ryser (Chapter 2). Lecturer: Pranab Sen. 

Week 3 4, 6, 8 Sep 
Combinatorics: Applications of inclusionexclusion: formula for Euler's totient function, Ryser's formula, determinant versus permanent function, Ryser's depththree 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: 3859 from [A]. 

Week 5 18, 20, 22 Sep 03 
Combinatorics: Permutations, cycle representation,
Stirling numbers of the first kind. Suggested reading:
pages 120 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 5969 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 87104 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 CayleyHamilton 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 LittlewoodOfford problem,
Kleitman's theorem. Suggested reading:
Chapter 4 of [B].
Homework (due 20 Nov 06).
Set theory: Zorn's lemma, wellordering. Suggested reading: Chapter 16, 17 of [H]. Algebra: Characteristic polynomials of diagonalizable matrices, commuting matrices. 

Week 10 15, 16, 17 Nov 06 
Set theory: Wellordering, transfinite induction. Suggested
reading: [H]
Combinatorics: KruskalKatona theorem. Algebra: Direct sum and projection operators: [HK]. 

Week 10 21, 22, 24 Nov 06 
Combinatorics: ErdosKoRado theorem,
VapnikChervonenkis dimension, SauerShelahPerles 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: KruskalKatona theorem
Set theory: Ordinal numbers, limit ordinals, equivalence of sets, BernsteinSchroder 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]. 