# CR 04: Graphs and Polynomials

• 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).