Courses:

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



Lecture Notes



Lecture Notes

This section contains documents created from scanned original files, which are inaccessible to screen reader software. A "#" symbol is used to denote such documents.

These lecture notes were taken by Amanda Redlich, a student in the class, and were used with permission.


Lec #TopicsLecture Notes
1Course Introduction

Ramsey Theorem
(PDF)#
2Additive Number Theory

Theorems of Schur and Van der Waerden
(PDF)#
3Lower Bound in Schur's Theorem

Erdös-Szekeres Theorem (Two Proofs)

2-Colorability of Multigraphs

Intersection Conditions
(PDF)#
4More on Colorings

Greedy Algorithm

Height Functions Argument for 3-Colorings of a Rectangle

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

Erdös-Lovász Theorem

Brooks Theorem
(PDF)#
65-Color Theorem

Vizing's Theorem
(PDF)#
7Edge Coloring of Bipartite Graphs

Heawood Formula
(PDF)#
8Glauber Dynamics

The Diameter

Explicit Calculations

Bounds on Chromatic Number via the Number of Edges, and via the Independence Number
(PDF)#
9Chromatic Polynomial

NBC Theorem
(PDF)#
10Acyclic Orientations

Stanley's Theorem

Two Definitions of the Tutte Polynomial
(PDF)#
11More on Tutte Polynomial

Special Values

External and Internal Activities

Tutte's Theorem
(PDF)#
12Tutte Polynomial for a Cycle

Gessel's Formula for Tutte Polynomial of a Complete Graph
(PDF)#
13Crapo's Bijection

Medial Graph and Two Type of Cuts

Introduction to Knot Theory

Reidemeister Moves
(PDF)#
14Kauffman Bracket and Jones Polynomial(PDF)#
15Linear Algebra Methods

Oddtown Theorem

Fisher's Inequality

2-Distance Sets
(PDF)#
16Non-uniform Ray-Chaudhuri-Wilson Theorem

Frankl-Wilson Theorem
(PDF)#
17Borsuk Conjecture

Kahn-Kalai Theorem
(PDF)#
18Packing with Bipartite Graphs

Testing Matrix Multiplication
(PDF)#
19Hamiltonicity, Basic Results

Tutte's Counter Example

Length of the Longest Path in a Planar Graph
(PDF)#
20Grinberg's Formula

Lovász and Babai Conjectures for Vertex-transitive Graphs

Dirac's Theorem
(PDF)#
21Tutte's Theorem

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

Examples of Hamiltonian Cycles in Cayley Graphs of Sn
(PDF)#
22Hamiltonian Cayley Graphs of General Groups(PDF)#
23Menger Theorem

Gallai-Milgram Theorem
(PDF)#
24Dilworth Theorem

Hall's Marriage Theorem

Erdös-Szekeres Theorem
(PDF)#
25Sperner Theorem

Two Proofs of Mantel Theorem

Graham-Kleitman Theorem
(PDF)#
26Swell Colorings

Ward-Szabo Theorem

Affine Planes
(PDF)#
27Turán's Theorem

Asymptotic Analogues
(PDF)#
28Pattern Avoidance

The case of S3 and Catalan Numbers

Stanley-Wilf Conjecture
(PDF)#
29Permutation Patterns

Arratia Theorem

Furedi-Hajnal Conjecture
(PDF)#
30Proof by Marcus and Tardos of the Stanley-Wilf Conjecture(PDF)#
31Non-intersecting Path Principle

Gessel-Viennot Determinants

Binet-Cauchy Identity
32Convex Polyomino

Narayana Numbers

MacMahon Formula
(PDF)#
33Solid Partitions

MacMahon's Theorem

Hook-content Formula
(PDF)#
34Hook Length Formula(PDF)#
35Two Polytope Theorem(PDF)#
36Connection to RSK

Special Cases
(PDF)#
37Duality

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

Thurston's Theorem
(PDF)#

 








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