Discrete Mathematics - Lecture notes https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/main.pdf. D. Yogeshwaran Indian Statistical Institute, Bangalore (May 9, 2025) Contents 0 Disclaimers and Warnings 1 Introduction to Discrete Mathematics 1.1 Definition of graphs and some motivating examples 1.1.1 Popular examples of graphs 1.2 Some history and more motivation 1.3 Tentative Course overview : 1.3.1 Basic counting techniques 1.3.2 Flows, Matchings and Games on Graphs 1.3.3 *Graphs and matrices 1.3.4 Random graphs and probabilistic method. 2 Some basic notions 2.1 Some useful classes of graphs : 2.1.1 Some graph constructions 2.2 Some basic notions 2.3 Walks, Trails and Paths 2.4 ***Graphs and matrices : A little peek*** 2.5 Graphs as metric spaces 2.6 ***Some questions*** 3 Eulerian and Hamiltonian cycles 3.1 Euler’s theorem and König’s theorem on bi-partite graphs 3.2 Hamiltonian cycles 4 Spanning Trees 4.1 Trees and Cayley’s theorem 4.2 ***Spanning Trees and Forests*** 4.3 **Minimal spanning trees** 4.4 ***Kruskal and other algorithms *** 4.5 ***Some questions : Random spanning trees*** 5 Extremal Combinatorics 5.1 Erdös-Szekeres lemma and Dilworth’s theorem 5.2 Existence of complete subgraphs 5.3 Ramsey Theory and Probabilistic method 5.4 Applications to Number theory 5.5 ***Some other methods*** 5.6 Exercises 6 System of distinct representatives 6.1 Hall’s marriage theorem and SDR 6.2 Latin rectangles and decomposition of doubly stochastic matrices 6.3 Independent Sets and Covers: Konig, Egervary theorem 6.4 Gallai’s and Berge’s theorems 6.5 Tutte’s theorem 6.6 Exercises 6.7 ***Gale-Shapley Stable marriage/matching algorithm*** 6.8 ***Shannon rate of communication*** 6.9 ***Erdös-Gallai Theorem*** 6.10 ***Equivalent theorems to Hall’s matching theorem and more applications*** 7 Flows on networks, vertex and edge connectivity 7.1 Max-flow min-cut theorem 7.2 Vertex and edge connectivity 7.3 Menger’s theorem 7.4 Exercises 7.5 ***Some applications*** 8 Extremal Set theory 8.1 Chains and Antichains in Set systems 8.2 Intersecting and non-intersecting sets 8.3 Fisher’s inequality 8.4 Exercises 9 Designs 9.1 Examples and basic properties 9.2 Fisher’s inequality for designs 9.3 Finite linear spaces 9.4 Projective Planes 9.5 Blocking Set 9.6 Affine Planes 9.7 Hadamard Matrices 10 Recursions and generating functions 10.1 One-variable examples 10.2 Two-variable examples 10.3 Catalan numbers 10.4 Product Structures 11 ***Chromatic number and polynomials*** 11.1 Graph coloring 11.2 Chromatic Polynomials 11.3 Some bounds on chromatic number. 11.4 Edge-Chromatic number 11.5 ***Read’s conjecture and Matroids*** 12 ***Graphs and matrices*** 12.1 Incidence matrix and connectivity 12.2 Laplacian Matrix 12.3 Spanning trees and Laplacian 12.4 More properties of Adjacency Matrix 12.5 Exercises 12.6 Further reading 13 ***Planar graphs*** 13.1 Euler’s formula and Kuratowski’s theorem 13.2 Coloring of Planar graphs 13.3 ***Graph dual**** 13.4 Exercises 13.5 Further Reading Index References
![[Uncaptioned image]](isilogo.png)