Discrete Mathematics (M.Tech CS & CRS, 2023-24)
Instructors Arijit Ghosh
Status Completed
Description Introduction to Discrete Mathematics
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Tuesdays and Thursdays from 2:15 pm - 4: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
[D12] R. 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] C. L. 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] J. H. van Lint and R. 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] J. Matoušek and J. Nešetřil, An Invitation to Discrete Mathematics, Second Edition, Oxford University Press, 2008
[S22] A. Sheffer, Polynomial Methods and Incidence Theory, Cambridge University Press, 2022
[T12] A. Tucker, Applied Combinatorics, Wiley, 2012
[W00] D. B. West, Introduction to Graph Theory, Second Edition, Pearson, 2000
Lecture details
Topics covered in Lecture 1
Course details
Sets, multisets, and frequency of elements in multisets
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
Reading materials:
Topics covered in Lecture 2
Relations
Different types of relations (reflexive, symmetric, antisymmetric, and transitive)
Equivalence relation and partitions
Functions, truth tables, types of functions, and examples
Boolean functions
Propositional logic
Logical connectives and their properties
Reading materials:
Topics covered in Lecture 3
Predicates
Well-ordering principles and mathematical induction
Partially ordered sets (Posets)
Predecessors, chains, and antichains
Statement of Dilworth's theorem about posets
Erdős–Szekeres theorem and its proof using Dilworth's theorem
Reading materials:
Topics covered in Lecture 4
Different proof types:
Using case analysis
Proof by contradiction
Induction and strong induction
Disproving using counterexample
Types of asymptotic notations: big-O, big-Ω, little-o, and little-ω
Proof of Dilworth's Theorem using mathematical induction
Reading materials:
Topics covered in Lecture 5
Pigeonhole principle (PHP)
Proof of Erdős–Szekeres theorem using PHP
Dual of Dilworth's Theorem
LYM-inequality and Sperner's Theorem
Basics of counting: Permutations and combinations, factorials, binomial coefficients, and cyclic permutations
Recursive formula for binomial coefficients, Pascal's triangle, and Binomial theorem
Recursive formula for multinomial coefficients, and Multinomial theorem
Cyclic permutation
Statement of Erdős–Ko–Rado theorem
Reading materials:
Topics covered in Lecture 6
Estimates for harmonic function, functorial function, and binomial coefficients
Inclusion-exclusion principle
Three different proofs of the inclusion-exclusion principle
Applications of inclusion-exclusion principle:
Counting surjective functions
Counting k-partitions
Counting derangements
Introduction to Graph Theory
Graph homomorphisms, isomorphisms, and automorphism
Reading materials:
Chapters 3 and 4 from [MN08]
Topics covered in Lecture 7
Number of non-isomorphic graphs
Subgraphs and induced subgraphs
Definitions of matchings, independent set, dominating set, and vertex cover
2-factor approximation of vertex cover via maximal matching
Paths, cycles, walks, and tours
Connectivity and connected components
Adjacency matrix of a graph
Connections between counting k-length walks and the adjacency matrix of a graph
Reading materials:
Topics covered in Lecture 8
Degree sequence of a graph and Havel–Hakimi Theorem
Eulerian graph and its characterization
Triangle-free graphs and Mantel's Theorem
Reading materials:
Chapter 4 from [MN08]
Tutorial Session 1 (by Buddhadev Das and Arnab Ray)
Discussed solutions to Problem Set 1
Topics covered in Lecture 9 (by Buddhadev Das)
Definitions of Hamiltonian cycle, k-coloring problem, chromatic number, and clique number
Trees and their different characterizations
Planter tree isomorphism, rooted tree isomorphism, and tree isomorphism
Spanning trees
Algorithm for finding a spanning tree and its proof of correctness
Reading materials:
Additional reading materials (optional):
Chapter 3 from [W00]
Topics covered in Lecture 10 (by Buddhadev Das)
Existence of a spanning tree in a connected graph
Minimum spanning tree (MST) and its properties
Algorithms (Prim and Kruskal) for computing MST
Reading materials:
Chapter 5 from [MN08]
Additional reading materials (optional):
Section 3.1 in Chapter 3 from [W00]
Topics covered in Lecture 11
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 for a triangle using edge additions and edge subdivision
Properties of Hamiltonian Graphs
Reading materials:
Topics covered in Lecture 12
Recall Dilworth's Theorem about posets
Recall the connection between vertex covers and independent sets in graphs
Definitions of matchings and d-matchings in graphs
Recall the simple connection between the size of a maximum matching and the size of a minimum vertex cover in general graphs
Statements of Hall's Theorem and König-Egeváry Theorem, and their proofs via Dilworth's Theorem
Reading materials:
Section 3.1 in Chapter 3 from [W00]
Additional reading materials (optional):
Topics covered in Lecture 13 (by Swarnalipa Datta)
Generating functions
Reading materials:
Topics covered in Lecture 14 (by Buddhadev Das)
Recurrence relations
Reading materials:
Topics covered in Lecture 15
Introduction to Linear Programming (LP) and Integer Linear Programming (ILP)
Optimal solutions, optimal value, and feasible solutions
ILP formulation of vertex cover and LP formulation of fractional vertex cover
Statement of Weak and Strong Duality of LP
Polynomial equivalence between finding a feasible solution and finding an optimal solution for LPs
Convex sets, affine dependence/independence, convex combination, and convex hulls
Different equivalent definitions of affine independence
Reading materials:
Topics covered in Lecture 16
Radon Theorem about convex hulls
Helly Theorem for convex sets
Discussion on infinite Helly Theorem and compact sets
Carathéodory's Theorem about convex hulls
Reading materials:
Topics covered in Lecture 17
Introduction to Finite Probability Spaces
Random variables and expectations
Examples of interesting finite probability spaces:
Erdős–Rényi random graph model
Probability measure on the hypercube
Random permutation
Indicator random variables
Probabilistic proof of the existence of a tournament with many Hamiltonian paths
Reading materials:
Chapter 10 in [MN08]
Topics covered in Lecture 18
Recall the definition of independent random variables
Prove that most of the graphs are not bipartite using three different approaches
Existence of a large independent set using random permutations
Balancing vectors using independent random variables
Existence of a small dominating set in d-regular graphs using the alteration method
Reading materials:
Additional reading materials:
For a more detailed introduction to the alteration method read Chapter 3 in [AS08]
Topics covered in Lecture 19
Existence of large cuts in graphs
Proof of Erdos-Ko-Rado Theorem via Katona's Circle Method
Bounds on (k,l)-systems via Bollobás' Set Pairs Inequality
Introduction to graph drawing and planar graphs
Reading materials:
Additional reading materials:
To know more about Katona's Circle Method see the recent survey by Frankl [F21]
Topics covered in Lecture 20
Introduction to graph drawing and planar graphs
Faces of planar graphs
Bounding crossing number using Euler's inequality for planar graphs
Statement of Jordan Curve Theorem
Proving a complete graph on 5 or more vertices is not planar
Reading materials:
Chapter 6 in [MN08]
Topics covered in Lecture 21 (by Buddhadev Das)
Cycles in planar graphs
Euler's formula for planar graphs
Bounding number of edges and faces in a planar graphs
Platonic solids
Reading materials:
Chapter 6 in [MN08]
Topics covered in Lecture 22
Statement of Kuratowski's Theorem
Statement of Wagner's Theorem for planar graphs
Proof of Crossing Lemma using the probabilistic method
Introduction of incidence geometry
Bounding incidence using Kovari-Sos-Turan Theorem
Proof of Szemerédi–Trotter Theorem using crossing lemma
Reading materials:
Tutorial Session 2 (by Soumi Nandi)
Discussed solutions to Problem Set 5
Tutorial Session 3 (by Swarnalipa Datta)
Discussed solutions to Problem Sets and Problem Set 6