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 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 1 R. Fagin, Probabilities on finite models, J. Symb. Log. 41 (1976), no. 1, 50–58. 2 Y.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. 4 C. Blatter and E. Specker, Le nombre de structures finies d’une th´ eorie ` 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. 5 B. 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
Previous Page Next Page