On contractible polyhedra that are not simply contractible

In answer to a question of Michael, Dydak, Segal and Spiez have constructed a contractible polyhedron that is not strictly contractible. In the present note we prove a related result; by using alternative methods we show that there exist contractible polyhedra that are not simply (hence not strictly) contractible.

     

Spherical coxeter groups and hyperelliptic 3-manifolds

Reflection groups of Coxeter polyhedra in three-dimensional Thurston geometries are examined. For a wide class of Coxeter groups, the existence of subgroups of finite index that uniformize hyperelliptic 3-manifolds is established. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 173–177, August, 1999.     

On transformations of special spines and special polyhedra

Special spines of 3-manifolds and special polyhedra are examined. Special transformations of spines and polyhedra are considered. Two triangulations of the same 3-manifold are known to have a common stellar subdivision, and two Heegaard splittings of the same 3-manifold are stably equivalent. We prove similar assertions for spines and polyhedra. Spines with the structure of a branched surface are studied. Translated fromMatematicheskie Zametki, Vol. 65, No. 3, pp. 354–361, March, 1999.     

Connected cubic <Emphasis Type="Italic">s</Emphasis>-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two sufficient and necessary conditions for such graphs to be 1- or 2-arcregular are given and based on the conditions, several infinite families of 1- or 2-arc-regular cubic Cayley graphs of alternating groups are constructed. This work was supported by Guangxi Science Foundations (Grant No. 0832054) and Guangxi Postgraduate Education Innovation Research (Grant No. 2008105930701M102)     

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

It has widely been recognized that submodular set functions and base polyhedra associated with them play fundamental and important roles in combinatorial optimization problems. In the present paper, we introduce a generalized concept of base polyhedron. We consider a class of pointed convex polyhedra in R^V whose edge vectors have supports of size at most 2. We call such a convex polyhedron a polybasic polyhedron. The class of polybasic polyhedra includes ordinary base polyhedra, submodular/supermodular polyhedra, generalized polymatroids, bisubmodular polyhedra, polybasic zonotopes, boundary polyhedra of flows in generalized networks, etc. We show that for a pointed polyhedron PR^V, the following three statements are equivalent:

(1) P is a polybasic polyhedron.

(2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes.

(3) The support function of P is a submodular function on each orthant of R^V.

This reveals the geometric structure of polybasic polyhedra and its relation to submodularity.     

On octahedral fulleroids

The discovery of the first fullerene has raised an interest in the study of other candidates for modelling of carbon molecules. As a generalization of the fullerenes, fulleroids are defined as cubic convex polyhedra with all the faces of size five or greater. In this paper, we give necessary and sufficient condition for the existence of fulleroids with only pentagonal and n-gonal faces and with the symmetry group isomorphic to the full symmetry group of the regular octahedron. The existence is proved by finding infinite series of examples. The nonexistence is proved using symmetry invariants.     

Recognizability of finite simple groups <Emphasis Type="Italic">L</Emphasis><Subscript>4</Subscript>(2<Superscript>m</Superscript>) and <Emphasis Type="Italic">U</Emphasis><Subscript>4</Subscript>(2<Superscript>m</Superscript>) by spectrum

It is proved that finite simple groups L₄(2^m), m ⩾ 2, and U₄(2^m), m ⩾ 2, are, up to isomorphism, recognized by spectra, i.e., sets of their element orders, in the class of finite groups. As a consequence the question on recognizability by spectrum is settled for all finite simple groups without elements of order 8. Supported by RFBR (grant Nos. 05-01-00797 and 06-01-39001), by SB RAS (Complex Integration project No. 1.2), and by the Ministry of Education of China (Project for Retaining Foreign Expert). Supported by NSF of Chongqing (CSTC: 2005BB8096). __________ Translated from Algebra i Logika, Vol. 47, No. 1, pp. 83–93, January–February, 2008.     

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).     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

On an Elementary Proof of Rivin's Characterization of Convex Ideal Hyperbolic Polyhedra by their Dihedral Angles

In 1832, Jakob Steiner (Systematische Entwicklung der Abhängigkeit geometrischer Gestalten von einander, Reimer (Berlin)) asked for a characterization of those planar graphs which are combinatorially equivalent to polyhedra inscribed in the sphere. This question was answered in the 1990s by Igor Rivin (Ann. of Math.143(1996), 51–70), as a byproduct of his classification of ideal polyhedra in hyperbolic 3-space. Rivin also proposed a more direct approach to these results in Rivin (Ann. of Math.139 (1994), 553–580). In this paper, we prove a combinatorial result (Theorem 6) which enables one to complete the program of Rivin (Ann. Math.139(1994), 553–580).     

Almost simple groups with socle 3D4(q) act on finite linear spaces

After the classification of flag-transitive linear spaces, attention has now turned to line-transitive linear spaces. Such spaces are first divided into the point-imprimitive and the point-primitive, the first class is usually easy by the theorem of Delandtsheer and Doyen. The primitive ones are now subdivided, according to the O’Nan-Scotte theorem and some further work by Camina, into the socles which are an elementary abelian or non-abelian simple. In this paper, we consider the latter. Namely, T ≤ G ≤ Aut(T) and G acts line-transitively on finite linear spaces, where T is a non-abelian simple. We obtain some useful lemmas. In particular, we prove that when T is isomorphic to ³ D ₄(q), then T is line-transitive, where q is a power of the prime p.     

Recognition by spectrum for finite simple linear groups of small dimensions over fields of characteristic 2

Two groups are said to be isospectral if they share the same set of element orders. For every finite simple linear group L of dimension n over an arbitrary field of characteristic 2, we prove that any finite group G isospectral to L is isomorphic to an automorphic extension of L. An explicit formula is derived for the number of isomorphism classes of finite groups that are isospectral to L. This account is a continuation of the second author's previous paper where a similar result was established for finite simple linear groups L in a sufficiently large dimension (n > 26), and so here we confine ourselves to groups of dimension at most 26. Supported by RFBR (project Nos. 08-01-00322 and 06-01-39001), by SB RAS (Integration Project No. 2006.1.2), and by the Council for Grants (under RF President) and State Aid of Leading Scientific Schools (grant NSh-344.2008.1) and Young Doctors and Candidates of Science (grants MD-2848.2007.1 and MK-377.2008.1). Translated from Algebra i Logika, Vol. 47, No. 5, pp. 558–570, September–October, 2008.     

Regular Polyhedra With Translational Symmetries

In this note we present a group theoretical approach to polyhedra with a translation subgroup in their automorphism group.     

Monohedral Idemvalent Polyhedra that are Toroids

In this article we describe polyhedra of genus one that satisfy the following two properties: They have all faces congruent (monohedral) and they have the same number of faces at each vertex (idemvalent). In particular, the construction given yields polyhedra with six congruent triangles at each vertex. The construction given is a generalization of one given half a century ago by Alaoglu and Giese, and leads to many interesting toroidal polyhedra. We end by showing how the construction can yield a monohedral idemvalent toroidal polyhedron that is knotted.     

Effectively and Noneffectively Nowhere Simple Sets

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ? of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ?*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ?*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ?*. Mathematics Subject Classification: 03D25, 03D10.     

Cubic graphical regular representations of finite non-abelian simple groups

Given a finite group R, a graphical regular representation of R is a Cayley graph Γ over R with R = Aut(Γ). In this paper we study graphical regular representations of finite non-abelian simple groups of small valency.     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

The distance of a subdivision surface to its control polyhedron

For standard subdivision algorithms and generic input data, near an extraordinary point the distance from the limit surface to the control polyhedron after m subdivision steps is shown to decay dominated by the mth power of the subsubdominant (third largest) eigenvalue. Conversely, for Loop subdivision we exhibit generic input data so that the Hausdorff distance at the mth step is greater than or equal to the mth power of the subsubdominant eigenvalue.In practice, it is important to closely predict the number of subdivision steps necessary so that the control polyhedron approximates the surface to within a fixed distance. Based on the above analysis, two such predictions are evaluated. The first is a popular heuristic that analyzes the distance only for control points and not for the facets of the control polyhedron. For a set of test polyhedra this prediction is remarkably close to the true distance. However, a concrete example shows that the prediction is not safe but can prescribe too few steps. The second approach is to first locally, per vertex neighborhood, subdivide the input net and then apply tabulated bounds on the eigenfunctions of the subdivision algorithm. This yields always safe predictions that are within one step for a set of typical test surfaces.     

Extended formulations for radial cones

This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.     

On difference between the spectra of the simple groups Bn(q) and Cn(q)

We prove that the nonisomorphic simple groups B _n (q) and C _n (q) have different sets of element orders. Original Russian Text Copyright ? 2007 Grechkoseeva M. A. __________ Translated from Sibirskiĭ Matematicheskiĭ Zhurnal, Vol. 48, No. 1, pp. 89–92, January–February, 2007.