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. 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	Uniqueness of the set of natural numbers constructed using the axiom of infinity; Peano axioms; derivation of the Peano axioms as theorems of ZF set theory; induction. Reference: [H], Chapter 12. Homework 2: PDF (due October 12).
13	Wednesday, 30 September 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra	Fixing a linearly independent set L and a spanning set S: 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; For subspaces U, W of V, dim(U) + dim(W) = dim(U + W) + dim(U ∩ W); coordinates with respect to an ordered basis: every vector has a unique coordinate representation in Fⁿ, compatible with vector-space arithmetic; change-of-basis matrices and their inverses; every invertible matrix is a change-of-basis matrix. Reference: [HK], Chapter 2.
—	Friday, 2 October —	No lecture.
14	Monday, 5 October 3:30 PM – 5:00 PM ECG Sudarshan Hall Set Theory	Definition by recursion and the recursion theorem; arithmetic of natural numbers; comparability of natural numbers and the induced total order; partial orders; equivalent sets; finite and infinite sets; the set of natural numbers ω is infinite. Reference: [H], Chapters 12–14.
15	Wednesday, 7 October 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra	Concrete example of change-of-basis computation, including matrix inversion by elementary row operations; row space and row rank of a matrix; row-equivalent matrices have the same row space; the nonzero rows of a row-reduced echelon matrix form a basis of its row space; statement and partial proof of the uniqueness theorem: for every subspace W ⊆ Fⁿ with dim(W) ≤ m, there exists a unique m × n row-reduced echelon matrix whose row space is W. Reference: [HK], Chapter 2.
16	Friday, 9 October 9:30 AM – 11:00 AM ECG Sudarshan Hall Combinatorics	Recurrence for derangements; linear algebraic method for solving linear recurrences; ballot problem and the reflection principle for deriving Catalan numbers; role of exponential generating functions in counting labelled objects. References: [vLW], Chapter 14; Jiří Matoušek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, Chapter 1 (for the linear algebraic method).
17	Monday, 12 October 3:30 PM – 5:00 PM ECG Sudarshan Hall Set Theory
18	Wednesday, 14 October 9:30 AM – 11:00 AM ECG Sudarshan Hall Linear Algebra
19	Friday, 16 October 9:30 AM – 11:00 AM ECG Sudarshan Hall Combinatorics
—	Monday, 19 October —	No lecture.