Source author record

Vera Koponen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

12works
2topics
2close collaborators

Published work

12 publications

preprint2016arXiv

Binary primitive homogeneous simple structures

Suppose that M is countable, binary, primitive, homogeneous, and simple, and hence 1-based. We prove that the SU-rank of the complete theory of M is~1. It follows that M is a random structure. The conclusion that M is a random structure does not hold if the binarity condition is removed, as witnessed by the generic tetrahedron-free 3-hypergraph. However, to show that the generic tetrahedron-free 3-hypergraph is 1-based requires some work (it is known that it has the other properties) since this notion is defined in terms of imaginary elements. This is partly why we also characterize equivalence relations which are definable without parameters in the context of omega-categorical structures with degenerate algebraic closure. Another reason is that such characterizations may be useful in future research about simple (nonbinary) homogeneous structures.

preprint2015arXiv

Homogeneous 1-based structures and interpretability in random structures

Let VV be a finite relational vocabulary in which no symbol has arity greater than 2. Let MM be countable VV-structure which is homogeneous, simple and 1-based. The first main result says that if MM is, in addition, primitive, then it is strongly interpretable in a random structure. The second main result, which generalizes the first, implies (without the assumption on primitivity) that if MM is "coordinatized" by a set with SU-rank 1 and there is no definable (without parameters) nontrivial equivalence relation on MM with only finite classes, then MM is strongly interpretable in a random structure.

preprint2014arXiv

On sets with rank one in simple homogeneous structures

We study definable sets DD of SU-rank 1 in MeqM^{eq}, where MM is a countable homogeneous and simple structure in a language with finite relational vocabulary. Each such DD can be seen as a `canonically embedded structure', which inherits all relations on DD which are definable in MeqM^{eq}, and has no other definable relations. Our results imply that if no relation symbol of the language of MM has arity higher than 2, then there is a close relationship between triviality of dependence and DD being a reduct of a binary random structure. Somewhat more preciely: (a) if for every n≥2n \geq 2, every nn-type p(x1,...,xn)p(x_1, ..., x_n) which is realized in DD is determined by its sub-2-types q(xi,xj)⊆pq(x_i, x_j) \subseteq p, then the algebraic closure restricted to DD is trivial; (b) if MM has trivial dependence, then DD is a reduct of a binary random structure.

preprint2013arXiv

A limit law of almost ll-partite graphs

For integers l≥2l \geq 2, d≥1d \geq 1 we study (undirected) graphs with vertices 1,...,n1, ..., n such that the vertices can be partitioned into ll parts such that every vertex has at most dd neighbours in its own part. The set of all such graphs is denoted $\mbP_n(l,d)$. We prove a labelled first-order limit law, i.e., for every first-order sentence φφ, the proportion of graphs in $\mbP_n(l,d)$ that satisfy φφ converges as n→∞n \to \infty. By combining this result with a result of Hundack, Prömel and Steger \cite{HPS} we also prove that if 1≤s1≤...≤sl1 \leq s_1 \leq ... \leq s_l are integers, then $\mb{Forb}(\mcK_{1, s_1, ..., s_l})$ has a labelled first-order limit law, where $\mb{Forb}(\mcK_{1, s_1, ..., s_l})$ denotes the set of all graphs with vertices 1,...,n1, ..., n, for some nn, in which there is no subgraph isomorphic to the complete (l+1)(l+1)-partite graph with parts of sizes 1,s1,...,sl1, s_1, ..., s_l. In the course of doing this we also prove that there exists a first-order formula ξξ (depending only on ll and dd) such that the proportion of $\mcG \in \mbP_n(l,d)$ with the following property approaches 1 as n→∞n \to \infty: there is a unique partition of {1,...,n}\{1, ..., n\} into ll parts such that every vertex has at most dd neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by ξξ.

preprint2013arXiv

A note on noncompact logics

A condition, in two variants, is given such that if a property P satisfies this condition, then every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The result is used to prove that for a number of natural properties P speaking about automorphism groups, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The basic idea underlying the results and examples presented here is that, using results from random graph theory, it is possible to construct a countable first-order theory T such that every model of T has a very rich automorphism group, but every finite subset of T has a model which is rigid.

preprint2013arXiv

Limit laws and automorphism groups of random nonrigid structures

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 kkth level of the hierarchy can consist of all structures having at least kk elements which are moved by some automorphism. Or we can consider, for any finite group GG, all finite structures M\mathcal{M} such that GG is a subgroup of the group of autmorphisms of M\mathcal{M}; 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=0k = 0 or GG is trivial). Moreover, the number of (labelled or unlabelled) nn-element structures in one place of the hierarchy divided by the number of nn-element structures in another place always converges to a rational number or to ∞\infty as n→∞n \to \infty. All instances of the respective result are proved by an essentially uniform argument.

preprint2013arXiv

On compactness of logics that can express properties of symmetry or connectivity

A condition, in two variants, is given such that if a property P satisfies this condition, then every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The result is used to prove that for a number of natural properties P speaking about automorphism groups or connectivity, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. We also give an example of a logic that extends first-order logic, has the compactness property and can express the property "the cardinality of the automorphism group is at most 2ℵ02^{\aleph_0}".

preprint2013arXiv

Typical automorphism groups of finite nonrigid structures

We work with a finite relational vocabulary with at least one relation symbol with arity at least 2. Fix any integer m>1m > 1. For almost all finite structures (labelled or unlabelled) such that at least mm elements are moved by some automorphisms, the automorphism group is (Z2)i(Z_2)^i for some i≤(m+1)/2i \leq (m+1)/2; and if some relation symbol has arity at least 3, then the automorphism group is almost always Z2Z_2.

preprint2012arXiv

Asymptotic probabilities of extension properties and random ll-colourable structures

We consider a set $\mbK = \bigcup_{n \in \mbbN}\mbK_n$ of {\em finite} structures such that all members of $\mbK_n$ have the same universe, the cardinality of which approaches ∞\infty as n→∞n\to\infty. Each structure in $\mbK$ may have a nontrivial underlying pregeometry and on each $\mbK_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 φφ, compatible with the defining properties of $\mbK$, the probability that φφ is true in a member of $\mbK_n$ approaches 1 as n→∞n \to \infty? And what conditions imply that this is not the case, possibly in the strong sense that the mentioned probability approaches 0 for some φφ? If each $\mbK_n$ is the set of structures with universe 1,...,n{1, ..., 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.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.