Monday, July 7, 2008
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
Abstract:
A graph is called perfect if for every induced subgraph, the size of its
largest clique equals the minimum number of colors needed to color its
vertices. As it turns out, the notion of perfect graphs generalizes a
large number of phenomena, both in graph theory and in combinatorial
optimization. Therefore, the problems of charactering perfect (or
minimal
imperfect) graphs and finding an efficient recognition algorithm have
become well known in both communities. In 1960's Claude Berge made a
conjecture that any graph with no induced odd cycles of length greater
than three or their complements is perfect (thus, odd cycles of length
greater than three and their complements are the only minimal imperfect
graphs). This conjecture is known as the Strong Perfect Graph
Conjecture.
We call graphs containing no induced odd cycles of length greater than
three or their complements Berge graphs. A stronger conjecture was made
by Conforti, Cornuejols and Vuskovic, that any Berge graph either
belongs
to one of a few well understood basic classes or has a decomposition
that
can not occur in a minimal counterexample to Berge's Conjecture. In
joint
work with Neil Robertson, Paul Seymour and Robin Thomas we were able to
prove this conjecture and consequently the Strong Perfect Graph Theorem.
Later, in joint work with G. Cornuejols, X, Lui, P.Seymour and K.
Vuskovic,
we found an algorithm that tests in polynomial time whether a graph is
Berge, and therefore perfect.
In my talk I will give an overview of both these results.
Colloquium - 16:00
Abstract:
A discrete optimization problem is often modeled as the problem to find
an integral
vector x which optimizes a linear function over a set of inequalities
specified by a 0-1 matrix A and an integral vector r.
Note that problems of this type cannnot be solved efficiently in general.
However, since each row of the 0-1 matrix A can be identified with a
subset of the column set, we may take the structure of the corresponding
row set family into account.
We present a greedy-type algorithm for solving the problem if the set
family is endowed with a certain partial order: the poset forms a
consecutive lattice on which r is submodular.
Our model fits into the framework of Hoffman and Schwartz' lattice
polyhedra and covers optimization problems such as finding shortest
paths or arborescences in a digraph, an optimal basis of a polymatroid,
or a maximum flow in a planar graph.
This is joint work with Ulrich Faigle.