Location
This course is given onsite at Utrecht Campus Science Park: Room HFG 611, Hans-Freudenthal building, Budapestlaan 6.

Time
Monday 11.00 - 12.45, November 18 - December 16 2024, January 6 2025, and January 20 - February 10 2025

Lecturers
Monique Laurent (CWI, Tilburg University), Sven Polak (Tilburg University)

Course material
The course will be based on parts of the Lecture Notes: A Course on Combinatorial Optimization by A. Schrijver (abbreviated below as [LNAS]), and on the Lecture Notes: Networks and Semidefinite Programming (abbreviated below as [NSP]).

Examination
Take home problems will be distributed on a weekly basis and will be posted below.

Rules:
- You may work in a group of two students and return a common solution set for the group (but every student is expected to work individually on all exercises).
- Write the solutions preferably in Latex. Handwritten solutions must be written in a careful and well readable manner.
- The solutions can be handed in after the end of the course.
- Please email your solutions (pdf file, no doc file) at Sven.Polak@cwi.nl, M.Laurent@cwi.nl
- The deadline to send the solutions is March 17 2025.

Program of the course and weekly assignments:

Lecture about (part of) Chapter 6 and Chapter 7.1 in [LNAS]: basic facts about complexity classes, introducing basic graph parameters (stable sets, cliques, coloring) and some facts on their complexity.

Homework Exercises: Exercise 7.4 in [LNAS], and Exercises A & B posted here.

Monday 25 November [Sven]

Lecture about Chapters 7.1 and 7.2 in [LNAS]: vertex and edge covers, vertex and edge coloring of graphs.

Homework Exercises: Posted here.

Monday 2 December [Sven]

Lecture about Chapters 7.3 and 7.4 in [LNAS]: Dilworth theorem, basic facts about perfect graphs, and the perfect graph theorem.

Homework exercises: Exercises 7.19, 7.22 (in [LNAS]) and Exercises A, B below.

Exercise A: Assume that G1 and G2 are two perfect graphs, with disjoint sets of vertices. Build the new graph G, obtained by taking the union of G1 and G2, and adding all possible edges between nodes of G1 and nodes of G2. Show that G is perfect.

Exercise B: Give a class of perfect graphs having exponentially many maximal stable sets and exponentially many maximal cliques (in terms of the number of nodes).
Hint: You may want to use the result of Exercise A.

Monday 9 December [Sven]

Lecture about Chapters 7.4 and 7.5 in [LNAS]: proof of the perfect graph theorem, chordal graphs, simplicial nodes and perfect elimination orderings, efficient algorithms for cliques, stable sets and coloring (further details next week).

Homework exercises: Exercises 7.30 and 7.32 in [LNAS].

Monday 16 December [Sven]

Follow-up on chordal graphs: perfect elimination orderings and their use for efficiently computing stability number, clique number, coloring number in chordal graphs; tree representation of chordal graphs.
If you are interested to read more about chordal graphs (and the related concepts of partial k-trees and tree-width of graphs) you may look at the following survey by Heggernes.
Lecture about Section 3.2.1 and Section 3.3.1 in the Lecture Notes [NSP]: LP approach to maximum stable sets and minimum coloring, fractional stable sets and coloring, introducing Lovasz theta number.

Before the next lecture on Monday 6 January, please read Chapter 1 in [NSP] containing preliminaries about positive semidefinite matrices.

Homework exercises: Exercise 1.1 in [NSP] (Hint: think of using the Schur complement operation); Exercise 1.2 from [NSP].
Exercise A: Consider the matrix M with entries M(i,j)= 1/(i+j) for i,j=1,..,n. Show that M is positive semidefinite. (Hint: Given a nonnegative integer k, if you integrate the function x-> x^k over the interval [0,1], what value do you get?)

Monday 6 January [Monique]

Lecture about Chapter 2 (primal and dual SDP programs, weak duality, strong duality under strict feasibility, efficient algorithm).

Homework Exercises: Exercise 2.3 in [NSP] and Exercises A, B posted here.

Monday 20 January [Monique]

Lecture about (parts of) Chapter 3.1 (perfect graphs), Chapter 3.2.1 (fractional stability number and coloring), Chapter 3.3.1 (sandwich theorem), Chapter 3.4 (various formulations of the theta number), Chapter 3.5 (theta body), Chapter 3.6 (theta number of vertex-transitive graphs - please read it in detail), Chapter 3.7 (using the theta number to bound the Shannon capacity).

Homework Exercises: Exercises 3.1, 3.2 in [NSP].

Monday 27 January

Homework Exercises:

Monday 3 February: no class

Monday 10 February

Homework Exercises: