The sound of problems falling

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 pq 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,qP, there is at most one rP 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 pq, 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.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , , . Bookmark the permalink.

6 Responses to The sound of problems falling

  1. Benjs says:

    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.

    • Benjamin Steinberg says:

      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

      • 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.

  2. observer says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.