1.

Record Nr.

UNINA9910788636303321

Titolo

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

Pubbl/distr/stampa

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

©2011

ISBN

0-8218-8237-6

Descrizione fisica

1 online resource (529 p.)

Collana

Contemporary mathematics, ; 558 , 0271-4132

Classificazione

03-0203-0605-0205-0668-0268-06

Disciplina

519.2

Soggetti

Finite model theory

Combinatorial probabilities

Lingua di pubblicazione

Inglese

Formato

Materiale a stampa

Livello bibliografico

Monografia

Note generali

Description based upon print version of record.

Nota di bibliografia

Includes bibliographical references.

Nota di contenuto

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 --  1. Introduction --  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.