This month brought news that two problems I posed have been solved. A conjecture of mine was proved by Martin Bridson and Henry Wilton, and another question (which I didn’t feel brave enough to connjecture) has been answered by Greg Cherlin.

### Extending partial permutations

A *partial permutation* of a set *A* is a bijection from a subset of *A* to another subset. The partial permutation *q* *extends* *p* if *p* is the restriction of *q* to a subset of its domain. The *composition* *p*•*q* of *p* and *q* is defined wherever it can be: that is, its domaim is the inverse image under *p* of the intersection of the range of *p* and the domain of *q*, and it is defined by applying *p* and then *q*.

Consider the following decision problem. The input is a set *P* of partial permutations on a finite set *A* satisfying the two conditions

- the identity permutation is contained in
*P*; - for any
*p,q*∈*P*, there is at most one*r*∈*P*such that*r*extends the composition of*p*and*q*.

The problem is: Does there exist a finite set *B* extending *A* and a set *Q* of permutations of *B* extending the partial permutations in *P*, so that

- the identity on
*A*extends to the identity on*B*, and - if
*r*extends*p*•*q*, and*p**,*q**,*r** are their extensions to*B*, then*r** =*p**•*q**?

I conjectured that this question is recursively unsolvable; this is what Bridson and Wilton have now proved, using a detailed (and difficult) analysis of the “triviality problem” for profinite completions of groups.

There is another question here which is still open and probably not so hard. Consider the modification of the above problem where we require that *B* = *A*, in other words, we extend the partial permutations to permutations of the same set. This problem is clearly solvable, since there are only finitely many things to test; and it is in NP, since a proposed solution can easily be checked. Is it NP-complete?

### Henson’s graphs as Cayley graphs

A *Cayley graph* for a group *G* is a graph with vertex set *G* which is invariant under right translation in *G*. If it is also invariant under left translation, it is called a *normal Cayley graph*. Thus, any Cayley graph for an abelian group is normal.

*Henson’s graph* *H _{n}* is the unique countable graph which contains every finite

*K*-free graph (where

_{n}*K*is the complete graph on

_{n}*n*vertices), and is

*homogeneous*(any isomorphism between finite subgraphs extends to an automorphism).

Ward Henson, who first constructed these graphs, showed that *H*_{3} is a Cayley graph for the infinite cyclic group, while *H _{n}* is not if

*n*> 3. I extended his result, using very similar arguments, to show that

*H*

_{3}is a Cayley graph for a wide variety of countable groups, whereas

*H*is not a

_{n}*normal*Cayley graph for any countable group; I asked whether it could be a Cayley graph. (For more details on this class of problems, see the series starting here.)

Cherlin has now shown that, for all *n*, *H _{n}* is a Cayley graph for the free group of countable rank, and for various other groups including a large class of nilpotent groups.

There is much more in his note as well; he deals with various homogeneous directed graphs and metric spaces.

This seems very close to something I proved over ten years ago. I proved it is undecidable whether a set P of partial permutations of a finite set A can be extended to a set Q of permutations of a finite set B containing A such that B generates a regular permutation group. In other words it is undecidable if a finite Stallings graph embeds in the Cayley graph of a finite group. I used Slobdskoii’s undecidability of the uniform word problem for finite grous.

Sorry, my iPad sent this comment before I finished typing my name. It is supposed to be signed Benjamin Steinberg.

That also comes into what Bridson and Wilton did.

Your iPad comment doesn’t surprise me – I haven’t yet managed to get it to do what I want rather than what it wants…

Here is my blog post describing Gurevich’s proof of the undecidability of the uniform word problem for finite semigroups http://bensteinberg.wordpress.com/author/bsteinbg/

Peter, in the end I have written an appendix to the Bridson/Wilton paper that clarifies how it relates to what I did and inverse semigroup theory. Maybe you have run into enough inverse semigroup theory by now to know the terms, otherwise I can clarify. My old result says that is is undecidable whether a finite inverse semigroup is a quotient of a finite E-unitary inverse semigroup by an ideal. Bridson/Wilton says it is undecidable if a finite inverse monoid is a quotient of a finite F-inverse monoid by an ideal.

Surely these solvers are not using an ongoing confusion over an unsolved partial differential equations problem.