A new paper by Barto, Bodor, Kozik, Mottet, and Pinsker will be presented this summer at the Logic In Computer Science (LICS) conference. The paper was one of the few papers receiving a distinction this year.
The paper, entitled Symmetries of structures that fail to interpret something finite, is about the abstract algebraic properties of structures (e.g., graphs) that are able to encode every other finite structure. Any complete graph on at least 3 vertices is an example of such a structure, while a bipartite graph can only encode other bipartite graphs, or graphs that contain a loop. A classical result by Bulatov is that every finite undirected graph $\mathbb G$ containing a cycle of odd length and no loop can encode every other finite graph. Similarly, a result by Barto, Kozik, and Niven, gives that any finite loopless directed graph without sources or sinks and with algebraic length 1 can encode every other finite graph.
In the previous results, the way a graph can encode another graph is by means of pp-interpretations with constants. Two questions arise naturally:
- What if the graph is not finite?
- What if we consider pp-interpretations without the use of constants?
Read the paper to find out more!
