papers

Let \(m\) be a positive integer, \(X\) a graph with vertex set \(Ω\), and \({\rm WL}_m(X)\) the coloring of the Cartesian \(m\)-power \(Ω^m\), obtained by the \(m\)-dimensional Weisfeiler-Leman algorithm. The \({\rm WL}\)-dimension of the graph \(X\) is defined to be the smallest \(m\) for which the coloring \({\rm WL}_m(X)\) determines \(X\) up to isomorphism. It is known that the \({\rm WL}\)-dimension of any planar graph is \(2\) or \(3\), but no planar graph of \({\rm WL}\)-dimension \(3\) is known. We prove that the \({\rm WL}\)-dimension of a polyhedral (i.e., \(3\)-connected planar) graph \(X\) is at most \(2\) if the color classes of the coloring \({\rm WL}_2(X)\) are the orbits of the componentwise action of the group \({\rm Aut}(X)\) on \(Ω^2\).

Abstract Sabidussi’s theorem [Duke Math. J. 28 (1961), 573–578] gives necessary and sufficient conditions under which the automorphism group of a lexicographic product of two graphs is a wreath product of the respective automorphism groups. We prove a quantum version of Sabidussi’s theorem for finite graphs, with the automorphism groups replaced by quantum automorphism groups and the wreath product replaced by the free wreath product of quantum groups. This extends the result of Chassaniol [J. Algebra 456, 2016, 23–45], who proved it for regular graphs. Moreover, we apply our result to lexicographic products of quantum vertex transitive graphs, determining their quantum automorphism groups even when Sabidussi’s conditions do not apply.

We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free products and free wreath products. This can be considered a quantum version of Jordan’s theorem for the automorphism groups of trees. This is one of the first characterisations of quantum automorphism groups of a natural class of graphs with quantum symmetry.

By a map we mean a 2-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.

We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of planar graphs. The characterization is formulated in terms of inhomogeneous wreath products. In the proof, we combine techniques from combinatorics, group theory, and geometry. Our result significantly improves the Babai’s description (1975).