Preface

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.

Talanov2,

applications of Model Theory to generating func-

tions by K.J.

Compton3

and to counting functions by C. Blatter and E.

Specker4;

and the emergence of algorithmic meta-theorems initiated by B.

Courcelle5.

The

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 rˆ 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

1R.

Fagin, Probabilities on finite models, J. Symb. Log. 41 (1976), no. 1, 50–58.

2Y.V.

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.

4C.

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. B¨ orger, G. Hasenjaeger, and D. R¨ odding, eds.),

Lecture Notes in Computer Science, vol. 171, Springer, 1984, pp. 43–61.

5B.

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.

vii