Complexity questions in combinatorial geometry (I+II)

By Jürgen Richter-Gebert

These two talks focus on different aspects of the ``realizability problem'' for oriented matroids. Oriented matroids form a fundamental structure in combinatorial geometry that generalizes the notion of ``relative position'' in linear vector spaces. Every finite point configuration P in R^d leads to a corresponding oriented matroid M_P . The realizability problem asks the for the opposite: ``Given an oriented matroid M: If there is a configuration P with M_P = M then find one, otherwise prove non-realizability.'' The fundamental importance of the realizability problem comes from the fact that many representation problems of combinatorial geometry (polyhedral representability, line arrangements, etc.) can be translated into corresponding problems for oriented matroids.

PART I: Here we introduce several strategies that have been useful for finding realizations, or non-realizability proofs if a specific oriented matroid is given. In particular we introduce coordinate solvability sequences and point solvability sequences for proving realizability, and bi-quadratic final polynomials for proving non-realizability.

PART II: The realizability problem for oriented matroids is known to be NP-hard. This is a particular consequence of Mnëv's famous ``Universality Theorem''. It is the aim of this second talk to present a relatively short proof of this theorem. Furthermore we will prove that the related problem ``orientablity of matoids'' is NP-complete.