Spatial polyhedra without diagonals

We provide new polyhedra without diagonals, and we discuss their embeddings in euclidean 3-space with maximal symmetries starting with a complete classification of their combinatorial properties: orientable neighborly 2-pseudomanifolds with 9 vertices or Mendelsohn triple systemsS ₂(2, 3, 9). This article was motivated by the longstanding and still open question: find a triangulated 2-manifold which can not be embedded in 3-space. Furthermore, we applied tested and improved algorithms for realizing oriented matroids or finding final polynomials.     

Nonrealizable Minimal Vertex Triangulations of Surfaces: Showing Nonrealizability Using Oriented Matroids and Satisfiability Solvers

We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in ℝ³. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. Correcting a previous error in the literature, we construct the first infinite family of such nonrealizable triangulations of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e.g., for face lattices of polytopes.     

Matroid Enumeration for Incidence Geometry

Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity, but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm the conjectures of Welsh–Seymour on ≤11 points in ℝ³ and that of Motzkin on ≤12 lines in ℝ², extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability (SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids.     

The Graph of Triangulations of a Point Configuration with d +4 Vertices Is 3-Connected

We study the graph of bistellar flips between triangulations of a vector configuration A with d+4 elements in rank d+1 (i.e. with corank 3), as a step in the Baues problem. We prove that the graph is connected in general and 3-connected for acyclic vector configurations, which include all point configurations of dimension d with d+4 elements. Hence, every pair of triangulations can be joined by a finite sequence of bistellar flips and, in the acyclic case, every triangulation has at least three geometric bistellar neighbours. In corank 4, connectivity is not known and having at least four flips is false. In corank 2, the results are trivial since the graph is a cycle. Our methods are based on a dualization of the concept of triangulation of a point or vector configuration A to that of a virtual chamber of its Gale transform B , introduced by de Loera et al. in 1996. As an additional result we prove a topological representation theorem for virtual chambers, stating that every virtual chamber of a rank 3 vector configuration B can be realized as a cell in some pseudo-chamber complex of B in the same way that regular triangulations appear as cells in the usual chamber complex. All the results in this paper generalize to triangulations of corank 3 oriented matroids and virtual chambers of rank 3 oriented matroids, realizable or not. The details for this generalization are given in the Appendix. Received March 1, 1999, and in revised form September 7, 1999.     

Optimal 1-planar graphs which triangulate other surfaces

We show that, for any given non-spherical orientable closed surface F², there exists an optimal 1-planar graph which can be embedded on F² as a triangulation. On the other hand, we prove that there does not exist any such graph for the nonorientable closed surfaces of genus at most 3.     

The computational complexity of basic decision problems in 3-dimensional topology

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.      

No optimal 1‐planar graph triangulates any nonorientable closed surface

Suzuki [Discrete Math. 310 (2010), 6–11] proved that for any orientable closed surface F² other than the sphere, there exists an optimal 1‐planar graph which can be embedded on F² as a triangulation. However, for nonorientable closed surfaces, the existence of such graphs is unknown. In this article, we prove that no optimal 1‐planar graph triangulates a nonorientable closed surface.     

On foliated circle bundles over closed orientable 3-manifolds

We show that there exists a family of smooth orientable circle bundles over closed orientable 3-manifolds each of which has a codimension-one foliation transverse to the fibres of class C ⁰ but has none of class C ³ . There arises a necessary condition induced from the Milnor-Wood inequality for the existence of a foliation transverse to the fibres of an orientable circle bundle over a closed orientable 3-manifold. We show that with some exceptions this necessary condition is also sufficient for the existence of a smooth transverse foliation if the base space is a closed Seifert fibred manifold. Received: May 13, 1996     

A Note on Geometric Embeddings of Simplicial Complexes in a Euclidean Space

In this note we prove that if a simplicial complex K can be embedded geometrically in R ^m , then a certain linear system of equations associated with K possesses a small integral solution. Received July 5, 1998, and in revised form May13, 1999.     

Generating Quadratic Pseudo-Anosov Homeomorphisms of Closed Surfaces

In this note, we show that given a closed, orientable genus-g surface S _g , any hyperbolic toral automorphism has a positive power which induces a quadratic, orientable pseudo-Anosov homeomorphism on S _g . To show this, we lift Anosov toral automorphisms through a ramified topological covering and present the lifted homeomorphism via a standard set of Lickorish twists. This construction provides a general method of producing pseudo-Anosov maps of closed surfaces with predetermined orientable foliations and quadratic dilatation. Since these lifted automorphisms have orientable foliations, this construction is a sort of converse to that of Franks and Rykken [Trans. Amer. Math. Soc. 1999], who established that one can associate to a quadratic pseudo-Anosov homeomorphism with oriented unstable foliation a hyperbolic toral automorphism.     

Geodesic knots in closed hyperbolic 3-manifolds

We consider the existence of simple closed geodesics or “geodesic knots” in finite volume orientable hyperbolic 3-manifolds. Every such manifold contains at least one geodesic knot by results of Adams, Hass and Scott in (Adams et al. Bull. London Math. Soc. 31: 81–86, 1999). In (Kuhlmann Algebr. Geom. Topol. 6: 2151–2162, 2006) we showed that every cusped orientable hyperbolic 3-manifold in fact contains infinitely many geodesic knots. In this paper we consider the closed manifold case, and show that if a closed orientable hyperbolic 3-manifold satisfies certain geometric and arithmetic conditions, then it contains infinitely many geodesic knots. The conditions on the manifold can be checked computationally, and have been verified for many manifolds in the Hodgson-Weeks census of closed hyperbolic 3-manifolds. Our proof is constructive, and the infinite family of geodesic knots spiral around a short simple closed geodesic in the manifold.      

Homotopy types of line arrangements

Summary We prove that the complement of a real affine line arrangement inC ² is homotopy equivalent to the canonical 2-complex associated with Randell's presentation of the fundamental group. This provides a much smaller model for the homotopy type of the complement of a real affine 2- or central 3-arrangement than the Salvetti complex and its cousins. As an application we prove that these exist (infinitely many) pairs of central arrangements inC ³ with different underlying matroids whose complements are homotopy equivalent. We also show that two real 3-arrangements whose oriented matroids are connected by a sequence of flips are homotopy equivalent.Oblatum 17-X-1991 & 8-VII-1992Author partially supported by NSF grant DMS-9004202     

Computing Matveev’s Complexity via Crystallization Theory: The Orientable Case

By means of a slight modification of the notion of GM-complexity introduced in [Casali, M.R., Topol. Its Appl., 144: 201–209, 2004], the present paper performs a graph-theoretical approach to the computation of (Matveev’s) complexity for closed orientable 3-manifolds. In particular, the existing crystallization catalogue available in [Lins, S., Knots and Everything 5, World Scientific, Singapore, 1995] is used to obtain upper bounds for the complexity of closed orientable 3-manifolds triangulated by at most 28 tetrahedra. The experimental results actually coincide with the exact values of complexity, for all but three elements. Moreover, in the case of at most 26 tetrahedra, the exact value of the complexity is shown to be always directly computable via crystallization theory.     

Orientability of matroids

In this paper we define oriented matroids and develop their fundamental properties, which lead to generalizations of known results concerning directed graphs, convex polytopes, and linear programming. Duals and minors of oriented matroids are defined. It is shown that every coordinatization (representation) of a matroid over an ordered field induces an orientation of the matroid. Examples of matroids that are orientable but not coordinatizable and of matroids that are not orientable are presented. We show that a binary matroid is orientable if and only if it is unimodular (regular), and that every unimodular matroid has an orientation that is induced by a coordinatization and is unique in a certain straightforward sense.     

Bounds for Generalized Thrackles

A thrackle (resp. generalized thrackle) is a drawing of a graph in which each pair of edges meets precisely once (resp. an odd number of times). For a graph with n vertices and m edges, we show that, for drawings in the plane, m≤ (2/3)(n-1) for thrackles, while m≤ 2n-2 for generalized thrackles. This improves theorems of Lovász, Pach, and Szegedy. The paper also examines thrackles in the more general setting of drawings on closed surfaces. The main result is: a bipartite graph G can be drawn as a generalized thrackle on a closed orientable connected surface if and only if G can be embedded in that surface. Received July 23, 1998, and in revised form January 1, 1999.     

Cyclic branched coverings of some pretzel links

We construct infinite families of closed connected orientable 3-manifolds obtained from certain triangulated 3-cells by pairwise identifications of their boundary faces. Our combinatorial constructions extend and complete a particular polyhedral scheme which Kim and Kostrikin used in [10] and [11] to define a series of spaces denoted M ₃(n). Then we determine geometric presentations of the fundamental groups, and prove that many of the constructed manifolds are n-fold (non-strongly) cyclic coverings of the ³-sphere branched over some specified pretzel links.     

On the orientable genus of graphs embedded in the klein bottle

Let G be a graph embedded in the Klein bottle with “representativity” at least four. We give a formula for the orientable genus of G, which also implies a polynomially bounded algorithm. The formula is in terms of the number of times certain closed curves on the Klein bottle intersect the graph. In particular, it shows that a cut-and-paste technique for re-embedding graphs is the best possible.     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

Mutation Polynomials and Oriented Matroids

Several polynomials are of use in various enumeration problems concerning objects in oriented matroids. Chief among these is the Radon catalog. We continue to study these, as well as the total polynomials of uniform oriented matroids, by considering the effect on them of mutations of the uniform oriented matroid. The notion of a ``mutation polynomial' is introduced to facilitate the study. The affine spans of the Radon catalogs and the total polynomials in the appropriate rational vector spaces of polynomials are determined, and bases for the Z -modules generated by the mutation polynomials are found. The Radon polynomials associated with alternating oriented matroids are described; it is conjectured that a certain extremal property, like that held by cyclic polytopes among simplicial polytopes, is possessed by them. Received November 20, 1998, and in revised form August 21, 1999. Online publication May 19, 2000.