Asymptotic probabilities of extension properties and random l-colourable structures

DOI10.1016/J.APAL.2011.12.001zbMATH Open1257.03057arXiv1204.2460OpenAlexW2592336120MaRDI QIDQ764265FDOQ764265

Vera Koponen

Publication date: 13 March 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Abstract: We consider a set $$ of {em finite} structures such that all members of $mb{K}_n$ have the same universe, the cardinality of which approaches $infty$ as $noinfty$. Each structure in $mbK$ may have a nontrivial underlying pregeometry and on each $mb{K}_n$ we consider a probability measure, either the uniform measure, or what we call the {em dimension conditional measure}. The main questions are: What conditions imply that for every extension axiom $varphi$, compatible with the defining properties of $mbK$, the probability that $varphi$ is true in a member of $mb{K}_n$ approaches 1 as $noinfty$? And what conditions imply that this is not the case, possibly in the strong sense that the mentioned probability approaches 0 for some $varphi$? If each $mb{K}_n$ is the set of structures with universe $1,\mathrm{...},n$, in a fixed relational language, in which certain "forbidden" structures cannot be weakly embedded and $mbK$ has the disjoint amalgamation property, then there is a condition (concerning the set of forbidden structures) which, if we consider the uniform measure, gives a dichotomy; i.e. the condition holds if and only if the answer to the first question is `yes'. In general, we do not obtain a dichotomy, but we do obtain a condition guaranteeing that the answer is `yes' for the first question, as well as a condition guaranteeing that the answer is `no'; and we give examples showing that in the gap between these conditions the answer may be either `yes' or `no'. This analysis is made for both the uniform measure and for the dimension conditional measure. The later measure has closer relation to random generation of structures and is more "generous" with respect to satisfiability of extension axioms.

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

zbMATH Keywords

colouringfinite model theorypregeometryhereditary propertyzero-one lawamalgamation propertyasymptotic probabilityextension axiomsforbidden structures

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05) Model theory of finite structures (03C13) Zero-one laws (60F20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Probabilities on finite models
• Paths in graphs
• 25 pretty graph colouring problems
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The typical structure of graphs without given excluded subgraphs
• The fine structure of octahedron-free graphs
• Combinatorial theory.
• Deux ou trois choses que je sais de L_n
• The structure of almost all graphs in a hereditary property
• Upper and lower bounds for first order expressibility
• Countable homogeneous relational structures and ℵ₀-categorical theories
• Asymptotic enumeration, global structure, and constrained evolution
• \(\aleph_0\)-categorical structures with a predimension
• The finite submodel property and \(\omega\)-categorical expansions of pregeometries
• Random I‐colorable graphs
• On first-order sentences without finite models
• Approximation and Online Algorithms

Cited In (7)

• Simple structures axiomatized by almost sure theories
• Limit laws and automorphism groups of random nonrigid structures
• Structure and enumeration theorems for hereditary properties in finite relational languages
• On sets with rank one in simple homogeneous structures
• DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS
• A limit law of almost \(l\)-partite graphs
• Random ℓ‐colourable structures with a pregeometry

This page was built for publication: Asymptotic probabilities of extension properties and random \(l\)-colourable structures

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