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

Richter, Jürgen; Sturmfels, Bernd

doi:10.1090/S0002-9947-1991-0994170-3

On the topology and geometric construction of oriented matroids and convex polytopes
HTML articles powered by AMS MathViewer

by Jürgen Richter and Bernd Sturmfels PDF

Trans. Amer. Math. Soc. 325 (1991), 389-412 Request permission

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

Noga Alon, The number of polytopes, configurations and real matroids, Mathematika 33 (1986), no. 1, 62–71. MR 859498, DOI 10.1112/S0025579300013875
Amos Altshuler and Ido Shemer, Construction theorems for polytopes, Israel J. Math. 47 (1984), no. 2-3, 99–110. MR 738161, DOI 10.1007/BF02760509
Robert G. Bland and Michel Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1978), no. 1, 94–123. MR 485461, DOI 10.1016/0095-8956(78)90080-1
Jürgen Bokowski, Aspects of computational synthetic geometry. II. Combinatorial complexes and their geometric realization—an algorithmic approach, Computer aided geometric reasoning, Vol. I, II (Sophia-Antipolis, 1987) INRIA, Rocquencourt, 1987, pp. 87–125. MR 921057
Jürgen Bokowski, Jürgen Richter, and Bernd Sturmfels, Nonrealizability proofs in computational geometry, Discrete Comput. Geom. 5 (1990), no. 4, 333–350. MR 1043715, DOI 10.1007/BF02187794
Jürgen Bokowski and Ido Shemer, Neighborly $6$-polytopes with $10$ vertices, Israel J. Math. 58 (1987), no. 1, 103–124. MR 889975, DOI 10.1007/BF02764673
Jürgen Bokowski and Bernd Sturmfels, On the coordinatization of oriented matroids, Discrete Comput. Geom. 1 (1986), no. 4, 293–306. MR 866365, DOI 10.1007/BF02187702
Jürgen Bokowski and Bernd Sturmfels, Polytopal and nonpolytopal spheres: an algorithmic approach, Israel J. Math. 57 (1987), no. 3, 257–271. MR 889977, DOI 10.1007/BF02766213
Jürgen Bokowski and Bernd Sturmfels, Reell realisierbare orientierte Matroide, Bayreuth. Math. Schr. 21 (1986), 1–13 (German). Diskrete Strukturen, algebraische Methoden und Anwendungen (Bayreuth, 1985). MR 864084
Raul Cordovil and Pierre Duchet, On sign-invariance graphs of uniform oriented matroids, Discrete Math. 79 (1990), no. 3, 251–257. MR 1044225, DOI 10.1016/0012-365X(90)90333-D

Oriented matroids and cyclic polytopes

Henry Crapo and Juliette Ryan, Réalisations spatiales des scènes linéaires, Structural Topology 13 (1986), 33–68. Dual French-English text. MR 880673
Andreas W. M. Dress, Chirotops and oriented matroids, Bayreuth. Math. Schr. 21 (1986), 14–68. Diskrete Strukturen, algebraische Methoden und Anwendungen (Bayreuth, 1985). MR 864085
Jon Folkman and Jim Lawrence, Oriented matroids, J. Combin. Theory Ser. B 25 (1978), no. 2, 199–236. MR 511992, DOI 10.1016/0095-8956(78)90039-4

Convex polytopes

Jacob E. Goodman and Richard Pollack, Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines, J. Combin. Theory Ser. A 29 (1980), no. 3, 385–390. MR 600606, DOI 10.1016/0097-3165(80)90038-2
Jacob E. Goodman and Richard Pollack, Upper bounds for configurations and polytopes in $\textbf {R}^d$, Discrete Comput. Geom. 1 (1986), no. 3, 219–227. MR 861891, DOI 10.1007/BF02187696

Zonotopal complexes on the

cube

Beat Jaggi, Peter Mani-Levitska, Bernd Sturmfels, and Neil White, Uniform oriented matroids without the isotopy property, Discrete Comput. Geom. 4 (1989), no. 2, 97–100. MR 973539, DOI 10.1007/BF02187717

On the number of ordinary lines determined by

points

10

Victor Klee and Peter Kleinschmidt, The $d$-step conjecture and its relatives, Math. Oper. Res. 12 (1987), no. 4, 718–755. MR 913867, DOI 10.1287/moor.12.4.718
Michel Las Vergnas, Convexity in oriented matroids, J. Combin. Theory Ser. B 29 (1980), no. 2, 231–243. MR 586435, DOI 10.1016/0095-8956(80)90082-9

Matroïdes orientables

280

Michel Las Vergnas, Order properties of lines in the plane and a conjecture of G. Ringel, J. Combin. Theory Ser. B 41 (1986), no. 2, 246–249. MR 859315, DOI 10.1016/0095-8956(86)90048-1

Extensions ponctuelles d’une géométrie combinatoire

Jim Lawrence, Oriented matroids and multiply ordered sets, Linear Algebra Appl. 48 (1982), 1–12. MR 683205, DOI 10.1016/0024-3795(82)90094-5
P. McMullen and G. C. Shephard, Convex polytopes and the upper bound conjecture, London Mathematical Society Lecture Note Series, vol. 3, Cambridge University Press, London-New York, 1971. Prepared in collaboration with J. E. Reeve and A. A. Ball. MR 0301635
N. E. Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, Topology and geometry—Rohlin Seminar, Lecture Notes in Math., vol. 1346, Springer, Berlin, 1988, pp. 527–543. MR 970093, DOI 10.1007/BFb0082792

Problemliste im Tagungsbericht Oberwolfach

Jürgen Richter, Kombinatorische Realisierbarkeitskriterien für orientierte Matroide, Mitt. Math. Sem. Giessen 194 (1989), 112 (German, with English summary). MR 1043138
Gerhard Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden, Math. Z. 64 (1955), 79–102 (1956) (German). MR 74817, DOI 10.1007/BF01166556
J.-P. Roudneff, Inseparability graphs of oriented matroids, Combinatorica 9 (1989), no. 1, 75–84. MR 1010302, DOI 10.1007/BF02122686

Matroides orientés et arrangements de pseudodroites

Jean-Pierre Roudneff and Bernd Sturmfels, Simplicial cells in arrangements and mutations of oriented matroids, Geom. Dedicata 27 (1988), no. 2, 153–170. MR 957597, DOI 10.1007/BF00151346
Ido Shemer, Neighborly polytopes, Israel J. Math. 43 (1982), no. 4, 291–314. MR 693351, DOI 10.1007/BF02761235
Edwin H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0210112
Ernst Steinitz and Hans Rademacher, Vorlesungen über die Theorie der Polyeder unter Einschluss der Elemente der Topologie, Grundlehren der Mathematischen Wissenschaften, No. 41, Springer-Verlag, Berlin-New York, 1976. Reprint der 1934 Auflage. MR 0430958
Bernd Sturmfels, Neighborly polytopes and oriented matroids, European J. Combin. 9 (1988), no. 6, 537–546. MR 970389, DOI 10.1016/S0195-6698(88)80050-7
Bernd Sturmfels, On the decidability of Diophantine problems in combinatorial geometry, Bull. Amer. Math. Soc. (N.S.) 17 (1987), no. 1, 121–124. MR 888886, DOI 10.1090/S0273-0979-1987-15532-7

Computational synthetic geometry

Cyclic polytopes and

order curves

14

A. M. Vershik, Topology of the convex polytopes’ manifolds, the manifold of the projective configurations of a given combinatorial type and representations of lattices, Topology and geometry—Rohlin Seminar, Lecture Notes in Math., vol. 1346, Springer, Berlin, 1988, pp. 557–581. MR 970095, DOI 10.1007/BFb0082794

A non-uniform oriented matroid which violates the isotopy property

4