**Contemporary Mathematics**

Volume: 558;
2011;
519 pp;
Softcover

MSC: Primary 03; 05; 68;

Print ISBN: 978-0-8218-4943-9

Product Code: CONM/558

List Price: $145.00

Individual Member Price: $116.00

**Electronic ISBN: 978-0-8218-8237-5
Product Code: CONM/558.E**

List Price: $145.00

Individual Member Price: $116.00

# Model Theoretic Methods in Finite Combinatorics

Share this page *Edited by *
*Martin Grohe; Johann A. Makowsky*

This volume contains the proceedings of the AMS-ASL Special Session on Model Theoretic Methods in Finite Combinatorics, held January 5–8, 2009, in Washington, DC.

Over the last 20 years, various new connections between model theory and finite combinatorics emerged. The best known of these are in the area of 0-1 laws, but 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 directions 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 homogeneous structures, and logical aspects of Ramsey theory.

#### Table of Contents

# Table of Contents

## Model Theoretic Methods in Finite Combinatorics

- Contents v6 free
- Preface vii8 free
- Application of Logic to Combinatorial Sequences and Their Recurrence Relations 110 free
- Spectra and Systems of Equations 4352
- Compton's Method for Proving Logical Limit Laws 97106
- Logical Complexity of Graphs: A Survey 129138
- Methods for Algorithmic Meta Theorems 181190
- On Counting Generalized Colorings 207216
- 1. Introduction 208217
- 2. Prelude: two typical graph polynomials 210219
- 3. Counting generalized colorings 217226
- 4. SOL-polynomials and subset expansion 224233
- 5. Standard vs FF vs Newton SOL-polynomials 228237
- 6. Equivalence of counting φ-colorings and SOL-polynomials 230239
- 7. MSOL-polynomials 233242
- 8. Enter categoricity 234243
- 9. Conclusions 238247
- References 239248

- Counting Homomorphisms and Partition Functions 243252
- Some Examples of Universal and Generic Partial Orders 293302
- Two Problems on Homogeneous Structures, Revisited 319328
- On Symmetric Indivisibility of Countable Structures 417426
- Partitions and Permutation Groups 453462
- (Un)countable and (Non)effective Versions of Ramsey's Theorem 467476
- Reducts of Ramsey Structures 489498
- 1. Introduction 490499
- 2. Reducts 492501
- 3. Ramsey Classes 497506
- 4. Topological Dynamics 500509
- 5. Minimal Functions 500509
- 6. Decidability of Definability 504513
- 7. Interpretability 505514
- 8. Complexity of Constraint Satisfaction 507516
- 9. Concluding Remarks and Further Directions 516525
- References 516525

#### Readership

Graduate students and research mathematicians interested in logic, combinatorics, and theoretical computer science.