From the very beginnings of Model Theory, applications to Algebra, Geometry
and Number Theory accompanied its development and served as a source of inspi-
ration. In contrast to this, applications to combinatorics emerged more recently
and more slowly. Between 1975 and 1990 we saw the discovery of 0-1 laws for finite
models of sentences of Predicate Logic by R. Fagin1 and Y.V. Glebskii, D.I. Kogan,
M.I. Liogonkii and V.A.
applications of Model Theory to generating func-
tions by K.J.
and to counting functions by C. Blatter and E.
and the emergence of algorithmic meta-theorems initiated by B.
best known of these are the 0-1 laws which were, and still are, widely studied. The
least known are the applications of Model Theory to combinatorial functions.
Methodologically, in the early applications of Model Theory to Algebra and
Number Theory, elimination of quantifiers and the Compactness Theorem play
crucial oles, and the logic is always First Order Logic. In the applications to
Combinatorics the logic often is Monadic Second Order Logic, and the tools are
refinements of Ehrenfeucht-Fra¨ ıss´ e Games and of the Feferman-Vaught Theorem.
In recent years other very promising interactions between Model Theory and
Combinatorics have been developed in areas such as extremal combinatorics and
graph limits, graph polynomials, homomorphism functions and related counting
functions, and discrete algorithms, touching the boundaries of computer science
and statistical physics.
This volume highlights some of the main results, techniques, and research di-
rections of the area. Topics covered in this volume include recent developments on
0-1 laws and their variations, counting functions defined by homomorphisms and
graph polynomials and their relation to logic, recurrences and spectra, the logical
complexity of graphs, algorithmic meta theorems based on logic, universal and ho-
mogeneous structures, and logical aspects of Ramsey theory. Most of the articles
are expository and contain comprehensive surveys as well as new results on partic-
ular aspects of how to use Model Theoretic Methods in Combinatorics. They make
Fagin, Probabilities on finite models, J. Symb. Log. 41 (1976), no. 1, 50–58.
Glebskii, D.I. Kogan, M.I. Liogonkii, and V.A. Talanov, Range and degree of realiz-
ability of formulas in the restricted predicate calculus, Cybernetics 5 (1969), 142–154.
3K.J. Compton, Applications of logic to finite combinatorics, Ph.D. thesis, University of
Wisconsin, 1980.
Blatter and E. Specker, Le nombre de structures finies d’une th´ eorie ` a charact` ere fin,
Sciences Math´ ematiques, Fonds Nationale de la recherche Scientifique, Bruxelles (1981), 41–44,
and Recurrence relations for the number of labeled structures on a finite set. In Logic and Ma-
chines: Decision Problems and Complexity (E. orger, G. Hasenjaeger, and D. odding, eds.),
Lecture Notes in Computer Science, vol. 171, Springer, 1984, pp. 43–61.
Courcelle, Graph rewriting: An algebraic and logic approach, Handbook of Theoretical
Computer Science (J. van Leeuwen, ed.), vol. 2, Elsevier Science Publishers, 1990, pp. 193–242.
Previous Page Next Page