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

• Pubblicazione: Providence, Rhode Island : , : American Mathematical Society, , [2011]; ©2011
• Descrizione fisica: 1 online resource (529 p.)
• Disciplina: 519.2
• Soggetto topico: Finite model theory; Combinatorial probabilities
• Soggetto genere / forma: Electronic books.
• Persona (resp. second.): GroheM (Martin); MakowskyJohann A. <1948->
• 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""
• Titolo autorizzato: Model theoretic methods in finite combinatorics
• ISBN: 0-8218-8237-6
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910479936303321
• Lo trovi qui: Univ. Federico II
• Serie: Contemporary mathematics (American Mathematical Society) ; ; v. 558.