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 Hn is the unique countable graph which contains every finite Kn-free graph (where Kn is the complete graph on n vertices), and is homogeneous (any isomorphism between finite subgraphs extends to an automorphism).
Ward Henson, who first constructed these graphs, showed that H3 is a Cayley graph for the infinite cyclic group, while Hn is not if n > 3. I extended his result, using very similar arguments, to show that H3 is a Cayley graph for a wide variety of countable groups, whereas Hn is not a 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, Hn 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.