# 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 http://studentlife.osu.edu/csc/."

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: slds@osu.edu; 614-292-3307; 098 Baker Hall, 113 W. 12th Avenue."

Lectures:

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