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 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	Topic	Details
Lecture 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).
Lecture 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.
Lecture 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.
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.
Lecture 5	Wednesday, 9 September	9:30 AM – 11:00 AM	ECG Sudarshan Hall	Linear Algebra