BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vera Koponen

Vera Koponen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.LOmath.CO

Catalog footprint

What is connected

12works
2topics
2close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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.

Published work

12 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Homogeneous 1-based structures and interpretability in random structures

Let $V$ be a finite relational vocabulary in which no symbol has arity greater than 2. Let $M$ be countable $V$-structure which is homogeneous, simple and 1-based. The first main result says that if $M$ 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 $M$ is "coordinatized" by a set with SU-rank 1 and there is no definable (without parameters) nontrivial equivalence relation on $M$ with only finite classes, then $M$ is strongly interpretable in a random structure.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On sets with rank one in simple homogeneous structures

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

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A limit law of almost $l$-partite graphs

For integers $l \geq 2$, $d \geq 1$ we study (undirected) graphs with vertices $1, ..., n$ such that the vertices can be partitioned into $l$ parts such that every vertex has at most $d$ 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 \to \infty$. By combining this result with a result of Hundack, Prömel and Steger \cite{HPS} we also prove that if $1 \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, ..., n$, for some $n$, in which there is no subgraph isomorphic to the complete $(l+1)$-partite graph with parts of sizes $1, s_1, ..., s_l$. In the course of doing this we also prove that there exists a first-order formula $ξ$ (depending only on $l$ and $d$) such that the proportion of $\mcG \in \mbP_n(l,d)$ with the following property approaches 1 as $n \to \infty$: there is a unique partition of $\{1, ..., n\}$ into $l$ parts such that every vertex has at most $d$ neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by $ξ$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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 $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 $\mathcal{M}$ such that $G$ is a subgroup of the group of autmorphisms of $\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 = 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 $n \to \infty$. All instances of the respective result are proved by an essentially uniform argument.

0 citations0 reviewsNo code linkedOpen access
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^{\aleph_0}$".

0 citations0 reviewsNo code linkedOpen access
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 > 1$. For almost all finite structures (labelled or unlabelled) such that at least $m$ elements are moved by some automorphisms, the automorphism group is $(Z_2)^i$ for some $i \leq (m+1)/2$; and if some relation symbol has arity at least 3, then the automorphism group is almost always $Z_2$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Asymptotic probabilities of extension properties and random $l$-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\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 \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}$, 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.

0 citations0 reviewsNo code linkedOpen access