Limit laws and automorphism groups of random nonrigid structures

DOI10.4115/JLA.2015.7.2MaRDI QIDQ5247121zbMATH OpenOpenAlexWikidataFDO

Authors Ove Ahlman, Vera Koponen

Publication date 23 April 2015

Published in Journal of Logic and Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1305.3097

zbMATH Keywords

automorphism groupfinite model theorylimit lawrandom structurezero-one law

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Combinatorial probability (60C05) Zero-one laws (60F20)

Abstract: A systematic study is made, for an arbitrary finite relational language with at least one symbol of arity at least 2, of classes of nonrigid finite structures. The well known results that almost all finite structures are rigid and that the class of finite structures has a zero-one law are, in the present context, the first layer in a hierarchy of classes of finite structures with increasingly more complex automorphism groups. Such a hierarchy can be defined in more than one way. For example, the $k$th level of the hierarchy can consist of all structures having at least $k$ elements which are moved by some automorphism. Or we can consider, for any finite group $G$, all finite structures $mathcalM$ such that $G$ is a subgroup of the group of autmorphisms of $mathcalM$; in this case the "hierarchy" is a partial order. In both cases, as well as variants of them, each "level" satisfies a logical limit law, but not a zero-one law (unless $k=0$ or $G$ is trivial). Moreover, the number of (labelled or unlabelled) $n$-element structures in one place of the hierarchy divided by the number of $n$-element structures in another place always converges to a rational number or to $infty$ as $noinfty$. All instances of the respective result are proved by an essentially uniform argument.

Recommendations

• Typical automorphism groups of finite nonrigid structures
• scientific article; zbMATH DE number 1361526
• A geometric zero-one law
• scientific article; zbMATH DE number 7703228
• Counting unlabeled structures

Cites work

• Asymmetric graphs
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Asymptotic probabilities of extension properties and random l-colourable structures
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• On graphs with given automorphism group
• The computational complexity of asymptotic problems. I: Partial orders
• The number of finite relational structures

Cited in

(6)

• Extremal solutions of an inequality concerning supports of permutation groups and punctured Hadamard codes
• Simple structures axiomatized by almost sure theories
• Homogenizable structures and model completeness
• scientific article; zbMATH DE number 1361526 (Why is no real title available?)
• Typical automorphism groups of finite nonrigid structures
• Binary linear codes with near-extremal maximum distance

This page was built for publication: Limit laws and automorphism groups of random nonrigid structures

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