A survey of homogeneous structures

DOI10.1016/J.DISC.2011.01.024MaRDI QIDQ2275386zbMATH OpenOpenAlexWikidataFDO

Authors Dugald Macpherson

Publication date 8 August 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.01.024

zbMATH Keywords

constraint satisfactionhomogeneous structureoligomorhic groupomega-categoricalpermutation groupPolish groupRamsey classsurvey paper

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Model theory of denumerable and separable structures (03C15) Categoricity and completeness of theories (03C35) Classification theory, stability, and related concepts in model theory (03C45) Properties of classes of models (03C52) Descriptive set theory (03E15) Ramsey theory (05D10) Infinite automorphism groups (20B27) Groups as automorphisms of other structures (22F50)

Review text

This survey article concerns homogeneous first-order structures, that is, countable first-order structures such that every isomorphism between finite substructures extends to a full automorphism. According to a theorem of Fraïssé, homogeneous structures arise by taking a certain limit of classes of finite structures satisfying certain coherence properties: the hereditary property, joint embedding property, and amalgamation property. Particular examples of this theorem are \((\mathbb Q,<)\), which arises as the limit of finite linear orders, and the random graph, which arises as the limit of finite graphs. The article discusses homogeneous structures with an eye towards connections with various areas of mathematics, namely model theory, permutation group theory, combinatorics, descriptive set theory, and topological dynamics. From the model-theoretic perspective, connections with \(\omega\)-categoricity and stability are discussed. The article then proceeds to discuss automorphism groups of homogeneous structures as Polish groups and topics such as free and normal subgroups of the automorphism group. Another interesting topic raised is whether or not a homogeneous structure can be ``reconstructed from its automorphism group.

Recommendations

• scientific article; zbMATH DE number 4083593
• Homogeneous structures with nonuniversal automorphism groups
• On the automorphism group of homogeneous structures
• scientific article; zbMATH DE number 1054725
• scientific article; zbMATH DE number 1064592

Cites work

• \(\aleph _ 0\)-categorical, \(\aleph _ 0\)-stable structures
• \({\aleph_{0}}\)-categorical structures: endomorphisms and interpretations
• A census of infinite distance-transitive graphs
• A Constructive Solution to a Tournament Problem
• A family of countable homogeneous graphs
• A locally finite dense group acting on the random graph
• A polynomial bound for the orders of primitive solvable groups
• A topological version of the Bergman property
• AFFINE COVERS OF LIE GEOMETRIES AND THE AMALGAMATION PROPERTY
• Application de la Notion de Relation Presque‐Enchainable au Denombrement des Restrictions Finies D'une Relation
• Aut (M ) Has a Large Dense Free Subgroup for Saturated M
• Automorphism groups of countable highly homogeneous partially ordered sets
• Automorphism Groups of Infinite Semilinear Orders (I)
• Automorphism Groups of Infinite Semilinear Orders (II)
• Automorphism groups of models of first order theories
• Automorphisms of homogeneous structures
• Autour De La Propriété Du Petit Indice
• Classification of Infinite Primitive Jordan Permutation Groups
• Classification theory and the number of non-isomorphic models
• Combinatorially homogeneous graphs
• Comeagre conjugacy classes and free products with amalgamation
• Constraint Satisfaction Problems with Infinite Templates
• Constraint Satisfaction with Countable Homogeneous Templates
• Cores of Countably Categorical Structures
• Countable connected-homogeneous graphs
• Countable homogeneous coloured partial orders
• Countable homogeneous partially ordered sets
• Countable homogeneous relational structures and ℵ₀-categorical theories
• Countable Homogeneous Tournaments
• Countable Ultrahomogeneous Undirected Graphs
• Counterexamples to a conjecture on relative categoricity
• Definable Sets in Ordered Structures. I
• Ends of graphs
• Extending partial automorphisms and the profinite topology on free groups
• Extending partial isometries
• Extending partial isomorphisms for the small index property of many \(\omega\)-categorical structures
• Extending partial isomorphisms of graphs
• Extending partial isomorphisms on finite structures
• Finite axiomatizability and theories with trivial algebraic closure
• Finite axiomatizations for existentially closed posets and semilattices
• Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures
• Finite Covers, Cohomology and Homogeneous Structures
• Finite Homogeneous 3‐Graphs
• Finite presentation of homogeneous graphs, posets and Ramsey classes
• Finitely axiomatizable ω-categorical theories and the Mazoyer hypothesis
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• Generating automorphism groups of chains
• GENERATING INFINITE SYMMETRIC GROUPS
• Generic Automorphisms of Homogeneous Structures
• Generic expansions of countable models
• Generic expansions of ω-categorical structures and semantics of generalized quantifiers
• Generic structures and simple theories
• Graphs which contain all small graphs
• GROUPS OF AUTOMORPHISMS OF N₀-CATEGORICAL STRUCTURES
• Growth Rates in Infinite Graphs and Permutation Groups
• Homogeneous graphs
• Homogeneous permutations
• Homogenizable relational structures
• Homomorphism-homogeneous partially ordered sets
• Homomorphism-Homogeneous Relational Structures
• scientific article; zbMATH DE number 3873585 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3730191 (Why is no real title available?)
• scientific article; zbMATH DE number 3741468 (Why is no real title available?)
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 125198 (Why is no real title available?)
• scientific article; zbMATH DE number 663783 (Why is no real title available?)
• scientific article; zbMATH DE number 663795 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1064592 (Why is no real title available?)
• scientific article; zbMATH DE number 1064593 (Why is no real title available?)
• scientific article; zbMATH DE number 1974653 (Why is no real title available?)
• scientific article; zbMATH DE number 1912564 (Why is no real title available?)
• scientific article; zbMATH DE number 863494 (Why is no real title available?)
• scientific article; zbMATH DE number 1425669 (Why is no real title available?)
• scientific article; zbMATH DE number 272725 (Why is no real title available?)
• scientific article; zbMATH DE number 3311772 (Why is no real title available?)
• scientific article; zbMATH DE number 3333280 (Why is no real title available?)
• scientific article; zbMATH DE number 3190329 (Why is no real title available?)
• scientific article; zbMATH DE number 3080680 (Why is no real title available?)
• Infinite homogeneous bipartite graphs with unequal sides
• Infinite Permutation Groups of Rapid Growth
• Infinite permutation groups. II: Subgroups of small index
• Interpreting groups in ω-categorical structures
• Les automorphismes d'un ensemble fortement minimal
• Minimal functions on the random graph
• Minimality conditions on circularly ordered structures
• Model Companions for ℵ 0 -Categorical Theories
• Model Theory
• Model theory of difference fields
• Non-nesting actions of Polish groups on real trees.
• Notes on infinite permutation groups
• On \(\aleph_0\)-categorical weakly o-minimal structures
• On an algebra related to orbit-counting
• On countable homogeneous 3-hypergraphs
• On countable stable structures which are homogeneous for a finite relational language
• On stabilizers of some moieties of the random tournament
• On The Profinite Topology on a Free Group
• On the Reconstruction of ℵ₀ -Categorical Structures from their Automorphism Groups
• One-dimensional asymptotic classes of finite structures
• Orbits of Infinite Permutation Groups
• Orbits of Permutation Groups on Unordered Sets, II
• Partitions of finite relational and set systems
• Posets, homomorphisms and homogeneity
• Primitive Permutation Groups with Primitive Jordan Sets
• Probabilities on finite models
• Quasi finitely axiomatizable totally categorical theories
• Random hypergraphs in pseudofinite fields
• Reconstruction of classical geometries from their automorphism group
• Reconstruction of homogeneous relational structures
• Reducts of random hypergraphs
• Reducts of the random graph
• Relations related to betweenness: their structure and automorphisms
• Semilinear tower of Steiner systems
• Set-homogeneous directed graphs
• Set-homogeneous graphs
• Smoothly Embeddable Subgraphs
• Some counting problems related to permutation groups
• SOME TREELIKE OBJECTS
• Stable Finitely Homogeneous Structures
• Stable structures homogeneous for a finite binary language
• Strongly Bounded Groups and Infinite Powers of Finite Groups
• Structure of partially ordered sets with transitive automorphism groups
• Subgroups of Infinite Symmetric Groups
• Subgroups of small Index in infinite General Linear Groups
• Subgroups of small Index in infinite Symmetric Groups
• The 116 reducts of (ℚ, <, a)
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments
• The group of the countable universal graph
• The permutation group induced on a moiety
• The probability of generating the symmetric group
• The reducts of equality up to primitive positive interdefinability
• The Small Index Property for Free Groups and Relatively Free Groups
• The small index property for infinite dimensional classical groups
• The Small Index Property for ω‐Stable ω‐Categorical Structures and for the Random Graph
• Transitivity of permutation groups on unordered sets
• Turbulence, amalgamation, and generic automorphisms of homogeneous structures
• UBIQUITY OF FREE SUBGROUPS
• UNCOUNTABLE COFINALITIES OF PERMUTATION GROUPS
• Uncountable Saturated Structures have the Small Index Property
• When is the orbit algebra of a group an integral domain ? Proof of a conjecture of P.J. Cameron
• Äquivalenzklassen von n‐Tupeln
• Über die Permutationsgruppe der natürlichen Zahlenfolge

Cited in

(only showing first 100 items - show all)

• The age of a relational structure
• On generic structures
• Set-homogeneous graphs
• Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicity
• Polymorphism clones of homogeneous structures: generating sets, Sierpiński rank, cofinality and the Bergman property
• Reconstructing the topology of the elementary self-embedding monoids of countable saturated structures
• Fraïssé limits in comma categories
• \(>k\)-homogeneous infinite graphs
• Conjugacy for homogeneous ordered graphs
• Constants and finite unary relations in qualitative constraint reasoning
• Binary simple homogeneous structures
• Inexhaustible homogeneous structures
• Eliminating unbounded search in computable algebra
• \(\aleph_0\)-categoricity of semigroups. II.
• Homogeneous actions on the random graph
• On highly regular strongly regular graphs
• Using model theory to find decidable and tractable description logics with concrete domains
• Description logics with concrete domains and general concept inclusions revisited
• On a stronger reconstruction notion for monoids and clones
• Boundedness and nuclearity of pseudo-differential operators on homogeneous trees
• IB-homogeneous graphs
• The poset of morphism-extension classes of countable graphs
• Antichains of copies of ultrahomogeneous structures
• The classification of homomorphism homogeneous tournaments
• Positive families and Boolean chains of copies of ultrahomogeneous structures
• Infinite lexicographic products
• Fraïssé's construction from a topos-theoretic perspective
• Isomorphic and strongly connected components
• Extending partial isometries of antipodal graphs
• The back-and-forth method and computability without delay
• Two Fraïssé-style theorems for homomorphism-homogeneous relational structures
• The classification of homogeneous finite-dimensional permutation structures
• On holographic structures
• Categoricity in multiuniversal classes
• Supersimple -categorical theories and pregeometries
• A topological characterisation of endomorphism monoids of countable structures
• Betweenness relations in a categorical setting
• Permutation monoids and MB-homogeneity for graphs and relational structures
• Homogeneous 2-partite digraphs
• Big Ramsey degrees of 3-uniform hypergraphs are finite
• Binary simple homogeneous structures are supersimple with finite rank
• Towards a Ryll-Nardzewski-type theorem for weakly oligomorphic structures
• Weakly almost periodic functions, model-theoretic stability, and minimality of topological groups
• Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture
• Structural homeomorphism between structural descriptors and relation between corresponding structures: a mathematical picture
• On sets with rank one in simple homogeneous structures
• On the definition of the small index property
• The 42 reducts of the random ordered graph
• The reducts of the homogeneous binary branching C-relation
• On products of elementarily indivisible structures
• A characterization of retracts in certain Fraïssé limits
• Two problems on homogeneous structures, revisited
• The automorphism group of Hall’s universal group
• The Bergman property for endomorphism monoids of some Fraïssé limits.
• A classification of orbits admitting a unique invariant measure
• scientific article; zbMATH DE number 3846995 (Why is no real title available?)
• scientific article; zbMATH DE number 3865958 (Why is no real title available?)
• Homogenizable structures and model completeness
• scientific article; zbMATH DE number 4060253 (Why is no real title available?)
• scientific article; zbMATH DE number 4083593 (Why is no real title available?)
• Beyond Lebesgue and Baire. III: Steinhaus' theorem and its descendants
• The main trends in the theory of homogeneous structures
• Fraïssé sequences: category-theoretic approach to universal homogeneous structures
• scientific article; zbMATH DE number 125198 (Why is no real title available?)
• Properties of the automorphism group and a probabilistic construction of a class of countable labeled structures
• scientific article; zbMATH DE number 1064592 (Why is no real title available?)
• Unitary representations of oligomorphic groups
• scientific article; zbMATH DE number 1974652 (Why is no real title available?)
• Countable homogeneous linearly ordered posets
• Automorphism groups of generic structures: extreme amenability and amenability
• \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
• Relatively exchangeable structures
• Generalized amalgamation and homogeneity
• Retractions of reversible structures
• Action of endomorphism semigroups on definable sets
• Reducts of the random partial order
• On constraints and dividing in ternary homogeneous structures
• Homogeneous and ultrahomogeneous Steiner systems
• Non-universality of automorphism groups of uncountable ultrahomogeneous structures
• scientific article; zbMATH DE number 1421206 (Why is no real title available?)
• Automorphism groups of finite topological rank
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
• Topological dynamics of unordered Ramsey structures
• Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
• ON THE AUTOMORPHISM GROUP OF THE UNIVERSAL HOMOGENEOUS MEET-TREE
• Lattice of definability (of reducts) for integers with successor
• The lattice of definable equivalence relations in homogeneous \(n\)-dimensional permutation structures
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• Coherent extension of partial automorphisms, free amalgamation and automorphism groups
• Homogeneous 1-based structures and interpretability in random structures
• Homogeneous structures with nonuniversal automorphism groups
• Characterizations of monadic NIP
• Tractability of quantified temporal constraints to the max
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Reconstruction of homogeneous relational structures
• scientific article; zbMATH DE number 5208304 (Why is no real title available?)
• Countable homogeneous and partially homogeneous ordered structures
• Binary primitive homogeneous simple structures
• INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES

This page was built for publication: A survey of homogeneous structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275386)