Discrete Mathematics (M.Tech CS, 2025-26)
Discrete Mathematics (M.Tech CS, 2025-26)
Instructors Arijit Ghosh
Status Ongoing
Teaching assistants Kuntal Das, Swarnalipa Datta, and Priyanka Jana
Description Introduction to Discrete Mathematics
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Mondays and Wednesdays from 11:10 am - 12:55 pm
Syllabus For details see the students' brochure for the M.Tech CS course
References
[AS08] Noga Alon and Joel Spencer, The Probabilistic Method, 3rd Edition, Wiley-Blackwell, 2008
[BHS80] Jon Louis Bentley, Dorothea Haken and James B. Saxe, A general method for solving divide-and-conquer recurrences, ACM SIGACT News, 12 (3): 36–44, 1980
[CLRS22] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Fourth Edition, The MIT Press, 2022
[D12] Reinhard Diestel, Graph Theory, 4th Edition, Graduate Texts in Mathematics, Springer, 2012
[F21] Peter Frankl, Old and new applications of Katona’s circle, European Journal of Combinatorics, 2021
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006
[L85] Chung Laung Liu, Elements of Discrete Mathematics, Second Edition, Tata McGraw Hill, 1985
[LLM10] Eric Lehman, Tom Leighton and Albert Meyer, Mathematics For Computer Science, MIT OpenCourseWare, 2010
[LW01] Jacobus H. van Lint and Richard M. Wilson, A Course in Combinatorics, Second Edition, Cambridge University Press, 2001
[M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002
[MG07] Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007
[MN08] Jiří Matoušek and J. Nešetřil, An Invitation to Discrete Mathematics, Second Edition, Oxford University Press, 2008
[S18] Benny Sudakov, Graph Theory, Lecture Notes, ETH Zurich, 2018
[S22] Adam Sheffer, Polynomial Methods and Incidence Theory, Cambridge University Press, 2022
[T12] Alan Tucker, Applied Combinatorics, Wiley, 2012
[W20] Douglas B. West, Combinatorial Mathematics, Cambridge University Press, 2020
[W00] Douglas B. West, Introduction to Graph Theory, Second Edition, Pearson, 2000
[Z23] Yufei Zhao, Graph Theory and Additive Combinatorics, Cambridge University Press, 2023
[Z22] Yufei Zhao, Probabilistic Methods in Combinatorics (Lecture Notes), Fall 2022, MIT, 2022
Lecture details
Topics covered in Lecture 1
Course details
Set operations and their properties
Connection with subsets of a set and points in the hypercube (or Hamming cube)
Interpreting set operations with operations on the hypercube
Examples of some proof techniques:
Using case analysis
Mathematical induction (MP)
Pigeonhole principle (PHP)
Proof by contradiction
Disproving mathematical statements using counterexamples
Statement of the well-ordering principle (WOP)
Proof of MP using WOP
Relations
Different types of relations (reflexive, symmetric, antisymmetric, and transitive)
Equivalence relations and partitions
Partially ordered set (poset)
Linear/total ordering
Lexicographic/dictionary ordering
Examples of posets
Study materials:
Chapter 1 from [L85]
Chapters 2 and 3 from [LLM10]
Chapters 1 and 2 from [MN08]
Sourav Chakraborty's lecture videos (video-a and video-b) and slides (slides) on sets, relations, and functions
Sourav Chakraborty's lecture videos and slides on proof techniques
Nice write-up on mathematical induction (link)
Supplementary study materials on propositional and predicate logic
Chapter 1 from [LLM10]
Sourav Chakraborty's lecture video and slides
Topics covered in Lecture 2
Immediate predecessor of an element in a poset, and its existence in a finite poset
Hasse diagram of a poset
Minimal and maximal elements of a poset, and their existence in a finite poset
Existence of linear extensions of a finite poset
Embedding a poset into another poset
Embedding a poset into its power set
Chains and antichains in a poset
Statement of Dilworth's theorem, and Tverberg's proof of Dilworth's theorem
Study materials:
Topics covered in Lecture 3
Dual of Dilworth's theorem and its proof
In any finite poset, the longest chain length times the largest antichain length is at least the size of the set
Erdős–Szekeres theorem and its proof using Dilworth's theorem
Sperner's theorem
Lubell–Yamamoto–Meshalkin (LYM) inequality (also sometimes called YBLM inequality)
Every finite poset is an intersection of finitely many of its linear extensions
Study materials:
Topics covered in Lecture 4
Revisit the fact that every finite poset is an extension of finitely many linear extensions
Erdős–Ko–Rado theorem and Katona's circle method
LYM-type inequality in the Erdős–Ko–Rado theorem setting
Recalled:
Permutation and factorial
Binomial and multinomials coefficients
Binomial and multinomial theorems
Introduction to balls and bins framework
Distinct balls and distinct bins
Identical balls and distinct bins
Study materials:
Additional reading material (optional):
Frankl's recent paper on Katona's circle method
Topics covered in Lecture 5
Types of asymptotic notations: big-O, big-Ω, Θ, little-o, and little-ω
Falling factorial and rising factorial
Counting techniques and their applications:
Sum principle
Product principle
Principle of counting two ways
Bijection principle
Pigeonhole principle (PHP)
Polynomial method
Brief introduction to Polynomial Identity Testing
Alon-Furedi's hyperplane covering and polynomial method
Study materials:
Additional reading materials:
Topics covered in Lecture 6
Combinatorial proofs of the following theorem using polynomial method
Binomial theorem
Multinomial theorem
Binomial/multinomial theorem for falling factorial
Lattice, and lattice paths
Delannoy path and Delannoy numbers
Lattice balls, and counting the number of points in a lattice ball
Study materials:
Topics covered in Lecture 7
Inclusion–exclusion principle (IEP) and its three proofs
Counting derangements and surjective functions using IEP
Balls and bins framework when balls are distinct and bins are identical
Study materials:
Topics covered in Lecture 8
Revisiting the inclusion–exclusion principle (IEP)
Applications of IEP:
Euler's totient function
Counting the number of multisets with limited usage
Evaluating sums
Study materials:
Chapter 1 from [W20]
Topics covered in Lecture 9 (by Kuntal Das)
Discussed solutions to Problem Sets 1 and 2
Topics covered in Lecture 10
Convex sets, convex combinations, and convex hulls
Affine dependence/independence, affine combination, and affine hulls
Different equivalent definitions of affine independence
Relation between convex combinations and convex hulls
Radon's theorem about convex hulls
Helly's theorem for convex sets
Study materials:
Topics covered in Lecture 11 (by Kuntal Das)
Introduction to recurrence relations
Recurrence relations and "divide and conquer" algorithm paradigm
Technical subtleties in solving recurrences: handling floors/ceilings, boundary conditions, small inputs, and asymptotic bounds
Substitution method for solving recurrences
Recursion-tree method for solving recurrences
Master theorem for recurrences (statement only)
Applications of the master theorem for solving recurrences
Solving linear recurrences via characteristic polynomials: Fibonacci example
Study materials:
(Optional) Additional study materials:
Topics covered in Lecture 12
Recalled the proof of Helly's theorem
Discussion on the infinite version of Helly's theorem
Center point of a point set
Rado's center point theorem
Carathéodory's theorem about convex hulls
Study materials:
Topics covered in Lecture 13 (by Buddha Dev Das)
Recall the definition of recurrence
Types of recurrences:
Linear recurrence
Order/degree k recurrence
Homogeneous and inhomogeneous recurrence
Some standard examples of recurrences
Characteristic equation method for solving recurrences
Study materials:
Topics covered in Lecture 14 (by Buddha Dev Das)
Generating function method for solving recurrences
Introduction to graph theory
Representation of graphs: adjacency matrix, adjacency list, incidence matrix, and edge list
Handshaking lemma
Study materials:
Topics covered in Lecture 15 (by Buddha Dev Das)
Introduction to trees, paths, cycles, vertex cover, and independent sets
Connected graphs and components of a graph
Tree characterizations
Spanning tree of a graph
Algorithms for finding the spanning tree of a graph (Prim's and Kruskal with unit edge weight)
Minimum spanning tree (MST)
Algorithms for computing MST: Prim's and Kruskal's algorithms
Study materials:
Chapters 4 and 5 from [MN08]