Model theoretic methods in finite combinatorics : AMS-ASL Joint Special Session, January 5-8, 2009 Washington, DC / Martin Grohe, Johann A. Makowsky, editors.

Format:

Book

Conference/Event

Author/Creator:

AMS-ASL Joint Special Session on Model Theoretic Methods in Finite Combinatorics, Corporate Author.

Contributor:

Grohe, M. (Martin), editor.

Makowsky, Johann A., 1948- editor.

American Mathematical Society.

Association for Symbolic Logic.

Conference Name:

AMS-ASL Joint Special Session on Model Theoretic Methods in Finite Combinatorics (2009 : Washington, D.C.)

AMS-ASL Joint Special Session on Model Theoretic Methods in Finite Combinatorics

Series:

Contemporary mathematics (American Mathematical Society). 0271-4132 558

Contemporary mathematics, 558 0271-4132

Language:

English

Subjects (All):

Finite model theory--Congresses.

Finite model theory.

Combinatorial probabilities--Congresses.

Combinatorial probabilities.

Physical Description:

1 online resource (529 p.)

Edition:

1st ed.

Place of Publication:

Providence, Rhode Island : American Mathematical Society, [2011]

Language Note:

English

Summary:

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.

Contents:

Contents

Preface

Application of Logic to Combinatorial Sequences and Their Recurrence Relations

Part 1. Introduction and Synopsis

1. Sequences of integers and their combinatorial interpretations

2. Linear recurrences

3. Logical formalisms

4. Finiteness conditions

5. Logical interpretations of integer sequences

Part 2. Guiding Examples

6. The classical recurrence relations

7. Functions, permutations and partitions

8. Trees and forests

9. Graph properties

10. Latin squares

Part 3. C-Finite and Holonomic Sequences

2.2. A length-depth relation

2.3. Distinguishability vs. definability

3. Ehrenfeucht games

4. The Weisfeiler-Lehman algorithm

5. Worst case bounds

5.1. Classes of graphs

5.2. General case

6. Average case bounds

Methods for Algorithmic Meta Theorems

On Counting Generalized Colorings

1. Introduction

2. Prelude: two typical graph polynomials

3. Counting generalized colorings

4. SOL-polynomials and subset expansion

5. Standard vs FF vs Newton SOL-polynomials

6. Equivalence of counting Ï?-colorings and SOL-polynomials

7. MSOL-polynomials

8. Enter categoricity

9. Conclusions

References

Counting Homomorphisms and Partition Functions

Some Examples of Universal and Generic Partial Orders

Two Problems on Homogeneous Structures, Revisited

On Symmetric Indivisibility of Countable Structures

Partitions and Permutation Groups

(Un)countable and (Non)effective Versions of Ramsey's Theorem

Reducts of Ramsey Structures

2. Reducts

3. Ramsey Classes

4. Topological Dynamics

5. Minimal Functions

6. Decidability of Definability

7. Interpretability

8. Complexity of Constraint Satisfaction

9. Concluding Remarks and Further Directions

References.

Notes:

Description based upon print version of record.

Includes bibliographical references.

Description based on print version record.

ISBN:

0-8218-8237-6