These two talks constitute Ms. Ruiz's candidacy examination. The committee members are Laura Anderson (chair), Marcin Mazur, and Thomas Zaslavsky.
Deciding whether or not a given oriented matroid is realizable is known to be NP-hard, but it is an important problem in oriented matroid theory to find algorithms to determine realizability. A final polynomial for an oriented matroids is a polynomial that proves its nonrealizability. I will introduce final polynomials and discuss how a "real Nullstellensatz" guarantees their existence for nonrealizable oriented matroids.
This talk is based on the paper "Nonrealizability proofs in computational geometry" by Jürgen Bokowski, Jürgen Richter, and Bernd Sturmfels.
This is a continuation of my previous talk. I will narrow the consideration to non-Euclidean oriented matroids, which are strange and interesting for a number of reasons, one being that we can explicitly construct final polynomials for them. I will describe how Fukuda's characterization of Euclidean oriented matroids in terms of linear programming translates into a construction method for final polynomials.
This talk is based on Jürgen Richter-Gebert's paper "Euclideaness [sic] and final polynomials in oriented matroid theory".