- South Block (Déli Tömb) 00.623
- Friday 2:30-4:00pm
- Attention: No classes on Sept 26, Oct 24 (national holiday) and Oct 31 (Fall break).
- 10/12/2014: home1.pdf
- 11/22/2014: home2.pdf (with correction) Deadline: 12/05/2014
- 11/22/2014: home3.pdf Deadline: 12/15/2014
Time and location:
Course notes:L. Lovász: Geometric representations of graphs. Version 10/12/2014
Do not print the whole book, I will make upgrades/corrections during the semester.
September 12.Introductory example: Approximating the maximum cut (the Goemans-Williamson algorithm). Section 1.2.
Harmonic functions on graphs, definition and simple properties. Section 4.1.
September 19.Harmonic functions: Three constructions (random walks, electrical networks, rubber bands). Section 4.2.
Applications of the equivalence (formulas for commute time, resistance, force, Rayleigh monotonicity property). Section 4.3.
October 3.Rubber band representations. Convexity of the energy. Tutte's Theorem: rubber band representation gives planar embedding. Sections 5.1, 5.2, 5.3.1.
October 10.Projecting and lifting graphs: Projection of convex polytope is a rubber band embedding, and rubber band embedding can be lifted to a convex polytope. First proof of Steinitz's Theorem. Sections 5.3.2, 5.3.3.
October 17.Köbe representation by touching circles. Double circle representation. Almost-proof by adjusting the radii. Proof by optimizing a more sophisticated objective function.
November 7.Spherical version of Köbe representation: double cap representation. Application: Planar Separator Theorem. Auxiliary result: statistical center of a finite point set.
November 14.Harmonic functions and the Brooks-Smith-Stone-Tutte representation of a planar graph by square tiling.
Orthogonal representations: definition and basic examples. The Shannon capacity problem.
November 21.Orthogonal representations: definition and basic properties of the theta function, application to the Shannon capacity problem. Several formulas, duality; beginning of proof.