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.

Color-preserving automorphisms in Fraisse classes (new version)

Again, a question closely related to a characterization of standard atoms (not to be confused with standard alphabets:). The question is a refinement of a question posted in Automorphisms vs color-preserving automorphisms in Fraisse classes, which has been answered negatively (see the recent post The colored open question closed).

Continue reading

A stronger Kleene theorem

This post continues the discussion on the Kleene theorem from here. The previous post gave a notion of regular expressions that had the same expressive power as nondeterministic automata. The idea was that a star corresponds to a graph where the set of vertices had one orbit, and where the edges where labelled by simpler regular expressions. In the case without atoms, such a graph is necessarily a self loop, which corresponds to the standard Kleene star. This post is about a stronger requirement: instead of saying that the graph has one orbit of vertices, we say that it has one orbit of edges.

Continue reading