Courses:

Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics >> Content Detail



Calendar / Schedule



Calendar

Lec #TopicsKEY DATES
1Course Introduction

Ramsey Theorem
2Additive Number Theory

Theorems of Schur and Van der Waerden
3Lower Bound in Schur's Theorem

Erdös-Szekeres Theorem (Two Proofs)

2-Colorability of Multigraphs

Intersection Conditions
4More on Colorings

Greedy Algorithm

Height Functions Argument for 3-Colorings of a Rectangle

Erdös Theorem
5More on Colorings (cont.)

Erdös-Lovász Theorem

Brooks Theorem
65-Color Theorem

Vizing's Theorem
Problem set 1 due
7Edge Coloring of Bipartite Graphs

Heawood Formula
8Glauber Dynamics

The Diameter

Explicit Calculations

Bounds on Chromatic Number via the Number of Edges, and via the Independence Number
9Chromatic Polynomial

NBC Theorem
Problem set 2 due
10Acyclic Orientations

Stanley's Theorem

Two Definitions of the Tutte Polynomial
11More on Tutte Polynomial

Special Values

External and Internal Activities

Tutte's Theorem
12Tutte Polynomial for a Cycle

Gessel's Formula for Tutte Polynomial of a Complete Graph
13Crapo's Bijection

Medial Graph and Two Type of Cuts

Introduction to Knot Theory

Reidemeister Moves
14Kauffman Bracket and Jones PolynomialProblem set 3 due
15Linear Algebra Methods

Oddtown Theorem

Fisher's Inequality

2-Distance Sets
16Non-uniform Ray-Chaudhuri-Wilson Theorem

Frankl-Wilson Theorem
17Borsuk Conjecture

Kahn-Kalai Theorem
Problem set 4 due
18Packing with Bipartite Graphs

Testing Matrix Multiplication
19Hamiltonicity, Basic Results

Tutte's Counter Example

Length of the Longest Path in a Planar Graph
20Grinberg's Formula

Lovász and Babai Conjectures for Vertex-transitive Graphs

Dirac's Theorem
21Tutte's Theorem

Every Cubic Graph Contains Either no HC, or At Least Three

Examples of Hamiltonian Cycles in Cayley Graphs of Sn
22Hamiltonian Cayley Graphs of General Groups
23Menger Theorem

Gallai-Milgram Theorem
Problem set 5 due
24Dilworth Theorem

Hall's Marriage Theorem

Erdös-Szekeres Theorem
25Sperner Theorem

Two Proofs of Mantel Theorem

Graham-Kleitman Theorem
26Swell Colorings

Ward-Szabo Theorem

Affine Planes
Problem set 6 due
27Turán's Theorem

Asymptotic Analogues
28Pattern Avoidance

The case of S3 and Catalan Numbers

Stanley-Wilf Conjecture
29Permutation Patterns

Arratia Theorem

Furedi-Hajnal Conjecture
30Proof by Marcus and Tardos of the Stanley-Wilf ConjectureProblem set 7 due
31Non-intersecting Path Principle

Gessel-Viennot Determinants

Binet-Cauchy Identity
32Convex Polyomino

Narayana Numbers

MacMahon Formula
33Solid Partitions

MacMahon's Theorem

Hook-content Formula
34Hook Length Formula
35Two Polytope Theorem
36Connection to RSK

Special Cases
Problem set 8 due
37Duality

Number of Involutions in Sn
38Direct Bijective Proof of the Hook Length Formula
39Introduction to Tilings

Thurston's Theorem

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.