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