Logic and Combinatorics Research Seminar (238901)
Home page under construction: Last updated 08.01.2015
For graduate and advanced undergraduate students of both Computer Science
Suitable for research topics
Last given in 2012/13: Advanced Topics in Computer Science 236604
Logical Methods in Combinatorics
Lecturer: J.A. Makowsky and participants
Time: Thursday, 12:30-14:30
Place: Taub 201
Course requirements: Seminar presentation or final project
Prerequisites: Logic and Sets, some familiarity with graph theory and combinatorics.
Unimodality of graph polynomials. Links and directions for the project.
The matching polynomial on grids. Discussion of explicit formulas and recurrence relations.
We use the slides from
2012-13 resp. 2009-10.
Logical Methods in Combinatorics, planned outline.
The topics marked (*) will be covered as much as time permits.
- Expressibility in First and Second Order Logic.
- Proving non-expressibility.
- Piecing structures together.
- Reduction methods.
Applications to combinatorics (*)
- Asymptotics and 0-1 laws.
- Spectra of first order sentences.
- Linear recurrence relations.
- Chromatic polynomial and its generalizations.
- Connection matrices of graph invariants.
- Counting homomorphisms.
H.D. Ebbinghaus and J. Flum and W. Thomas,
Mathematical Logic, 2nd edition, 1994
The Strange Logic of Random Graphs,
- 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
Graph Polynomial Project,
funded ISF project, grant No. ISF 1392/07.