Under construction,
previously updated: 31.10.2009,
last updated: 23.04.2010
Advanced Topics in Computer Science (236605) WS 2009/10
NEW: Completed student projects
The following are the
projects
which received high grades.
Logical Methods in Combinatorics
Home page
of the course: http://www.cs.technion.ac.il/~janos/COURSES/236605-09.
Lecturer: Prof. J.A. Makowsky
Time: Sunday 13:30-15:30 Lecture and 15:30-16:30 Tirgul
Place: Taub 4
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 236605 before,
but on another topic, arrangements will be found
to get credit again.
A similar course was tought as 236601 in WS 2005/6.
Format:
Two hours frontal lecture + one hour tirgul
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:
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.
We shall use logical methods to develop a general theory of graph polynomials.
Literature
See OUTLINE.
Links
The
Graph Polynomial Project,
funded ISF project, grant No. ISF 1392/07.