Discrete Mathematics (M.Tech CS, 2024-25)
Discrete Mathematics (M.Tech CS, 2024-25)
Instructors Arijit Ghosh
Status Completed
Teaching assistants Aranya Kumar Bal, Debarshi Chanda, Swarnalipa Dutta, and Buddha Dev Das
Description Introduction to Discrete Mathematics
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Mondays and Wednesdays from 11:15 am - 1:00 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
[W00] Douglas B. West, Introduction to Graph Theory, Second Edition, Pearson, 2000
[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
Statement of the well-ordering principle (WOP)
Proof of MP using WOP
Reading materials:
Topics covered in Lecture 2
Boolean functions
Propositional logic
First-order logic
Logical connectives and their properties
Relations
Different types of relations (reflexive, symmetric, antisymmetric, and transitive)
Composition of relations and inverse of relations
Equivalence relation and partitions
Reading materials:
Topics covered in Lecture 3
Partially ordered set (poset)
Linear/total ordering
Lexicographic/dictionary ordering
Examples of posets
Immediate predecessor of an element in a poset
Hasse diagram of a poset
Minimal and maximal elements of a poset
Existence of linear extensions of a finite poset
Embedding of poset
Embedding poset into its power set
Reading materials:
Chapters 1 and 2 from [MN08]
Topics covered in Lectures 4 and 5 (by Buddha Dev Das and Debarshi Chanda)
Introduction to graphs
Cycles, paths, and walks
Connected components
Representation of graphs: edge list, adjacency list, adjacency matrix, and incidence matrix
Connections between counting k-length walks and the adjacency matrix of a graph
Handshaking lemma
Degree sequence of a graph and Havel–Hakimi Theorem
Graph isomorphisms and a simple lower bound on counting isomorphisms
Reading materials:
Chapter 4 from [MN08]
Topics covered in Lecture 6
Chains and antichains
Statements of Dilworth's theorem and its dual
Erdős–Szekeres theorem and its proof using Dilworth's theorem
Proof of Dilworth's theorem
Reading materials:
Chapter 6 from [LW01]
Topics covered in Lecture 7
Dual of Dilworth's theorem and its proof
Sperner's theorem
LYM inequality
Statement of Erdős–Ko–Rado theorem
Reading materials:
Chapter 6 from [LW01]
Topics covered in Lecture 8
Proof of Erdős–Ko–Rado theorem
Types of asymptotic notations: big-O, big-Ω, Θ, little-o, and little-ω
Reading materials:
Topics covered in Lecture 9
Permutation and factorial
Binomial and multinomials coefficients
Binomial and multinomial theorems
Properties of binomial coefficients
Balls and bins
Distinct balls and distinct bins
Identical balls and distinct bins
Inclusion–exclusion principle (IEP) and its two proofs
Counting derangements using (IEP)
Estimating harmonic numbers, factorials, and binomial coefficients
Reading materials:
Chapter 3 from [MN08]
Topics covered in Lecture 10 (by Debarshi Chanda)
Definition of k-connected (edge and vertex) graphs
Characterization of vertex 2-connected graphs
Graph operations: edge addition/deletion, vertex deletion, cone vertex addition, and edge subdivision
Synthesis of vertex 2-connected graphs from a triangle using edge additions and edge subdivision
Reading materials:
Chapter 4 from [MN08]
Topics covered in Lecture 11 (by Buddha Dev Das)
Trees and their different characterizations
Spanning trees
Existence of a spanning tree in a connected graph
Algorithm for finding a spanning tree and its proof of correctness
Minimum spanning tree (MST) and its properties
Minimum spanning tree problem
Algorithms (Prim and Kruskal) for computing MST
Reading materials:
Chapter 5 (except Section 5.2) from [MN08]
Topics covered in Lecture 12
Convex sets, convex combination, and convex hulls
Affine dependence/independence, affine combination, and affine hulls
Different equivalent definitions of affine independence
Statement of the Carathéodory's Theorem about convex hulls
Radon Theorem about convex hulls
Reading materials:
Topics covered in Lecture 13
Helly Theorem for convex sets
Discussion on infinite Helly Theorem and compact sets
Carathéodory's Theorem about convex hulls
Introduction to Linear Programming (LP)
Optimal solutions, optimal value, and feasible solutions
LP in standard/equational form
Dual linear programs
Weak duality of LP
Reading materials:
Topics covered in Lecture 14
Statement of the Strong Duality Theorem for LP
Polynomial equivalence between finding a feasible solution and finding an optimal solution for LPs
Examples of LP
Introduction to Integer Linear Programming (ILP)
ILP formulation of vertex cover and independent set problems
Fractional vertex cover and independent set problems
Some discussions on optimal solutions of the fractional vertex cover problem
Reading materials:
Topics covered in Lecture 15
Introduction to matchings
ILP formulation of matching and vertex cover problems
Fractional matching and vertex cover problems, and their duality
2-factor approximation for vertex cover problem via fractional vertex cover problem
Statements of Hall's Theorem and König-Egeváry Theorem
Proof of Hall's Theorem
Reading materials:
Additional reading materials (optional):
Topics covered in Lecture 16
Applications of Hall's Theorem
System of distinct representatives (SDR)
Decomposition of regular bipartite graphs into disjoint matchings
Statement of Tutte's Theorem about characterization graphs containing a perfect matching
Proof of König-Egeváry Theorem using Hall's Theorem
Reading materials:
Chapter 5 from [S18]
Additional reading materials (optional):
Topics covered in Lecture 17 (by Aranya Kumar Bal)
Isomorphism of trees
Cayley's formula on the number of spanning trees
Reading materials:
Additional reading materials (optional):
Topics covered in Lecture 18 (by Buddha Dev Das)
Tutte's theorem characterizing graphs with perfect matchings
Berge formula characterizing the size of a maximum matching in a graph
Hamilton paths and cycles, and Hamiltonian graphs
Properties of Hamiltonian graphs
Dirac and Ore theorems on Hamiltonian cycles
Reading materials:
Sections 4.2 and 5.3 from [S18]
Topics covered in Lecture 19 (by Swarnalipa Dutta)
Introduction to generating functions
Combinatorial applications of polynomials
Calculation with power series
Integer partitions
Reading materials:
Sections 12.1, 12.2, 12.3 and 12.7 from [MN08]
Topics covered in Lecture 20 (by Swarnalipa Dutta)
Introduction to Recurrence relation
Substitution method for solving recurrences
Statement of Master Theorem (for recurrences)
Using master theorem for solving recurrences
Reading materials:
Sections 4.3, 4.4 and 4.5 from [CLRS22]
Topics covered in Lecture 21 (by Buddha Dev Das)
Proof of Master Theorem (continuous case)
More applications of the master theorem
Reading materials:
Section 4.6 from [CLRS22]
Additional reading materials:
Topics covered in Lecture 22
Introduction to Finite Probability Spaces
Random variables, expectations, and variance
Example of an interesting finite probability space:
Probability measure on the hypercube
Indicator random variables
Balancing vectors using independent random variables
Reading materials:
Chapter 10 from [MN08]
Topics covered in Lecture 23
Random permutation and its properties
Large independent set in graphs using random permutation
Bollobás set-pair inequality using random permutation
Reading materials:
Topics covered in Lecture 24
Markov and Chebyshev Inequalities
Properties of indicator random variables
Union bound theorem in probability theory using indicator random variable
Inclusion-Exclusion formula in probability theory using indicator random variable
Large cuts in graphs using first-moment method
Property B (two-coloring hypergraphs) using first-moment method
Reading materials:
Topics covered in Lecture 25
Weight of a random point in a Hamming cube using Chebyshev inequality
Alteration method:
Domination number upper bound in graphs
Turan's independent set lower bound in terms of average degree in graphs
Erdős lower bound on the existence of a sum-free subset
Probabilistic proof of the existence of a tournament with many Hamiltonian paths
Reading materials:
Topics covered in Lecture 26
Introduction to Random Graphs (Erdős–Rényi random graph model)
A probabilistic proof that most of the graphs are not bipartite using random graphs
Introduction to thresholds in random graphs
Threshold probability for the existence of a triangle in random graph
Introduction Ramsey Numbers
Erdős lower bound on Ramsey numbers using the probabilistic method
Reading materials:
Topics covered in Lecture 27
Introduction to graph drawing and planar graphs
Faces of planar graphs
Statement of Jordan Curve Theorem
Euler's formula for planar graphs
Bounding number of edges and faces in a planar graphs
Minors and subdivisions of graphs
Statements of
Kuratowski's Theorem
Wagner's Theorem for planar graphs
Hanani–Tutte Theorem (both weak and strong variants)
Reading materials: