Color-preserving automorphisms in Fraisse classes (new version)

Again, a question closely related to a characterization of standard atoms (not to be confused with standard alphabets:). The question is a refinement of a question posted in Automorphisms vs color-preserving automorphisms in Fraisse classes, which has been answered negatively (see the recent post The colored open question closed).

Consider a Fraisse class $\cal K$ of finite structures over a finite relational vocabulary. By a colored structure from $\cal K$ we mean a structure from $\cal K$ together with a mapping from its carrier to some finite set of colors. A color class is the set of elements mapped to the same color.

A structure $A$ from $\cal K$ is stiffened by a subset $X$ of its carrier if the subgroup of automorphisms

$\aut{A/X} \ \eqdef \ \{ \pi \in \aut{A} \ : \ \forall x \in X. \ \pi(x) = x\}$

is trivial, i.e. contains only the identity. Similarly one defines when a colored structure is stiffened by $X$ , by considering color-preserving automorphisms of $A$ instead of all automorphisms.

Fact: The following conditions are equivalent, for every Fraisse class $\cal K$ :

1. The colored structures in $\cal K$ have boundedly many automorphisms: for every $m$ there is an $n$ such that every colored structure in $\cal K$ with color classes of size bounded by $m$ , has at most $n$ color-preserving automorphisms.

2. The colored structures in $\cal K$ are stiffened by a bounded number of elements: for every $m$ there is an $n$ such that every colored structure in $\cal K$ with color classes of size bounded by $m$ , is stiffened by some its subset $X$ of at most $n$ elements.

Proof (idea): 1 implies 2: A set $X$ may be found in a greedy way, by inspecting elements $x$ of $A$ is an arbitrary order and checking whether imposing the equality $\pi(x) = x$ eliminates some automorphisms of $A$ .

2 implies 1: If $X$ stiffens $A$ then every (colored) automorphism $\pi$ of $A$ is uniquely determined by its restriction $\pi|_X$ to $X$ . As the color classes are bounded and $X$ is bounded, there is only boundedly many possibilites for the value of $\pi|_X$ , and thus boundedly many color-preserving automorphisms.

Remark: It seems that the above condition is quite robust, as it may be formulated in a number of equivalent ways. For instance, one can define an independence system on color classes, and require a bound on the size of independent sets.

The conditions in the above fact may be adapted to a non-colored settings, by omiting the bound $m$ on the size of color classes. In case of condition 1, the colored and non-colored versions are inequivalent, as shown in a recent post The colored open question closed. An interesting open question remains for condition 2:

Question: Are the following two conditions equivalent, for every Fraisse class $\cal K$ ?

1. The colored structures in $\cal K$ are stiffened by a bounded number of elements.

2. The structures in $\cal K$ are stiffened by a bounded number of elements: there is an $n$ such that every structure in $\cal K$ is stiffened by some its subset of at most $n$ elements.

Atompress

Color-preserving automorphisms in Fraisse classes (new version)

Leave a Reply Cancel reply

Computation with atoms