Textbook
Miklos Bona,
A Walk through Combinatorics:
An Introduction to Enumeration and Graph
Theory 3rd edition,
World Scientific Publishing Company.
Now, August, September, October, November, December and January.
Monday, August 26
Game of parts.
Induction and strong inductions.
Proof without induction.
More examples of induction.
12 + 22 + ... + n2 = n * (n+1) * (2n+1)/6.
Wednesday, August 28
Proof by induction that all horses have the same color.
Graphs. Planar graphs.
Counting vertices, edges and regions: f0, f1 and f2.
Euler's formula: f0 - f1 + f2 = 2.
(Historical note about
Descartes
and
Sweden.)
Three proofs:
(1) Removing edges... (not quite a solid proof).
(2) The cutting tree and the dual tree.
(3) Using positrons and electrons.
Friday, August 30
Platonic solids.
Regular tilings of the plane.
The 4-dimensional cube.
Monday, September 2
LABOR DAY!!!!!!!
(Do not show up to class!)
Wednesday, September 4
More 4-dimensional cube.
K5 is not planar.
K3,3 is not planar.
Kuratowski's theorem.
The four color theorem.
Every planar graph has a vertex of degree less than or equal to 5.
Friday, September 6
Proofs should yield insight.
Theorem: Color each edge of K6 red or blue.
Then there is a monochromatic triangle.
A bad proof 215 = 32768 cases versus a good proof.
The six color theorem. (Easy)
The five color theorem. (Slightly harder)
The four color theorem. (Homework)
Monday, September 9
Graphs embedded on other surfaces.
Drawing K7 on a torus.
See the Heawood conjecture,
proved by Ringel and Young.
The chromatic function.
The chromatic is polynomial and hence it is called the chromatic polynomial.
Wednesday, September 11
The chromatic polynomial of a tree:
t (t-1)n-1.
The chromatic polynomial of disjoint union.
The chromatic polynomial of an n-cycle:
(t-1)n + (-1)n (t-1).
Stanley's
evaluation of the chormatic polynomial at -1.
Acyclic orientations.
Tutte's near root at
golden ratio square for planar triangulations of the plane.
Friday, September 13
Deletion--contraction recursion for the number acyclic orientations.
Proof of Stanley's evalutation of the chromatix polynomial at -1.
(Now you know the meaning of coloring with -1 colors!)
The plus game. Please find a winning strategy.
Cayley's formula for the number of trees: nn-2.
Monday, September 16
Cayley's formula counting labeled trees: nn-2.
Rooted labeled trees: nn-1.
Prufer sequences:
-- Find node with smallest label,
-- write down label of parent, and
-- cut the leaf.
Repeat!
The Matrix Tree Theorem.
Wednesday, September 25
Matrix Tree Theorem.
Examples: small example.
The complete graph Kn.
-- By row reduction.
-- By eigenvalues.
The complete bipartite graph Km,n.
-- By row reduction.
Friday, September 27
Lecture on zoom due to Helene:
Notes and Youtube.
Electrical networks.
Ohm's law.
Two resistors in series:
R = R1 + R2.
Two resistors in parallel:
1/R = 1/R1 + 1/R2.
Cube example... 7/12.
Computing resistance by counting spanning trees.
The cube example again, by double counting.
The icosahedron.
The infinite grid.
Monday, September 30
Cauchy--Binet for expanding the determinant det(A * B).
Proof of the Matrix Tree Theorem.
Wednesday, October 2
End of proof of the Matrix Tree Theorem.
Wednesday, December 18
Final 1:00pm -- 3:00pm.
For your other classes
see.
Thursday, December 19
The rest of your life!
You do not want to see
me
in January!
Don't click on that month.
