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 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
- Original papers to be listed
Links
The
Graph Polynomial Project,
funded ISF project, grant No. ISF 1392/07.