CRS Discrete Mathematics

CMI, Jan-Apr 2025, V Arvind & Amit Kumar Sinhababu

---

Lecture notes

Prof. Arvind’s Lectures

See Cameron (2001), West (2021), Enumerative combinatorics vol1, by Richard Stanley

Stuff to cover: Schroder-Bernstein Theorem, recurrence relations, generating functions, IEP, Mobius inversions, permutation groups, Polya’s enumeration theorem, and should time permit, infinitorial combinatorics, graph theory, finite fields.

• LEC DMAT 2 ✅
  • Cardinal numbers and arithmetic, comparing cardinalities, Schröder–Bernstein theorem
• LEC DMAT 3 ✅
  • Zorn’s lemma, properties of cardinal numbers
• LEC DMAT 4 ✅
  • Disjoint coverings, more properties of infinite cardinals
• LEC DMAT 5 ✅
  • Graph colorings: another application of Zorn’s lemma
• LEC DMAT 6 ✅
  • Picking objects, counting functions
• LEC DMAT 7 ✅
  • Proof of Cayley’s theorem on trees using Zorn’s lemma
• LEC DMAT 8 ✅
  • The twelve fold way, generating functions
• LEC DMAT 9 ✅
  • Catalan numbers
• LEC DMAT 10
  • Pigeon hole principle
• LEC DMAT 11
  • Ramsey theory
• LEC DMAT 12 ✅
  • PIE
• LEC DMAT 13
  • Edge Reconstruction Conjecture, Möbius inversion, Dilworth’s theorem
• LEC DMAT 14 ✅
  • Burnside’s Lemma
• LEC DMAT 15
  • Polya’s Enumeration Theorem

Prof. Sinhababu’s Lectures

See Lavrov (n.d.), Muldoon (2020), Grinberg (2024), West (2001), Zhao (2023), Lovász et al. (2003), Jungnickel (2013), Matoušek & Nešetřil (2009)

Stuff to cover: Graph theory, discrete probability, number theory, finite fields, applications to error correcting codes

• LEC DMAT 16 ✅
  • Induction trap, induction on number of vertices, bipartite graphs
• LEC DMAT 17 ✅
  • Growing trees
• LEC DMAT 18 ✅
  • Spanning trees, Matrix tree theorem
• LEC DMAT 19 ✅
  • Minimum spanning trees, matroids
• LEC DMAT 20 ✅
  • Connectivity, blocks, ear decomposition
• LEC DMAT 21
  • Matchings in bipartite graphs, Hall’s marriage theorem, Edmonds matrix
• LEC DMAT 22 ✅
  • Proof of Hall’s using M-alternating paths, some matroid stuff
• LEC DMAT 23 ✅
  • Probabilistic proof example 1, Konig’s theorem, Tutte’s theorem
• LEC DMAT 24 ✅
  • Probabilistic proof example 2, planar graphs
• LEC DMAT 25 ✅
  • Greedy coloring algorithm, chromatic polynomial, coloring planar graphs, tournaments
• LEC DMAT 26

---

Tutorials

TUT DMAT 1

Assignments

PS DMAT 1
AS DMAT 1
AS DMAT 2
AS DMAT 3

---

References

Cameron, P. J. (2001). Combinatorics: Topics, Techniques, Algorithms (Transferred to digital printing). Cambridge Univ. Press.

Grinberg, D. (2024). An Introduction to Graph Theory. arXiv. https://doi.org/10.48550/arXiv.2308.04512

Jungnickel, D. (2013). Graphs, Networks, and Algorithms (4. ed). Springer.

Lavrov, M. (n.d.). Math 3322: Graph Theory. Retrieved July 17, 2025, from https://facultyweb.kennesaw.edu/mlavrov/courses/3322-fall-2024.php

Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. Springer.

Matoušek, J., & Nešetřil, J. (2009). Invitation to Discrete Mathematics (2nd ed). Oxford University Press.

Muldoon, M. (2020). MATH20902: Discrete Mathematics. https://personalpages.manchester.ac.uk/staff/mark.muldoon/Teaching/DiscreteMaths/LectureNotes/AllNotes.pdf

West, D. B. (2001). Introduction to Graph Theory (2nd ed). Prentice Hall.

West, D. B. (2021). Combinatorial Mathematics. Cambridge University Press.

Zhao, Y. (2023). Graph Theory and Additive Combinatorics. Cambridge University Press. https://yufeizhao.com/gtacbook/gtacbook.pdf