Advanced Topics in Computer Science (236605)
Logical Methods in Combinatorics, planned outline.
The topics marked (*) will be covered as much as time permits.
Logical Methods
 Expressibility in First and Second Order Logic.
 Proving nonexpressibility.
 Piecing structures together.
 Reduction methods.
Applications to combinatorics (*)
 Counting.
 Asymptotics and 01 laws.
 Spectra of first order sentences.
 Linear recurrence relations.
 Chromatic polynomial and its generalizations.
 Connection matrices of graph invariants.
 Counting homomorphisms.
References

H.D. Ebbinghaus and J. Flum and W. Thomas,
Mathematical Logic, 2nd edition, 1994

J. Spencer,
The Strange Logic of Random Graphs,
Springer, 2001
 B. Bollobas, Modern Graph Theory, Springer, 1998
 R. Diestel, Graph Theory, Springer, 3rd edition, 2005
 Original papers to be listed
Links
The
Graph Polynomial Project,
funded ISF project, grant No. ISF 1392/07.