Math 39A (Fall 2019) - Introduction to combinatorics

Undergraduate, Brandeis University, 2019

Course Information

  • Instructor: Lam Pham
  • Office: Goldsmith 312
  • E-mail address: lampham@brandeis.edu
  • Office hours (current): Mondays (12-1pm), Wednesdays (6.30-7.30pm), and Thursday (1-2pm) in Goldsmith 312
  • Grader: Anurag Rao (anrg@brandeis.edu)
  • Grader’s office hours: Tuesdays (4-5pm) - You may ask questions about homework grades here

Lectures

  • Location: Goldsmith 226
  • Time: Mondays, Wednesdays, 5-6:20pm

Reference text

Alan Tucker, Applied Combinatorics (6th Edition)

Prerequisites

Linear algebra and calculus.

Grading scheme

  • Homeworks: 20%;
  • Midterm exam: 35%;
  • Final exam: 45%.

In the event that you perform poorly on the midterm exam, and perform much better on the final exam, I will adjust the weight of the midterm to 25% and the final exam to 55%.

Exam schedule

  • Midterm: Time and location TBA
  • Final exam: determined by registrar

Topics

enumeration, counting, correspondences, recursion and differential equations, induction, algebraic structures, networks, algorithms, spectral graph theory

Homeworks

  • Homework 1, due 09/09/2019

Schedule and Notes

  • Lecture 01 (Aug. 28). We defined graphs, subgraphs, morphisms, isomorphisms, the complement of a graph, and saw examples. We proved that $\sum_{x\in V(G)}\mathrm{deg}(x)=2\lvert E(G)\rvert$, and that $\lvert\lbrace x\in V(G)\,\mid\, \mathrm{deg}(x)~\mathrm{is}~\mathrm{odd}\rbrace\rvert$ is even. We defined paths, walks, trails, circuits and cycles, and proved that in any graph with minimal degree $\delta(G)\geq 2$, there exists a cycle of length $\geq \delta(G)+1$.