====== Amanda Ruiz (Binghamton) ====== ===== Abstracts for the Combinatorics Seminar 2011 July 7-8 ===== These two talks constitute Ms. Ruiz's candidacy examination. The committee members are Laura Anderson (chair), Marcin Mazur, and Thomas Zaslavsky. ====== Final Polynomials and Nonrealizability of Oriented Matroids ====== ===== 2011 July 7 ===== 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. ====== An Explicit Construction of Final Polynomials for Non-Euclidean Oriented Matroids ====== ===== 2011 July 8 ===== 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". ----