Instructors: Pascal Koiran, Stéphan Thomassé and Nicolas Trotignon
Prerequisites: No specialized knowedge is required, however basic notions in graph theory and algorithms, complexity theory, linear algebra and discrete probability will help.
Objective: Interpreting graphs as polynomials is a very powerful technique which provides both elegant and efficient solutions to a wide range of problems. Among these, let us mention graph polynomials and counting, randomized algorithms based on the isolation lemma, and graph coloring via the combinatorial nullstellensatz. The goal of this course is to explore the rich interactions between graphs and polynomials.
Course outline:
1) Graph polynomials.
There
exist many polynomials associated to graphs, such as the chromatic
polynomial, the flow polynomial, the matching polynomial, the Tutte
polynomial,... These are usually univariate or bivariate and are
built through contraction/deletion of edges. These polynomials
capture matroidal properties of graphs, and enjoy nice duality
properties reflecting for instance planar duality. Computing the
values of these polynomials at particular points allow counting
objects such as spanning trees, matchings, flows, acyclic
orientations and so on. This is often computationally hard and more
precisely #P-complete. The course will include an introduction to
#P-completeness theory (the theory of counting complexity).
2)
Efficient algorithms.
Edmonds'
famous polynomial time algorithm for finding a perfect matching in a
graph (or certifying that no such matching exists) admits a
randomized version based on a simple idea: a multivariate polynomial
is built via a determinant, and is identically zero if and only if
the graph has no perfect matching. This condition can be checked by
a randomized algorithm (the Schwartz-Zippel or isolation Lemma). The
use of randomization is now widely spread in both classical and
fixed parameter algorithms (FPT). We will survey several
applications of polynomials to the design of efficient algorithms
(deterministic or randomized).
3) Existence
theorems.
A combinatorial variant on Hilbert's
Nullstellensatz was introduced by Noga Alon and has many
applications to graph coloring, additive combinatorics and latin
squares. We will survey this technique and mainly its application
(due to Alon and Tarsi) to the so called list coloring conjecture.
It states that if a list of d+1 colors is associated to each edge of
a graph, where d is the maximal degree of G, then the edges of the
graph can be colored by picking for each edge a color of its list in
such a way that every adjacent edges receive different colors. This
method was successfully used by Fleischner and Stiebitz to show a
conjecture of Erdos: Every graph which is the edge union of a cycle
of length 3k and k disjoint triangles is 3-colorable. Contrary to
the previous section where polynomial methods provide algorithms,
there is no known efficient algorithm giving such a 3-coloring. If
time permits, we will briefly introduce homological methods closely
related to this question.
Validation: There will be a written final exam and either a homework assignment or an oral presentation of a research article.
Bibliography:
Probability:
Alon and Spencer's Probabilistic Method.
Graphs:
Diestel's Graph
Theory, Bondy and Murty's Graph Theory, see here for
the old
edition.
Counting
complexity : Papadimitriou’s
Computational
Complexity
or Arora and Barak’s Introduction
to Computational Complexity
(more advanced) ; Jerrrum’s Counting,
sampling and Integrating : Algorithms and Complexity (first
two chapters).