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:30-14: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
2012-13 resp. 2009-10.
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 non-expressibility.
- Piecing structures together.
- Reduction methods.
Applications to combinatorics (*)
- Counting.
- 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.
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.