As the course proceeds, we will keep updating this page to indicate what topics were covered in each lecture.
Module-1: Discrete Structures
Lecture-1 (13/03): Administrative and Logistical Matters pertaining to the course;Â Why Discrete Math?; Natural numbers and divisibility; Prime numbers; Theorem: There are infinitely many primes (proof: later); Twin Primes & the Twin Prime Conjecture
Lecture-2 (14/03): Goldbach's Conjecture; Sets & subsets; Venn Diagram; Disjoint Sets; Set operations: intersection, union & difference
Lecture-3 (16/03): The Universe (aka Universal Set) vs the Empty Set; Set operation: complement of a set (w. r. t. universe); Generalizing intersection & union to one or more sets; Symmetric Difference of two sets
Lecture-4 (17/03): (Binary Homogeneous) Relations (through many "natural" examples); Special Properties satisfied by certain relations: Reflexivity, Symmetry & Transitivity; Equivalence Relations
Lecture-5 (20/03): Partition of a Set; Equivalence Classes (w. r. t. an equivalence relation); Theorem: The equivalence classes of an equivalence relation R (defined on a set U) form a partition of U (proof: later); Special Property satisfied by certain (binary homogeneous) relations: Antisymmetry; Partial Orders and Total Orders; Comparability of elements (w. r. t. a partial order); Partially Ordered Sets (aka Posets) and Totally Ordered Sets (aka Chains)
Lecture-6 (21/03): Friends & Strangers at a Party, and its different equivalent formulations: social formulation, symmetric relations formulation, graph-theoretic formulation; (undirected) Graphs and their drawings; Finite versus infinite graphs; vertices, edges & adjacencies
Lecture-7 (23/03): Friends & Strangers at a Party (continued): two equivalent graph-theoretic formulations --- black-and-white version & colorful version (using complete graphs); generalizing the problem & brief discussion of Ramsey Theory; Definition of (binary homogeneous) relation using (set operation) Cartesian Product
Lecture-8 (24/03): Symmetric relations versus finite/infinite (undirected) Graphs; Graphs are more general --- loops & parallel/multiple edges; Beginning of Graph Theory: the seven bridges of Konigsberg and Euler's resolution; reformulating the problem as drawing a graph without lifting the chalk; degree of a vertex; Directed Graphs (aka Digraphs) to represent (binary homogeneous) relations (that may not be symmetric); vertices & arcs (aka directed edges); tail & head (of an arc); in-degree versus out-degree (of a vertex); Problem (TIY): Which graphs can be oriented (to obtain a directed graph) such that in-degree = out-degree (for each vertex)?
Lecture-9 (27/03): (binary homogeneous) Relations versus finite/infinite (directed) Graphs; Generalizing binary relations --- from homogeneous to heterogeneous; Generalizing relations --- from binary (aka 2-ary) to n-ary; Definition of n-ary relation using Cartesian Product; Arity of a Relation; brief discussion on n-ary relations & its connection with databases
Lecture-10 (30/03): Viewing functions as relations; Basic terminology related to functions: image (of an element), pre-image, domain, codomain, range/image (of a function); Some terminology related to graphs & digraphs: adjacency versus incidence
Lecture-11 (31/03): Representing graphs using matrices: adjacency versus incidence matrices; Walking on a graph: walks, trails & paths; Walking back to the same point: closed walks, closed trails & cycles; Stating Euler's Problem in terms of trails: Which graphs have an Eulerian trail (that is, a trail that uses every edge once)?
Lecture-12 (03/04): Walks (in a graph) and the Reachability Relation (on the vertex set of a graph)
Module-2: Logic & Proofs
Lecture-12 (03/04): Our first theorem with proof: the reachability relation is an equivalence relation (on the vertex set of any graph); Connected components of a graph; Connected versus disconnected graphs; Observing that it suffices to solve Euler's Problem for Connected Graphs
Lecture-13 (06/04): When are two graphs "the same"? ; Cardinality of Finite Sets; Bijections: one-to-one (aka injective) as well as onto (aka surjective) functions; Generalizing to all (especially, infinite) sets: two sets are equicardinal if there is a bijection between them; Equicardinality
Lecture-14 (10/04): When are two graphs "the same"? ; Boring answer: two graphs being equal; Exciting answer: two graphs being isomorphic; our second theorem with proof: isomorphism is an equivalence relation (on the set of all graphs); inverse of a bijection; composition of functions
Lecture-15 (11/04): Meaning of "graphs up to isomorphism"; subgraphs of a graph (labeled versus unlabeled); Cycle Graphs; Forests --- graphs that do not contain any cycle (as a subgraph); Trees (connected forests)
Lecture-16 (18/04): Regular graphs; Our first nontrivial proof of a theorem: if each vertex of a graph G has degree two or more then G has a cycle
Lecture-17 (20/04):
Lecture-18 (21/04):
Lecture-19 (24/04):
Lecture-20 (25/04):
Lecture-21 (27/04):
Lecture-22 (28/04):
Module-3: Counting
Module-4: Algebraic Structures