| The concept of oriented matroid is a combinatorial abstraction of many geometric objects such as hyperplane arrangements. The problem to decide whether an oriented matroid has a geometric realization or not is called the realizability problem. This is a fundamental problem in the oriented matroid theory, and many important issues in combinatorial geometry such as stretchability of pseudoline arrangements [4] can be reduced to this problem. The realizability problem is known to be NP-hard [12] and there are many realizability certificates and non-realizability certificates based on sufficient conditions which can be checked efficiently. However, they cannot decide the realizability of all oriented matroids. Therefore new certificates are needed to determine the realizability of those that cannot be decided by existing methods. In this paper, we propose a new certificate for non-realizability of oriented matroids based on semidefinite programming relaxation of Grassmann-Plüker relations, and apply our method to oriented matroids with 8 elements and rank 4, and 9 elements and rank 3. |
|
