Petrie lengths of regular maps

A regular map \({\mathcal{M}}\) is an embedding of a graph into a compact surface S such that its automorphism group \({{\rm Aut}^+(\mathcal{M}) \subseteq {\rm Aut}^+(S)}\) acts transitively on the directed edges. A Petrie polygon of \({\mathcal{M}}\) is a zig-zag circuit in which every two consecutive edges but no three belong to the same face. It is known that the number of sides of every Petrie polygon of \({\mathcal{M}}\) is the same and this number is called the Petrie length of \({\mathcal{M}}\). In this paper our main concern is the Petrie lengths of toroidal regular maps. There are mainly two types of such regular maps up to duality, and for each type we prove a theorem that enables us to determine the Petrie length of the corresponding map. We also find the Petrie lengths of Accola–Maclachlan, Wiman and Fermat maps, which are well-known families of regular maps. Finally, we consider regular maps with Petrie length 2, and prove that only Accola–Maclachlan and Wiman surfaces underlie such regular maps. In this way, we obtain new characterizations of Accola–Maclachlan and Wiman surfaces.     

A combinatorial theory of Grünbaum's new regular polyhedra,Part II: Complete enumeration

The new regular polyhedra as defined by Branko Grünbaum in 1977 (cf. [5]) are completely enumerated. By means of a theorem of Bieberbach, concerning the existence of invariant affine subspaces for discrete affine isometry groups (cf. [3], [2] or [1]) the standard crystallographic restrictions are established for the isometry groups of the non finite (Grünbaum-)polyhedra. Then, using an appropriate classification scheme which—compared with the similar, geometrically motivated scheme, used originally by Grünbaum—is suggested rather by the group theoretical investigations in [4], it turns out that the list of examples given in [5] is essentially complete except for one additional polyhedron.So altogether—up to similarity—there are two classes of planar polyhedra, each consisting of 3 individuals and each class consisting of the Petrie duals of the other class, and there are ten classes of non planar polyhedra: two mutually Petrie dual classes of finite polyhedra, each consisting of 9 individuals, two mutually Petrie dual classes of infinite polyhedra which are contained between two parallel planes with each of those two classes consisting of three one-parameter families of polyhedra, two further mutually Petrie dual classes each of which consists of three one parameter families of polyhedra whose convex span is the whole 3-space, two further mutually Petrie dual classes consisting of three individuals each of which spanE ³ and two further classes which are closed with respect to Petrie duality, each containing 3 individuals, all spanningE ³, two of which are Petrie dual to each other, the remaining one being Petrie dual to itself.In addition, a new classification scheme for regular polygons inE ⁿ is worked out in §9.     

Series parallel extensions of plane graphs to dual-eulerian graphs

A plane graph is dual-eulerian if it has an eulerian tour with the property that the same sequence of edges also forms an eulerian tour in the dual graph. Dual-eulerian graphs are of interest in the design of CMOS VLSI circuits.Every dual-eulerian plane graph also has an eulerian Petrie (left–right) tour thus we consider series-parallel extensions of plane graphs to graphs, which have eulerian Petrie tours. We reduce several special cases of extensions to the problem of finding hamiltonian cycles. In particular, a 2-connected plane graph G has a single series parallel extension to a graph with an eulerian Petrie tour if and only if its medial graph has a hamiltonian cycle.     

Representing the sporadic Archimedean polyhedra as abstract polytopes

We present the results of an investigation into the representations of Archimedean polyhedra (those polyhedra containing only one type of vertex figure) as quotients of regular abstract polytopes. Two methods of generating these presentations are discussed, one of which may be applied in a general setting, and another which makes use of a regular polytope with the same automorphism group as the desired quotient. Representations of the 14 sporadic Archimedean polyhedra (including the pseudorhombicuboctahedron) as quotients of regular abstract polyhedra are obtained, and summarised in a table. The information is used to characterize which of these polyhedra have acoptic Petrie schemes (that is, have well-defined Petrie duals).     

Coxeter–Petrie Complexes of Regular Maps

Coxeter–Petrie complexes naturally arise as thin diagram geometries whose rank 3 residues contain all of the dual forms of a regular algebraic map M. Corresponding to an algebraic map is its classical dual, which is obtained simply by interchanging the vertices and faces, as well as its Petrie dual, which comes about by replacing the faces by the so-called Petrie polygons. Jones and Thornton have shown that these involutory duality operations generate the symmetric groupS₃ , giving in all six dual forms, and whose source is the outer automorphism group of the infinite triangle group generated by involutions s₁, s₂, s₃, subject to the additional relation s₁s₃ =  s₃s₁. In fact, this outer automorphism group is parametrized by the permutations of the three commuting involutions s₁,s₃ , s₁s₃. These involutions together with the involutions₂ can be taken to define the nodes of a Coxeter diagram of shape D₄(with the involution s₂at the central node), and when the original map M is regular, there is a natural extension from M to a thin Coxeter complex of rank 4 all of whose rank 3 residues are isomorphic to the various dual forms of M. These are fully explicated in case the original algebraic map is a Platonic map.     

Über projektive Moduln und Endlichkeitshindernisse bei Transformationsgruppen

We study projective modules in the category of functors from homogeneous spaces into abelian groups. Such functors have been considered by Bredon [1]. We show that protective functors are determined by a set of ordinary projective modules over suitable group rings. The general notions are applied to give a quick proof for the product formula of the finiteness obstruction for transformation groups. These finiteness obstructions are straightforward extensions of the Swan-Wall obstructions (see e. g. Quinn [7]). They are important in the study of homotopy representations (tom Dieck — Petrie [3], [4]). This work is also related to Rothenberg [8].     

Homotopy equivalent group representations and Picard groups op the burnside ring and the character ring

We are concerned with the homotopy theory of group representations and its relation to character theory and the theory of the Burnside ring. We combine the methods of tom Dieck — Petrie [4] and torn Dieck [3] to show that the canonical map from the J-group jO(G), a subquotient of the representation ring RO(G), into the Picard group of the rational representation ring is injective for p-groups G. Moreover we compute the order of the cokernel of this map. We show that the Picard group of the rational representation ring is a direct summand in the Picard group of the Burnside ring. Finally we compute the Picard groups if G is abelian and indicate a computation for general G.     

Spin^{\rm c} -manifolds with Pin(2)-action

We study -manifolds with Pin(2)-action. The main tool is a vanishing theorem for certain indices of twisted -Dirac operators. This theorem is used to show that the Witten genus vanishes on such manifolds provided the first Chern class and the first Pontrjagin class are torsion. We apply the vanishing theorem to cohomology complex projective spaces and give partial evidence for a conjecture of Petrie. For example we prove that the total Pontrjagin class of a cohomology with -action has standard form if the first Pontrjagin class has standard form. We also determine the intersection form of certain 4-manifolds with Pin(2)-action. Received: 26 June 1998     

Self‐dual and self‐petrie‐dual regular maps

Regular maps are cellular decompositions of surfaces with the “highest level of symmetry”, not necessarily orientation‐preserving. Such maps can be identified with three‐generator presentations of groups G of the form G = 〈a, b, c|a² = b² = c² = (ab)^k = (bc)^m = (ca)² = … = 1〉; the positive integers k and m are the face length and the vertex degree of the map. A regular map (G;a, b, c) is self‐dual if the assignment b?b, c?a and a?c extends to an automorphism of G, and self‐Petrie‐dual if G admits an automorphism fixing b and c and interchanging a with ca. In this note we show that for infinitely many numbers k there exist finite, self‐dual and self‐Petrie‐dual regular maps of vertex degree and face length equal to k. We also prove that no such map with odd vertex degree is a normal Cayley map. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:152‐159, 2012     

Cell Decompositions of the Projective Plane with Petrie Polygons of Constant Length

We study dual pairs of combinatorial face-to-face cell decompositions of the real projective plane P ² such that their canonically induced cell decompositions on the 2-sphere S ² form dual pairs of combinatorical types of convex polyhedra, and such that these dual pairs share two natural properties with those induced by dual pairs of Platonic solids: (1) Every Petrie polygon is a finite simple closed polygon of length 2(n-1) for some fixed n. (2) Every pair of Petrie polygons has precisely two common edges. Such pairs of face-to-face cell decompositions of the projective plane are in one-to-one correspondence with n-element pseudoline arrangements. We study in particular those dual pairs of cell decompositions in which has only 3-valent vertices, i.e., via the above one-to-one correspondence: p ₃-maximal pseudoline arrangements. A p ₃ -maximal pseudoline arrangement with n elements in turn determines a neighborly 2-manifold with Euler characteristic χ = n(7-n)/6, and vice versa, this neighborly 2-manifold uniquely determines its generating p ₃ -maximal pseudoline arrangement. We provide new inductive constructions for finding infinite example classes of p ₃-maximal pseudoline arrangements from small existing ones, we describe an algorithm for generating them, we provide a complete list of existence up to n = 40, and we discuss their properties. Received July 18, 1996, and in revised form October 28, 1996.     

Oriented matroids and complete-graph embeddings on surfaces

We provide a link between topological graph theory and pseudoline arrangements from the theory of oriented matroids. We investigate and generalize a function f that assigns to each simple pseudoline arrangement with an even number of elements a pair of complete-graph embeddings on a surface. Each element of the pair keeps the information of the oriented matroid we started with. We call a simple pseudoline arrangement triangular, when the cells in the cell decomposition of the projective plane are 2-colorable and when one color class of cells consists of triangles only. Precisely for triangular pseudoline arrangements, one element of the image pair of f is a triangular complete-graph embedding on a surface. We obtain all triangular complete-graph embeddings on surfaces this way, when we extend the definition of triangular complete pseudoline arrangements in a natural way to that of triangular curve arrangements on surfaces in which each pair of curves has a point in common where they cross. Thus Ringel's results on the triangular complete-graph embeddings can be interpreted as results on curve arrangements on surfaces. Furthermore, we establish the relationship between 2-colorable curve arrangements and Petrie dual maps. A data structure, called intersection pattern is provided for the study of curve arrangements on surfaces. Finally we show that an orientable surface of genus g admits a complete curve arrangement with at most 2g+1 curves in contrast to the non-orientable surface where the number of curves is not bounded.     

Twisted honeycombs {3, 5, 3} t and their groups

A honeycomb of type {3, 5, 3} is finite when it has Petrie polygons of length 4, 6, 7 or 9. In these cases its group of automorphisms is isomorphic to PSL(2, 9), PSL(2, 11)×₂, PSL(2, 29) or PSL(2, 19). Its edges and faces are incident in a manner indicated by the vertices of a bipartite graph of girth 8 (in the first case) or 10, whose group is PGL(2, 9), PGL(2, 11)×₂, PSL(2, 29)×₂ or PGL(2, 19), respectively.     

Realizing finite edge‐transitive orientable maps

J.E. Graver and M.E. Watkins, Memoirs Am. Math. Soc. 126 (601) ( 5 ) established that the automorphism group of an edge‐transitive, locally finite map manifests one of exactly 14 algebraically consistent combinations (called types) of the kinds of stabilizers of its edges, its vertices, its faces, and its Petrie walks. Exactly eight of these types are realized by infinite, locally finite maps in the plane. H.S.M. Coxeter (Regular Polytopes, 2nd ed., McMillan, New York, 1963) had previously observed that the nine finite edge‐transitive planar maps realize three of the eight planar types. In the present work, we show that for each of the 14 types and each integer n ≥ 11 such that n ≡ 3,11 (mod 12), there exist finite, orientable, edge‐transitive maps whose various stabilizers conform to the given type and whose automorphism groups are (abstractly) isomorphic to the symmetric group Sym(n). Exactly seven of these types (not a subset of the planar eight) are shown to admit infinite families of finite, edge‐transitive maps on the torus, and their automorphism groups are determined explicitly. Thus all finite, edge‐transitive toroidal maps are classified according to this schema. Finally, it is shown that exactly one of the 14 types can be realized as an abelian group of an edge‐transitive map, namely, as ?_n × ?₂ where n ≡ 2 (mod 4). © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 1–34, 2001     

基于离散网格的流形曲面构造综述

基于离散网格的流形曲面构造技术不仅能够生成具有高阶光滑性的曲面,并且该曲面可以是任意拓扑结构的.此外,在构造流形曲面时,无需进行额外的拼接操作,克服了传统曲面造型技术在进行面片之间的拼接时,计算量增大以及曲面光滑性难以保证的难题.本文介绍了流形曲面构造的流程以及构造过程中的难点,然后将目前已有的流形曲面构造技术分为三大类:传统意义上的流形构造方法;基于规范区域的流形构造方法;基于样条曲面推广的流形构造方法.并对每一类都进行详细地分类介绍.最后,对其作一个总结以及对未来的展望.     

Construction heuristics for the asymmetric TSP

Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Euclidean TSP construction heuristics. This state of affairs is at odds with the fact that asymmetric models are relevant to a wider range of applications, and indeed are uniformly more general that symmetric models. Moreover, common construction approaches for the Euclidean TSP have been shown to produce poor quality solutions for non-Euclidean instances. Motivation for remedying this gap in the study of construction approaches is increased by the fact that such methods are a great deal faster than other TSP heuristics, which can be important for real time problems requiring continuously updated response. The purpose of this paper is to describe two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two. Extensive computational experiments are performed for several different families of TSP instances, disclosing that our combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.     

The construction of extensible polynomial lattice rules with small weighted star discrepancy

In this paper we introduce a construction algorithm for extensible polynomial lattice rules and we prove that the construction algorithm yields generating vectors of polynomials which are optimal for a range of moduli chosen in advance. The construction algorithm uses a sieve where the generating vectors are extended by one coefficient in each component at each step and where one keeps a certain number of good ones and discards the rest. We also show that the construction can be done component by component.

     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

Lie Group Spectral Variational Integrators

We present a new class of high-order variational integrators on Lie groups. We show that these integrators are symplectic and momentum-preserving, can be constructed to be of arbitrarily high order, or can be made to converge geometrically. Furthermore, these methods are capable of taking very large time-steps. We demonstrate the construction of one such variational integrator for the rigid body and discuss how this construction could be generalized to other related Lie group problems. We close with several numerical examples which demonstrate our claims and discuss further extensions of our work.     

Generalized cardinal B-splines: Stability, linear independence, and appropriate scaling matrices

Generalized cardinal B-splines are defined as convolution products of characteristic functions of self-affine lattice tiles with respect to a given integer scaling matrix. By construction, these generalized splines are refinable functions with respect to the scaling matrix and therefore they can be used to define a multiresolution analysis and to construct a wavelet basis. In this paper, we study the stability and linear independence properties of the integer translates of these generalized spline functions. Moreover, we give a characterization of the scaling matrices to which the construction of the generalized spline functions can be applied.     

Takeuchi’s free Hopf algebra construction revisited

Takeuchi’s famous free Hopf algebra construction is analyzed from a categorical point of view, and so is the construction of the Hopf envelope of a bialgebra. Both constructions in fact can be described as compositions of well known and natural constructions. This way certain partially wrong perceptions of these constructions are clarified and their mutual relation is made precise. The construction of Hopf envelopes finally is shown to provide a construction of a Hopf coreflection of bialgebras by simple dualization. The results provided hold for any commutative von Neumann regular ring, not only for fields.