Discrete Mathematics — Monsoon 2026

Instructor: Mohit Garg

Intended audience: Beginning Int. PhD/PhD students in Theoretical Computer Science. All are welcome to attend.

Schedule

The course starts on Friday, August 28, 2026, and will end by mid-December 2026.

Monday:3:30 PM – 5:00 PM Wednesday:9:30 AM – 11:00 AM Friday:9:30 AM – 11:00 AM

Venue: IMSc, Chennai — ECG Sudarshan Hall or E326/E327.

Topics

The course will cover three broad areas:

Set Theory — Mondays
Linear Algebra — Wednesdays
Combinatorics — Fridays

Once a substantial part of one topic is completed, lectures on the other topics may occasionally spill over to its allotted day. This is not expected to happen during the first two months of the course.

A more detailed list of topics will be added as the course progresses.

Remark. This offering is modelled after Prof. Jaikumar Radhakrishnan's well-known and long-running Mathematical Structures course.

Prerequisites

Knowledge

The course will assume:

high-school-level counting;
some familiarity with graph theory;
some familiarity with matrices.

Mathematical maturity

Students should have taken at least a couple of mathematics courses at the undergraduate level. More importantly, they should come with an open mind and an interest in learning Combinatorics, Set Theory, and Linear Algebra.

References

The following books will be used as references. The course will not necessarily follow any one book closely.

[S] Richard P. Stanley, Enumerative Combinatorics, Volume 1.

[vLW] J. H. van Lint and R. M. Wilson, A Course in Combinatorics.

[B] Béla Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability.

[J] Stasys Jukna, Extremal Combinatorics: With Applications in Computer Science.

[H] Paul R. Halmos, Naive Set Theory.

[HK] Kenneth Hoffman and Ray Kunze, Linear Algebra.

Lectures

Lecture	Date, time, venue and topic	Details
1	Friday, 28 August 9:30 AM – 11:00 AM ECG Sudarshan Hall Combinatorics	Binomial coefficients; falling factorials; compositions and weak compositions; multiset coefficients; generating functions for binomial coefficients and multiset coefficients; permutations and their representations; cycle notation and standard form of cycle representation. Reference: [S], Chapter 1. Homework 1: PDF (due September 11).
2	Monday, 31 August 3:30 PM – 5:00 PM ECG Sudarshan Hall Set Theory	Axiom of extension; axiom of specification; subsets; axiom of pairing; unions and intersections; complements; power sets. Reference: [H], Chapters 1–5.
3	Wednesday, 2 September 9:30 AM – 11:00 AM E327 Linear Algebra	Fields; systems of linear equations; elementary row operations; row-equivalent matrices; row-reduced echelon form; augmented matrices and the condition for existence of a solution to an inhomogeneous system. Reference: [HK], Chapter 1.
—	Friday, 4 September —	No lecture.
4	Monday, 7 September 3:30 PM – 5:00 PM ECG Sudarshan Hall Set Theory	Ordered pairs; Cartesian products; relations; domain and range; equivalence relations; partitions. Reference: [H], Chapters 6–7.
5	Wednesday, 9 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra	Matrix multiplication; elementary matrices; matrix inverses; invertibility and its equivalent characterizations: row-equivalence to the identity matrix, representation as a product of elementary matrices, and solvability of systems of linear equations; vector spaces; linear independence; span. Reference: [HK], Chapters 1–2.
6	Friday, 11 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Combinatorics	Type of a permutation; number of permutations of a given type; counting functions; modelling indistinguishability using equivalence relations; Stirling numbers of the second kind. Reference: [S], Chapter 1.
—	Monday, 14 September —	No lecture.
7	Wednesday, 16 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra	Vector spaces and examples: spaces of n-tuples, matrices, functions, and polynomial functions; linear combinations and their geometric interpretation; subspaces, with examples and non-examples including Hermitian matrices; intersections of subspaces; span and its intrinsic and extrinsic characterizations; sums of subsets and sums of subspaces; linear dependence and independence; bases. Reference: [HK], Chapter 2.
8	Friday, 18 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Combinatorics	The twelvefold way; integer partitions of n into k parts; Bell numbers; Stirling numbers of the first kind, signed and unsigned; recurrence and generating function for the unsigned Stirling numbers of the first kind; proofs by induction and a combinatorial proof via a nondeterministic algorithm generating all permutations with k left-to-right maxima. Reference: [S], Chapter 1.
9	Monday, 21 September 3:30 PM – 5:00 PM E326 Set Theory	Functions; one-to-one, onto, and bijective functions; characteristic functions; families; Cartesian products of families of sets; composition of functions; inverses; construction of the natural numbers; axiom of infinity; construction of the set of all natural numbers. Reference: [H], Chapters 8–11.
10	Wednesday, 23 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra	Existence of a basis (using Zorn's lemma); finite-dimensional vector spaces; fixing a linearly independent set L and a spanning set S: \|L\| ≤ \|S\|; any two bases have the same cardinality; dimension; L extends to a basis; for a subspace W of V, dim(W) ≤ dim(V), with equality iff W = V; S contains a basis; L extends to a basis using vectors from S. Reference: [HK], Chapter 2.
11	Friday, 25 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Combinatorics	Generating function for the signed Stirling numbers of the first kind; Stirling numbers as change-of-basis coefficients between the monomial and falling-factorial bases, inverse change-of-basis matrices and the resulting Stirling inversion relations; ordinary generating functions; discrete convolution appearing in products of generating functions; counting unlabelled binary trees in which every node has either zero or two children using generating functions (Catalan numbers); exponential generating functions. References: [S], Chapter 1; [vLW], Chapter 14.
12	Monday, 28 September 3:30 PM – 5:00 PM ECG Sudarshan Hall Set Theory
13	Wednesday, 30 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra
—	Friday, 2 October —	No lecture.