اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAutomorphism groups of maps in linear time
149
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
A detailed proof is given of a theorem describing the centraliser of a transitive permutation group, with applications to automorphism groups of objects in various categories of maps, hypermaps, dessins, polytopes and covering spaces, where the autom
orphism group of an object is the centraliser of its monodromy group. An alternative form of the theorem, valid for finite objects, is discussed, with counterexamples based on Baumslag--Solitar groups to show how it fails more generally. The automorphism groups of objects with primitive monodromy groups are described, as are those of non-connected objects.
We continue our program of improving the complexity of so-called Boltzmann sampling algorithms, for the exact sampling of combinatorial structures, and reach average linear-time complexity, i.e. optimality up to a multiplicative constant. Here we sol
ve this problem for irreducible context-free structures, a broad family of structures to which the celebrated Drmota--Lalley--Woods Theorem applies. Our algorithm is a rejection algorithm. The main idea is to single out some degrees of freedom, i.e. write $p(x)=p_1(y) p_2(x|y)$, which allows to introduce a rejection factor at the level of the $y$ object, that is almost surely of order $1$.
Building on earlier results for regular maps and for orientably regular chiral maps, we classify the non-abelian finite simple groups arising as automorphism groups of maps in each of the 14 Graver-Watkins classes of edge-transitive maps.
In this paper, we classify regular polytopes with automorphism groups of order $2^n$ and Schlafli types ${4, 2^{n-3}}, {4, 2^{n-4}}$ and ${4, 2^{n-5}}$ for $n geq 10$, therefore giving a partial answer to a problem proposed by Schulte and Weiss in [P
roblems on polytopes, their groups, and realizations, Periodica Math. Hungarica 53(2006) 231-255].
A graph is edge-transitive if its automorphism group acts transitively on the edge set. In this paper, we investigate the automorphism groups of edge-transitive graphs of odd order and twice prime valency. Let $Gamma$ be a connected graph of odd orde
r and twice prime valency, and let $G$ be a subgroup of the automorphism group of $Ga$. In the case where $G$ acts transitively on the edges and quasiprimitively on the vertices of $Ga$, we prove that either $G$ is almost simple or $G$ is a primitive group of affine type. If further $G$ is an almost simple primitive group then, with two exceptions, the socle of $G$ acts transitively on the edges of $Gamma$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
