The school consists of a series of lectures on the Lovasz's theta function and perfect graphs.
by prof. Arnaud Pecher
Syllabus:
The clique number is a trivial lower bound for the chromatic number, but by far not always tight. The graphs where both parameters coincide for all induced subgraphs are called perfect. A main result of combinatorial optimization is that the weighted clique number and the chromatic number of a perfect graph are computable in polynomial time (Grotschel, Lovasz and Schrijver 1981).
In the first part, I will outline the proof of this celebrated result, with a focus on the main mathematical objects : the stable set polytope and Lovasz theta body. Then I will mention two applications of cyclotomic fields. The first application is an extension of Grotschel, Lovasz and Schrijver's polynomial time computability of the chromatic number of perfect graphs to the circular-chromatic number, a refinement of the chromatic number, and to a superclass of perfect graphs: circular-perfect graphs.
The second application is the use of cyclotomic fields as a convenient space for the construction of dense sphere packings in high dimensions. This problem has a natural reformulation in graph theoretic terms as follows: let G denote the graph whose vertices are the points of the Euclidean space and edges are pair of vertices at distance at most 2 one from the other. The independent sets of G are the sphere packings: so, finding a maximum density sphere packing is the same as finding a maximum-density independent set in this infinite graph.
Maximum density independent sets will constitute the main subject of the last part of my lecture, with an overview of some recent progress on the fractional chromatic number of the plane (stimulated by De Grey's breakthrough on the chromatic number of the plane) and a study of the case of polytope norms, mainly in dimension 3.
The schedule of lectures:
December 3: 14:40 - 18:50 in lecture room S7
December 4: 14:00 - 17:20 in lecture room S10
Posted on 2019-11-05