Classification of standard alphabets

The master thesis of Łukasz Wołochowski continues the study of standard alphabets and classifies  all alphabets of dimension up to 8, with regard to their standardness. Here is the thesis and here is its abstract:

This thesis concerns Turing machines with atoms. There exist alphabets with atoms over which Turing machines do not determinize and a method of alphabet classification is known. In this thesis we show and implement an improved version of this algorithm. The improvement is made by using advanced algorithms from the theory of Constraint Satisfaction Problems, as well as algebraic methods to reduce the size of a problem. As a result, we obtain a classification of all alphabets of dimension 8.

Orbit-finite bijections can be smoothed

In his recent post Bartek demonstrated an example of two equivariant sets with atoms that are related by a finitely supported bijection, but not by any equivariant bijection. We show that if the sets are orbit-finite then this situation is impossible.

Proposition. Let X and Y be two orbit-finite equivariant sets with atoms. If there exists a finitely supported bijection f \colon X \rightarrow Y then there exists an equivariant bijection F \colon X \rightarrow Y.
Continue reading

Join of two elements

Let a,b be two elements with atoms. The pair (a,b) satisfies the following universal property: (a,b) supports both a and b, and if y is another element with this property, then y supports (a,b).

We demonstrate the existence of an element denoted a\land b, with a dual property: a\land b is supported both by a and by b, and if y is another element with this property, then y is supported by a\land b.  The construction does not require any assumptions on the symmetry.

Continue reading

Bipartite graphs without bipartite partition

In the equality symmetry, there is a single-orbit graph G=(V,E) with the property that G is bipartite in the classical sense (equivalently, has no odd-length cycle) but has no partition into two parts which are finitely supported and not inter-connected. In other words, the graph G maps to the single-edge graph via a infinitely-supported homomorphism, but not via a finitely-supported one. And here’s the graph: its nodes are pairs of distinct atoms, and there is an edge from (a,b) to (b,a), whenever a,b are distinct atoms. That’s it.