200 Discrete Mathematics

Lecture notes

Prof. Arvind’s Lectures

Info

References:

• Combinatorics: Topics, Techniques, Algorithms, Peter Cameron (Main)
• Combinatorial Math, Douglass West
• 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.

• DMAT_L2 ✅
  • Cardinal numbers and arithmetic, comparing cardinalities, Schröder–Bernstein theorem
• DMAT_L3 ✅
  • Zorn’s lemma, properties of cardinal numbers
• DMAT_L4 ✅
  • Disjoint coverings, more properties of infinite cardinals
• DMAT_L5 ✅
  • Graph colorings: another application of Zorn’s lemma
• DMAT_L6 ✅
  • Picking objects, counting functions
• DMAT_L7 ✅
  • Proof of Cayley’s theorem on trees using Zorn’s lemma
• DMAT_L8 ✅
  • The twelve fold way, generating functions
• DMAT_L9 ✅
  • Catalan numbers
• DMAT_L10
  • Pigeon hole principle
• DMAT_L11
  • Ramsey theory
• DMAT_L12 ✅
  • PIE
• DMAT_L13
  • Edge Reconstruction Conjecture, Möbius inversion, Dilworth’s theorem
• DMAT_L14 ✅
  • Burnside’s Lemma
• DMAT_L15
  • Polya’s Enumeration Theorem

Prof. Sinhababu’s Lectures

Info

References:

• Misha Lavrov’s Math 3322 notes
• Mark Muldoon’s MATH20902 notes
• https://arxiv.org/pdf/2308.04512
• Introduction to Graph Theory (Douglass B. West)
• A First Course in Graph Theory (Gary Chartrand, Ping Zhang)
• Discrete Mathematics Elementary and Beyond (L. Lovász, J. Pelikán, K. Vesztergombi)
• Graphs, Networks and Algorithms (Dieter Jungnickel)
• An invitation to discrete mathematics (Matousek J., Nesetril J.)

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

• DMAT_L16 ✅
  • Induction trap, induction on number of vertices, bipartite graphs
• DMAT_L17 ✅
  • Growing trees
• DMAT_L18 ✅
  • Spanning trees, Matrix tree theorem
• DMAT_L19 ✅
  • Minimum spanning trees, matroids
• DMAT_L20 ✅
  • Connectivity, blocks, ear decomposition
• DMAT_L21
  • Matchings in bipartite graphs, Hall’s marriage theorem, Edmonds matrix
• DMAT_L22 ✅
  • Proof of Hall’s using M-alternating paths, some matroid stuff
• DMAT_L23 ✅
  • Probabilistic proof example 1, Konig’s theorem, Tutte’s theorem
• DMAT_L24 ✅
  • Probabilistic proof example 2, planar graphs
• DMAT_L25 ✅
  • Greedy coloring algorithm, chromatic polynomial, coloring planar graphs, tournaments
• DMAT_L26

---

Tutorials

DMAT_T1 ✅
DMAT_Tn1 (where $(n_k)$ is a subsequence of $2,3,\dots$)
DMAT_PS_Krutarth
DMAT_PS_Sunaina
DMAT_PS3b
DMAT_MatchingProblems

Assignments

DMAT_PS1
DMAT_AS1
DMAT_AS2
DMAT_AS3

Quizzes

DMAT_Q1

---

tut - maximum number of edges possible in a graph which does not have a triangle in it??