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:
#### 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.