**Lectures:** Tuesday and Thursday 8:30am-10:00am
1230 Undergraduate Sciences Building

**Instructor:** Thomas Lam,
tfylam@umich.edu

**Office Hours:** TBA.

**Prerequisites:**

The most important prerequisite is mathematical maturity. You have to be comfortable with reading and writing proofs. In particular, proofs by contradiction and proofs by induction will be common and used without further explanation. Some experience with abstract algebra, such as group theory or proof-based linear algebra
is assumed. Past experience with combinatorics is also helpful.

**Grading:**
There will be problem sets roughly every one or two weeks. There will be one midterm. There will be no final exam.

Grades will be calculated from: Midterm (25%) and Problem Sets (75%).

**Midterm:**
I plan to hold the midterm on Thursday Oct 13 during class time.
** Information about the midterm will be posted on Canvas. **

**Textbook (Required):**
A course in combinatorics, J. H. van Lint and R. M. Wilson, 2nd edition.

The textbook is available electronically through the library.

We shall also use An introduction to Hyperplane Arrangements by Richard Stanley.

**Homework policy:**
Homework must be written in LaTeX and will be collected using gradescope. Late homeworks, according to gradescope timestamp, are penalized 10% per hour. (To clarify: *The maximum possible achievable score on the homework is reduced by 10% per hour, rounded up to the nearest hour.*)
There are no makeups for missed or late homework; the lowest homework score will be dropped in the final calculation.

You are allowed to work with other students on the problem sets, but you must include the names of those you worked with when you hand in your homework. You are not allowed to post homework problems on question websites such as mathoverflow or stackexchange. If you use a solution you find in a book, online, or elsewhere, you must acknowledge the source.

**Academic Misconduct**
The University of Michigan community functions best when its members treat one another with honesty, fairness, respect, and trust. The college promotes the assumption of personal responsibility and integrity, and prohibits all forms of academic dishonesty and misconduct. All cases of academic misconduct will be referred to the LSA Office of the Assistant Dean for Undergraduate Education. Being found responsible for academic misconduct will usually result in a grade sanction, in addition to any sanction from the college. For more information, including examples of behaviors that are considered academic misconduct and potential sanctions, please see lsa.umich.edu/lsa/academics/academic-integrity.html.

**COVID-19:**

LSA is committed to delivering our mission while aiming to protect the health and safety of the community, which includes minimizing the spread of COVID-19.
Please see this link for the current university COVID-19 policies with respect to face masks, vaccines, etc.

*I ask that students who come to my office to please wear a face mask.
*

**Disabilities:**
The University of Michigan recognizes disability as an integral part of diversity and is committed to creating an inclusive and equitable educational environment for students with disabilities.
Students who are experiencing a disability-related barrier should contact Services for Students with Disabilities https://ssd.umich.edu/; 734-763-3000 or ssdoffice@umich.edu). For students who are connected with SSD, accommodation requests can be made in Accommodate. If you have any questions or concerns please contact your SSD Coordinator or visit SSDâ€™s Current Student webpage. SSD considers aspects of the course design, course learning objects and the individual academic and course barriers experienced by the student. Further conversation with SSD, instructors, and the student may be warranted to ensure an accessible course experience.

**Course Recordings:**
I plan to have course lectures audio/video recorded and made available to other students in this course. Unfortunately, I have little control over the quality of these recordings.
Please be aware that as part of your participation in this course, you may be recorded. If you have concerns about this, please let me know as soon as possible.

**Syllabus (subject to change):**

Graph Theory:

Turan's theorem, Ramsey's theorem, chromatic number and polynomial, planar graphs

Geometric Combinatorics:

posets, matroids, hyperplane arrangements

**Tentative list of lectures:**

- Aug 30: Turan's theorem [Chapter 4] wiki entry
- Sep 1: Turan's theorem II
- Sep 6: Brook's theorem [Chapter 3] wiki entry
- Sep 8: Ramsey's theorem [Chapter 3] wiki entry
- Sep 13: Van der Waerden's theorem wiki entry
- Sep 15: Planar graphs [Chapter 33] wiki entry (planar graphs)
- Sep 20: Euler's formula, chromatic polynomial [Chapter 33] wiki entry (Euler's formula) wiki entry (chromatic poly)
- Sep 22: Five-color theorem, Acyclic orientations wiki entry
- Sep 27: Hall's marriage theorem [Chapter 5] wiki entry
- Sep 29: Konig's theorem, Birkhoff's theorem [Chapter 5] wiki entry
- Oct 4: Latin squares [Chapter 17] wiki entry
- Oct 6: Max flow-min cut theorem [Chapter 7] wiki entry
- Oct 11: Dinitz conjecture [Chapter 17] wiki entry
- Oct 13: midterm
- Oct 18:
**Fall break** - Oct 20: Finite projective planes [Chapter 23] wiki entry
- Oct 25: Finite projective planes II
- Oct 27: Combinatorial geometries [Chapter 23]
- Nov 1: Geometric Lattices [Chapter 23] [Sta, Lec 3] wiki entry
- Nov 3: Geometric Lattices II
- Nov 8: Matroids [Sta, Lec 3] wiki entry
- Nov 10: Hyperplane arrangements [Sta, Lec 1] wiki entry
- Nov 15: Characteristic polynomial I [Sta, Lec 1]
- Nov 17: Mobius functions wiki entry
- Nov 22: Graphical arrangements [Sta, Lec 2]
- Nov 24:
**Thanksgiving** - Nov 29: Characteristic polynomial II
- Dec 1: Broken circuit complex [Sta, Lec 4]
- Dec 6: More on matroids
- Dec 8: Last lecture