Advanced Topics in Computer Science (236601)

Logical Methods in Combinatorics

Abstracts and slides of given lectures.
NEW: Project assignments
Students who still habve now projects assigned, please contact me.

Last updated: 21 June 2005

For those graduate students who have already taken 236601 before, but on another topic, arrangements will be found to get credit again.
Under construction, last updated: 13.03.2005

Lecturer: Prof. J.A. Makowsky
Time: Sunday, 12:30-14:30
Place: Taub 401

Format

Two hours frontal lecture.
Take home exam or (preferably) final project.

Outline

The course deals with the interplay of logic and combinatorics. We study various counting problems and how their solution is affected by an additional assumption on the definability of the property of the counted objects. The following examples are taken from graph theory, but can be generalized to hypergraphs and relational structures. Examples are:

Spectra

A spectrum of a graph property is the set of finite cardinalities in which there exists graphs with this property. The spectrum of connected graphs consists of all natural numbers. The spectrum of Eulerian cliques consists of the odd numbers. What can we say about the spectrum of graph properties definable in First Order Logic, Monadic Second Order Logic or Second Order Logic? This problem is intrinsically connected to the famous open problem P =? NP.

0-1 laws

Let \PHI be a graph property, and denote by p_PHI(n) the percentage of graphs on n labeled vertices having property \PHI. What can we say about the limit of p_PHI(n) when n goes to infinity. If \PHI is definable in First Order Logic, the limit always exists and is either 0 or 1. How can this be generalized?

Recurrence relations

Let \PHI be a graph property, and denote by N_PHI(n) the number of graphs on n labeled vertices having property \PHI. What can we say about the behaviour of this function. How does it help to know that \PHI is definable in First Order Logic?

Graph polynomials

A common generalization of counting problems are graph polynomials. The most prominent of these are the matching polynomials, the colouring polynomials and the Tutte polynomial. For general graphs these are often hard to compute (#P hard). But for graphs of bounded width computation becomes easy, provided the polynomials have a range of summation which is definable in Monadic Second Order Logic.

Literature