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.

 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>