Selected topics from graph theory, 2014 Fall semester

**
Time and location:**

- 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).

**
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.

**
Homeworks:**

- 10/12/2014: home1.pdf
Deadline: 10/27/2014

- 11/22/2014: home2.pdf (with correction) Deadline: 12/05/2014

- 11/22/2014: home3.pdf Deadline: 12/15/2014

**
Weakly topics:**

**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.