Existence of least supports for Fraisse atoms

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 S\subseteq \mathbb{A} and any distinct a,b\in\mathbb{A}\setminus S, there must be

    \[a\cdot G_S \subseteq a\cdot(G_{S\cup\{b\}}+G_{S\cup\{a\}})\]

where G_S is the group of those atom automorphisms that fix S pointwise, and + on the right-hand side is taking the subgroup generated from two subgroups. In words: wherever we can move an atom a keeping S fixed, we can also move it, in possibly many steps, alternating between steps that (in addition to S) fix b or a. (Clearly it only makes sense to start with a step that fixes b.)

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

    \[a\cdot G_S \subseteq a\cdot(G_{S\cup\{b\}}G_{S\cup\{a\}})\]

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 structureswhere such digraphs are called “Henson digraphs”.)

In that graph, pick three atoms (vertices) that form a simple directed cycle:


Consider S empty; then clearly e\in a\cdot G_S, because all atoms are in one orbit.  However, it turns out that a cannot be moved to e with two automorphisms, the first of which fixes b and the second – a. Indeed, the intermediate stage c of such a two-step transition would have to have:

  • an edge to b, because there is an automorphism that fixes b and maps a to c, and a has an edge to b, and
  • an edge to a, because there is an automorphism that fixes a and maps c  to e, and e has an edge to a.

Together with the edge from a to b, this would create a forbidden pattern:


so such an atom c cannot exist.

On the other hand, a can be moved to e with two intermediate steps c and d, as seen here:


Here, a is mapped to c and d to e by automorphisms that fix b, and c to d by an automorphism that fixes a.

It is not difficult to generalize the latter picture to show that three steps suffice for any S, a and b, 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.

One thought on “Existence of least supports for Fraisse atoms”

  1. Very interesting post;)

    The following question arises:
    what is an analogous sufficient and necessary condition for the existence of least algebraically closed supports?
    (The algebraic closure \bar S of a set S\subset \atoms is the union of all finite orbits of the action of G_S on \atoms).

    A natural candidate would be:

        \[a\cdot G_S\subset a\cdot (G_{\overline{S\cup \set{a}}}+G_{\overline{S\cup \set{b}}}),\]

    for all finite, algebraically closed S\subset\atoms and a,b\in\atoms-S.

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>