Under construction, previously updated: 3.10.12,
last updated: 3.28.2012
NEWS: On October 28, 2012 the lecture collides with the Rabin Memorial event.

We meet informally, but the course starts on November 4, 2012

Previously given as 236605 in WS 2009/10. You can see course projects of 2010 here .

Advanced Topics in Computer Science (236604) WS 2012/13

Logical Methods in Combinatorics

Home page of the course: http://www.cs.technion.ac.il/~janos/COURSES/236604-12-13.
Lecturer: Prof. J.A. Makowsky
Time: Sunday 12:30-14:30 Lecture. NO TIRGUL.
Place: Taub 8
Detailed approximate OUTLINE of given the course.
UPDATED (31.10.2009) SLIDES of given lectures will be updated during the semester.
UPDATED (24.10.2009) ABSTRACTS of given lectures will be updated during the semester.
NEW (31.10.2009) Further readings: A list of books and papers for further reading and projects (some with links to download).
UPDATED (15.12.2009) Enrolled students and their projects
NEW (15.12.2009) List of projects
For those graduate students who have already taken 236604 before, but on another topic, arrangements will be found to get credit again.
A similar course was tought also as 236601 in WS 2005/6.
Format: Two hours frontal lecture
Grading: Take home exam or (preferably) final project.
Prerequisites (Kedem): Sets and Logic (234293)
Goal:To introduce students into research literature and prepare them for thesis work in general.
Theses topics basesd on the course are available. (M.Sc. and Ph.D.)

Description of the course

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. Examples are:


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. We shall use logical methods to develop a general theory of graph polynomials.




The Graph Polynomial Project, funded ISF project, grant No. ISF 1392/07.