CoSP School on homomorphisms

The school consists of a series of lectures on

The Lov\'asz's theta function and perfect graphs.

by prof. Arnaud Pecher


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
and the chromatic number of a perfect graph are computable in polynomial
time (Gr\"otschel, Lov\'asz 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 Lov\'asz
theta body.

Then I will mention two applications of cyclotomic fields. The first
application is an extension of
Gr\"otschel, Lov\'asz 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
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
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