Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the topology and geometric construction of oriented matroids and convex polytopes


Authors: Jürgen Richter and Bernd Sturmfels
Journal: Trans. Amer. Math. Soc. 325 (1991), 389-412
MSC: Primary 05B35; Secondary 52B12
DOI: https://doi.org/10.1090/S0002-9947-1991-0994170-3
MathSciNet review: 994170
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper develops new combinatorial and geometric techniques for studying the topology of the real semialgebraic variety $ \mathcal{R}(M)$ of all realizations of an oriented matroid $ M$ . We focus our attention on point configurations in general position, and as the main result we prove that the realization space of every uniform rank $ 3$ oriented matroid with up to eight points is contractible. For these special classes our theorem implies the isotopy property which states the spaces $ \mathcal{R}(M)$ are path-connected.

We further apply our methods to several related problems on convex polytopes and line arrangements. A geometric construction and the isotopy property are obtained for a large class of neighborly polytopes. We improve a result of M. Las Vergnas by constructing a smallest counterexample to a conjecture of G. Ringel, and, finally, we discuss the solution to a problem of R. Cordovil and P. Duchet on the realizability of cyclic matroid polytopes.


References [Enhancements On Off] (What's this?)

  • [1] N. Alon, The number of polytopes, configurations and real matroids, Mathematika 33 (1986), 62-71. MR 859498 (88c:05038)
  • [2] A. Altshuler and I. Shemer, Construction theorems for polytopes, Israel J. Math. 47 (1984), 99-110. MR 738161 (85e:52008)
  • [3] R. Bland and M. Las Vergnas, Orientability of matroids, J. Combin. Theory Ser. B 24 (1978), 94-123. MR 0485461 (58:5294)
  • [4] J. Bokowski, Aspects of computational synthetic geometry, II. Combinatorial complexes and their geometric realization, Presented at the Workshop on Computer-Aided Geometric Reasoning, INRIA, Antibes (France), June 1987. MR 921057 (89a:05050)
  • [5] J. Bokowski, J. Richter, and B. Sturmfels, Nonrealizability proofs in computational geometry, Discrete Comput. Geom. 5 (1990), 333-350. MR 1043715 (91d:68121)
  • [6] J. Bokowski and I. Shemer, Neighborly $ 6$-polytopes with ten vertices, Israel J. Math. 58 (1987), 103-124. MR 889975 (89b:52010)
  • [7] J. Bokowski and B. Sturmfels, On the coordinatization of oriented matroids, Discrete Comput. Geom. 1 (1986), 293-306. MR 866365 (88c:05040)
  • [8] -, Polytopal and non-polytopal spheres--An algorithmic approach, Israel J. Math. 57 (1987), 257-271. MR 889977 (89b:52009)
  • [9] -, Reell realisierbare orientierte Matroide, Bayreuth. Math. Sch. 21 (1986), 1-13. MR 864084 (88c:05041)
  • [10] R. Cordovil and P. Duchet, On sign-invariance graphs of uniform oriented matroids, Discrete Math. 79 (1989/90), 251-257. MR 1044225 (92a:05034)
  • [11] -, Oriented matroids and cyclic polytopes, Combinatorica (to appear).
  • [12] H. Crapo and J. Ryan, Spatial realizations of linear scenes, Structural Topology 13 (1986), 33-68. MR 880673 (88d:51017)
  • [13] A. Dress, Chirotops and oriented matroids, Bayreuth. Math. Sch. 21 (1986), 14-68. MR 864085 (87k:05049)
  • [14] J. Folkman and J. Lawrence, Oriented matroids, J. Combin. Theory Ser. B 25 (1978), 199-238. MR 511992 (81g:05045)
  • [15] B. Grünbaum, Convex polytopes, Interscience, London, 1967.
  • [16] E. Goodman and R. Pollack, Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines, J. Combin. Theory Ser. A 29 (1980), 385-390. MR 600606 (82m:05026)
  • [17] -, Upper bounds for configurations and polytopes in $ {R^d}$, Discrete Comput. Geom. 1 (1986), 219-227. MR 861891 (87k:52016)
  • [18] E. Halsey, Zonotopal complexes on the $ d$-cube, Ph.D. Dissertation, University of Washington, Seattle, 1971.
  • [19] B. Jaggi, P. Mani-Levitska, B. Sturmfels, and N. White, Uniform oriented matroids without the isotopy property, Discrete Comput. Geom. 4 (1989), 97-100. MR 973539 (89j:05028)
  • [20] K. M. Kelly and W. O. J. Moser, On the number of ordinary lines determined by $ n$ points, Canad. J. Math. 10 (1958), 210-219.
  • [21] V. Klee and P. Kleinschmidt, The $ d$-step conjecture and its relatives, Math. Oper. Res. 12 (1987), 718-755. MR 913867 (89a:52018)
  • [22] M. Las Vergnas, Convexity in oriented matroids, J. Combin. Theory Ser. B 29 (1980), 231-243. MR 586435 (82f:05027)
  • [23] -, Matroïdes orientables, C. R. Acad. Sci. Paris Sér. I Math. 280 (1975), 61-64.
  • [24] -, Order properties of lines in the plane and a conjecture of G. Ringel, J. Combin. Theory Ser. B 41 (1986), 246-249. MR 859315 (87k:52027)
  • [25] -, Extensions ponctuelles d'une géométrie combinatoire, Problèmes Combinatoires et Th. des Graphes, Actes Colloq. C.N.R.S., no. 260, Orsay, 1976.
  • [26] J. Lawrence, Oriented matroids and multiply ordered sets, Linear Algebra Appl. 48 (1982), 1-12. MR 683205 (84g:05046)
  • [27] P. McMullen and G. Shephard, Convex polytopes and the upper bound conjecture, London Math. Soc. Lecture Note Series, Vol. 3, Cambridge, 1971. MR 0301635 (46:791)
  • [28] N. E. Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, in Topology and Geometry--Rohlin Seminar (O. Y. Viro, ed.), Lecture Notes in Math., vol. 1346, Springer, Heidelberg, 1988, pp. 527-544. MR 970093 (90a:52013)
  • [29] R. Pollack, Problemliste im Tagungsbericht Oberwolfach, Tagung über kombinatorische Geometrie, September 1984.
  • [30] J. Richter, Kombinatorische Realisierbarkeitskriterien für orientierte Matroide, Diplomarbeit, Technische Hochschule Darmstadt, 1988. MR 1043138 (91d:05038)
  • [31] G. Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden, Math. Z. 64 (1956), 79-102. MR 0074817 (17:651g)
  • [32] J.-P. Roundneff, Inseparability graphs of oriented matroids, Combinatorica 9 (1989), 75-84. MR 1010302 (91a:05026)
  • [33] -, Matroides orientés et arrangements de pseudodroites, Thése der 3em cycle, Université Pierre et Marie Curie, Paris, 1986.
  • [34] J.-P. Roundneff and B. Sturmfels, Simplicial cells in arrangements and mutations of oriented matroids, Geom. Dedicata 27 (1988), 153-170. MR 957597 (89h:51037)
  • [35] I. Shemer, Neighborly polytopes, Israel J. Math. 43 (1982), 291-314. MR 693351 (84k:52008)
  • [36] E. H. Spanier, Algebraic topology, MacGraw-Hill, New York, 1966. MR 0210112 (35:1007)
  • [37] E. Steinitz and H. Rademacher, Vorlesungen über die Theorie der Polyeder, reprint, Springer-Verlag, Berlin, 1976. MR 0430958 (55:3962)
  • [38] B. Sturmfels, Neighborly polytopes and oriented matroids, European J. Combin. 9 (1988), 537-546. MR 970389 (89j:52005)
  • [39] -, On the decidability of diophantine problems in combinatorial geometry, Bull. Amer. Math. Soc. (N.S.) 17 (1987), 121-124. MR 888886 (88m:52010)
  • [40] -, Computational synthetic geometry, Ph.D. Dissertation, University of Washington, Seattle, 1987.
  • [41] -, Cyclic polytopes and $ d$-order curves, Geom. Dedicata 14 (1987), 103-107.
  • [42] A. M. Vershik, Topology of the convex polytopes' manifold, the manifold of projective configurations of a given combinatorial type and representations of lattices, in Topology and Geometry--Rohlin Seminar (O. Y. Viro, ed.), Lecture Notes in Math., vol. 1346, Springer, Heidelberg, 1988, pp. 557-581. MR 970095 (90d:52007)
  • [43] N. White, A non-uniform oriented matroid which violates the isotopy property, Discrete Comput. Geom. 4 (1989), 1-2.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B35, 52B12

Retrieve articles in all journals with MSC: 05B35, 52B12


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1991-0994170-3
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society