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.