Graph theory & combinatorics I

This course is meant to introduce graduate students to a modern curriculum in combinatorics and graph theory. An emphasis is placed on covering the fundamentals of these subjects at a fast pace, emphasizing areas which are important for application. Many open problems and areas of current research will be pointed out along the way.
Topics covered will partly depend on the interests of the class, but will definitely include:

––techniques in enumerative combinatorics:
––graph theory: fundamentals, theory of planar graphs and topological graph theory, geometric graph theory
––Ramsey theory and extremal graph theory
––linear-algebra methods in combinatorics
––recent progress in discrete mathematics

I'll assign homework regularly, and occasionally devote some class time to letting people present solutions. I will also ask everyone to do a "class project". This could be a short expository note, a research project, or an oral presentation in class.

Office hours:

My office is MW540, in the Math Tower. I will hold regular office hours on Tuesdays at 3:00–3:55pm. I am also available to meet by appointment.

Academic Misconduct Statement:

“It is the responsibility of the Committee on Academic Misconduct to investigate or establish procedures for the investigation of all reported cases of student academic misconduct. The term “academic misconduct” includes all forms of student academic misconduct wherever committed; illustrated by, but not limited to, cases of plagiarism and dishonest practices in connection with examinations. Instructors shall report all instances of alleged academic misconduct to the committee (Faculty Rule 3335-5-48.7). For additional information, see the Code of Student Conduct at"

Disability Services Statement:

“Students with disabilities that have been certified by Student Life Disabilities Services (SLDS) will be appropriately accommodated and should inform the instructor as soon as possible of their needs. SLDS contact information:; 614-292-3307; 098 Baker Hall, 113 W. 12th Avenue."


8/22: Introductions and overview of course. Stirling's formula.
8/24: Proof of a weaker Stirling's formula. Some identities with binomial coefficients.
8/27: Introduction to generating functions. Deriving formulas for Fibonacci numbers and Catalan numbers.
8/29: Multiplying generating functions. Euler's formula for the generating function for partition function.
8/31: Exponential generating functions. Stirling numbers of the second kind.
9/5: Counting under symmetry (the orbit-counting theorem)
9/7: More counting under symmetry (cycle index polynomial)
9/10: HW #1 presentations
9/12: HW #1 presentations
9/14: Cayley's theorem: counting spanning trees
9/17: Basic graph theory notions (Diestel, Sections 1.1 and 1.2)
9/19: Paths and cycles (Diestel, Section 1.3)
9/21: Connectivity, trees and forests (Diestel, Sections 1.4 and 1.5)
9/24: Contractibility and minors (Diestel, Section 1.7)
9/26: Matchings in bipartite graphs (Diestel, Section 2.1)
9/28: Introduction to topological graph theory (Diestel, Section 4.1 & 4.2)
10/1: Euler's Formula v-e+f=2
10/3: Equivalence of Kuratowksi and Wagner's theorems (Section 4.4)
10/5: Proof of Kuratowski's and Wagner's theorems (Section 4.4)
10/8: Crossing number lemma
10/10: Kempe's proof of the 5-color theorem
10/15: HW #2 presentations
10/17: HW #2 presentations
10/19: Graphs with large girth and large chromatic number
10/22: Coloring infinite graphs: the de Bruijn–Erdos theorem
10/24: The chromatic number of the plane
10/26: Geometric graph theory: the unit distance problem, the distinct distance problem, etc.
10/29: Turán's theorem
10/31: Ramsey's theorem and upper bounds on Ramsey numbers
11/2: Lower bounds on Ramsey numbers
11/5: Linear algebra methods in combinatorics (introduction)
11/7: Intersection theorems with geometric consequences
11/9: Borsuk's conjecture
11/14: The Borsuk–Ulam theorem, The Ham Sandwich Theorem, and the Necklace Theorem
11/16: Kneser's conjecture
11/19: Introduction to convex polytopes. Balinski's theorem, Steinitz's theorem.
11/28: Proofs of Balinski's theorem and Steinitz's theorem
11/30: project presentations
12/3: HW #3 presentations
12/5: project presentations

Course Identifier: 
MATH 6501
MWF 3:00-3:55
Cockins Hall CH232