Model Theoretic Methods in Finite Combinatorics
Martin Grohe, Johann A. Makowsky · Contemporary mathematics - American Mathematical Society · 2011
Purpose of the special session We want to bring the various aspects of the interaction between Model Theory and Finite Combinatorics to a wider audience. Altough the work on 0-1 laws is by now widely known, the other applications on counting functions, graph polynomials, extremal combinatorics, graph minors and regularity lemmas, have not yet received their deserved attention. 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 [Spe01]. • 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 [Spe88, Fis03, FM03]