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 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 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]. |