In Automata theory in nominal sets (Thm. 9.3), we provided a necessary and sufficient criterion for the existence of least finite supports for arbitrary atoms. It was not clear whether the criterion could be significantly simplified for Fraisse atoms. I show that it cannot be made as simple as we originally conjectured.
The criterion from the paper says that for any finite
and any distinct
, there must be
where is the group of those atom automorphisms that fix
pointwise, and
on the right-hand side is taking the subgroup generated from two subgroups. In words: wherever we can move an atom
keeping
fixed, we can also move it, in possibly many steps, alternating between steps that (in addition to
) fix
or
. (Clearly it only makes sense to start with a step that fixes
.)
In the standard examples with least supports (equality atoms, totally or partially ordered ones, or the random graph), the above can actually be achieved already in two steps. This raised a question: are two steps enough, at least for Fraisse symmetries? Formally, does the seemingly stronger condition
follow from the existence of least finite supports? (Note that the generated subgroup is replaced by the set of compositions of permutations from two subgroups.)
The answer to that question is no. For a counterexample consider, as atoms, the universal anti-transitive directed graph, i.e., one that does not contain the three-element strict total order:
as a subgraph. (This is indeed a Fraisse structure, see e.g. Macpherson’s A survey of homogeneous structures, where such digraphs are called “Henson digraphs”.)
In that graph, pick three atoms (vertices) that form a simple directed cycle:
Consider empty; then clearly
, because all atoms are in one orbit. However, it turns out that
cannot be moved to
with two automorphisms, the first of which fixes
and the second –
. Indeed, the intermediate stage
of such a two-step transition would have to have:
- an edge to
, because there is an automorphism that fixes
and maps
to
, and
has an edge to
, and
- an edge to
, because there is an automorphism that fixes
and maps
to
, and
has an edge to
.
Together with the edge from to
, this would create a forbidden pattern:
so such an atom cannot exist.
On the other hand, can be moved to
with two intermediate steps
and
, as seen here:
Here, is mapped to
and
to
by automorphisms that fix
, and
to
by an automorphism that fixes
.
It is not difficult to generalize the latter picture to show that three steps suffice for any ,
and
, hence the anti-transitive digraph admits least supports. This completes the counterexample.
Remark. Following the latter construction, it is easy to see that three steps are enough in the least support criterion for all universal directed graphs that avoid a set of finite tournaments (“Henson digraphs”, see Macpherson, op. cit.). I have not checked the details, but this should hold also for universal edge-colored graphs. About the situation in general Fraisse relational structures (hypergraphs) I understand very little.
Very interesting post;)
The following question arises:
of a set
is the union of all finite orbits of the action of
on
).
what is an analogous sufficient and necessary condition for the existence of least algebraically closed supports?
(The algebraic closure
A natural candidate would be:
for all finite, algebraically closed
and
.