Endomorphism monoids of finite topological spaces

This post is inspired by this Mathoverflow question.

The question asks when a transformation monoid on a set X can be the monoid of all continuous maps for some topology on X. The OP observes that the monoid must contain all constant maps and asks what else, if anything is needed.

This question is equivalent to asking which monoids can be represented as endomorphism monoids of a topological space. Indeed, a transformation monoid containing all constant maps is the same thing as a monoid M whose minimal ideal consists of left zeroes and M acts faithfully on the left of it. (Note my functions act on the left.) So if M=\mathrm{End}(X) for a topological space X, then X is the minimal ideal of M with some topology.

This is not usually the kind of problem that appeals to me, but it is quite classical in semigroup theory. Nonetheless Google didn’t seem to give an answer. Instead it showed that people studied the related question of which monoids M can be the set of all non-constant mappings on some topological space. The answer, not surprisingly, is all monoids M.

A more interesting question to me is to restrict to the finite case and make it an algorithmic question. So here is my question.

Question 1. What is the time complexity of deciding whether a finite monoid (whose minimal ideal is a left zero semigroup on which it acts faithfully) is the endomorphism monoid of a finite topological space as a function of the size of the minimal ideal?

I have chosen to make the input the size of the minimal ideal rather than the size of the monoid because we want to think of the monoid as a transformation monoid.

I probably will not work seriously on this problem because I have too much else to do. I am hoping somebody has a student looking for a problem, who might find this one interesting.

Let’s make a small translation. A topology on a finite set X is the same thing as a preorder on X. Indeed, given a topology we can define the specialization order by x\leq y\iff \overline{x}\subseteq \overline{y}. Conversely, given a preorder, we can define a topology by taking the upper sets as the open sets. Continuous mappings correspond precisely to order-preserving mappings. So we have the following reformulation of Question 1.

Question 2. What is the time complexity of deciding whether a finite monoid (whose minimal ideal is a left zero semigroup on which it acts faithfully) is the endomorphism monoid of a finite preordered set as a function of the size of the minimal ideal?

The full transformation monoid is obviously the endomorphism of the discrete and of the indiscrete topology. So we shall always assume M is a proper submonoid of the full transformation monoid T_X on a finite set X containing all the constant maps. Also we assume |X|>2 since the case |X|=2 is an easy exercise.

One possible algorithm is to compute all preorders on X that are stable under M and then see if some other functions preserve them, but that is hopelessly slow.

Let me remark that there are serious constraints on the group of units G of M. For example if G is transitive on X, then it is easy to see that the preorder is an equivalence relation. This is because if x\leq y and gx=y, then x\leq gx\leq g^2x\leq\cdots\leq g^nx for all n\geq 1. Then since G is finite, we obtain eventually that y=gx\leq x.

Continuing the above example, since we are assuming M is a proper submonoid of T_X, we can assume this equivalence relation is neither the equality relation nor the universal relation. But then it follows that M contains a non-constant, non-invertible mapping (crush a non-trivial equivalence class to a point). Thus M cannot be just a transitive group and the constant mappings. This is our first “non-trivial” constraint.

The above discussion also shows that if G is transitive, then it is is not primitive (a permutation group is primitive if it preserves no non-trivial equivalence relation). This is another restriction.

Question 3. Which finite permutation groups 0n a finite set X are the homeomorphism group of some topology on X. What is the time complexity in deciding this (as a function of |X|)?

Advertisements

About Benjamin Steinberg

Mathematician interested in semigroups, groups and automata.
This entry was posted in Math and tagged , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s