Math 39A (Fall 2019) - Introduction to combinatorics

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$.