Logic and Combinatorics Research Seminar (238901)

For graduate and advanced undergraduate students of both Computer Science
and Mathematics.

Suitable for research topics

Last given in 2012/13: Advanced Topics in Computer Science 236604
Logical Methods in Combinatorics
Home page under construction: Last updated 08.01.2015
Lecturer: J.A. Makowsky and participants
Time: Thursday, 12:3014:30
Place: Taub 201
Course requirements: Seminar presentation or final project
Prerequisites: Logic and Sets, some familiarity with graph theory and combinatorics.
Projects

Unimodality of graph polynomials. Links and directions for the project.

The matching polynomial on grids. Discussion of explicit formulas and recurrence relations.
Seminar notes
We use the slides from
201213 resp. 200910.
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
 L. Lovasz, Large Networks and Graph Limits, AMS Colloquium Publications, volume 60, 2012
 Original papers to be listed
Links
The
Graph Polynomial Project,
funded ISF project, grant No. ISF 1392/07.