Background:
In the last twenty years several applications of Logic, in particular
Model theory, to problems in Combinatorics emerged. Among them we have
- 0-1 laws and their variations
This is well summarized in the book by J. Spencer [Spen].
- Modular linear recurrence relations for combinatorial
counting functions (The Specker-Blatter Theorem)
This theorem has remained widely unnoticed,
and deserves wider attention and further study [Spec,Fisc,FM].
- Recent progress in undertanding the ultimate
periodicity of finite spectra by Y. Gurevich and S. Shelah,
and E. Fischer and J.A. Makowsky [FMa].
- Applications of meta-theorems which apply to whole families of
combinatorial problems, instead of just specific problems.
This was pioneered by B. Courcelle and S. Arnborg,
J. Lagergren and D.Seese, in applications of definability
in Monadic Second Order Logic to
graph algorithms, and summarized in J.A. Makowsky [Mak] and M. Grohe [Groh].
- The use of definability criteria in the study of
graph polynomials (Tutte polynomial and its relatives,
matching polynomials, generalized chromatic polynomials)
introduced by J.A. Makowsky [Maka], and further
developed together with B. Zilber [MZ]. See also [Makb,FMb].
- The use of model theoretic methods in designing
algorithms for the computation of forbidden minors, [AGK].
- The realization that virtually all graph polynomials
of the literature can be viewed as combinatorial
counting functions which occur inside models of
omega-stable omega-categorical theories, J. Makowsky and B. Zilber [MZ].
- The use of model theory to unify results in extremal combinatorics,
as in A. Razborov [Raz].
- Recent work on the classification and characterization
of partition functions by L. Lovasz and B. Szegedy and their
collaborators [FLS,Sz], and their complexity, cf. [BuGr].
- The use of ultraproducts in the proof of the Regularity Lemma
by B. Szegedy and G. Elek [ES].
References:
-
[ADK] I. Adler, M. Grohe and S. Kreutzer, Computing Excluded
Minors, 19th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA) 2008, 641-650.
-
[BuGr] A. Bulatov and M. Grohe, The complexity of partition
functions, Theoretical Computer Science, 348 (2005), pp. 148-186.
- [ES] G. Elek and B. Szegedy, Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard
Approach, arXiv:0705.2179.
- [Fisc] E. Fischer, The Specker-Blatter theorem does not hold for quaternary
relations, Journal of Combinatorial Theory Series A 103 (2003), 121-136.
- [FM] E. Fischer and J. A. Makowsky, The Specker-Blatter Theorem revisited,
Proceedings of the 9th COCOON (2003), 90-101.
-
[FMa] E. Fischer and J. A. Makowsky, On spectra of sentences of monadic
second order logic with counting, Journal of Symbolic Logic 69 (2004),
617-640.
-
[FMb] E. Fischer and J.A. Makowsky, Linear Recurrence Relations for
Graph Polynomials, in: Special volume of LLNCS in honour of
Boris (Boaz) A. Trakhtenbrot on the occasion of his 85th birthday.
LNCS 4800 (2008) pp. 266-279
-
[FLS] M. Freedman, L. Lovasz and A. Schrijver: Reflection positivity, rank
connectivity, and homomorphism of graphs, J. AMS 20 (2007)
-
[Groh] M.Grohe, Logic, Graphs, and Algorithms, Preprint 2007
http://www2.informatik.hu-berlin.de/~grohe/pub/meta-survey.pdf
-
[Mak] J.A. Makowsky, Algorithmic aspects of the Feferman-Vaught Theorem,
Annals of Pure and Applied Logic, 126 (1-3) April 2004, pp. 159-213.
-
[Maka] J.A. Makowsky, Coloured Tutte Polynomials and Kauffman Brackets
for Graphs of Bounded Tree Width, Discrete Applied Mathematics
145 (2005) pp. 276-290
-
[Makb] J.A. Makowsky, From a Zoo to a Zoology: Towards a General
Theory of Graph Polynomials, Theory of Computing Systems, 2008
online available at:
http://www.springerlink.com/content/p651v22676071442/?p=c6b8fee80c03417ea13428404b6086c1&pi=64
-
[MZ] J.A. Makowsky and B. Zilber, Polynomial invariants of graphs
and totally categorical theories, Preprint 2006, MODNET,
http://www.logique.jussieu.fr/modnet/Publications/Preprint%20server/papers/21/index.php
-
[Raz] A. Razborov, Flag Algebras, Journal of Symbolic Logic, 72.4
(2007, pp. 1239-1282.
-
[Spen] J. Spencer, The Strange Logic of Random Graphs, Springer 2001
-
[Spec] E. Specker, Application of Logic and Combinatorics to Enumeration Problems, in:
Trends in Theoretical Computer Science,
E. B{\"o}rger ed., Computer Science Press, 1988, 141-169,
Reprinted in: Ernst Specker, Selecta, Birkh\"auser 1990, pp. 324-350
-
[Sz] B. Szegedy, Edge coloring models and reflection positivity. math.CO/0505035