This thesis explores the application of nonlinear algebraic tools to problems on graphs and polytopes. After providing an overview of the thesis in Chapter 1, we begin our study in Chapter 2 by exploring the use of systems of polynomial equations to model computationally hard graph theoretic problems. We show how the algorithmic theory behind solving polynomial systems can be used to detect classical combinatorial properties: k-colorability in graphs, unique Hamiltonicity, and graphs having a trivial automorphism group. Our algebraic tools are diverse and include Nullstellensatz certificates, linear algebra over finite fields, Grobner bases, toric algebra and real algebraic geometry. We also employ optimization tools, particularly linear and semidefinite programming.;In Chapter 3, we study the convex geometry of permutation polytopes, focusing on those associated to cyclic groups, dihedral groups, groups of automorphisms of tree graphs, and Frobenius groups. We find volumes by computing unimodular triangulations and Ehrhart polynomials. These are determined through the use of Grobner basis techniques and Gale duality. We also find convex semidefinite approximations to these objects by exploring applications of the theta body hierarchy to these polytopes.;After establishing in earlier chapters that theta bodies play an interesting role in combinatorial analysis, in Chapter 4, we explore their foundational algebraic structure. In particular, we investigate extensions of the theta body hierarchy to ideals that are not necessarily real radical. In doing this, we introduce the notion of strong nonnegativity on real varieties. This algebraic condition is more restrictive than nonnegativity, but holds for sums of squares. We show that strong negativity is equivalent to nonnegativity for nonsingular real varieties. Moreover, for singular varieties, we reprove and generalize earlier results of Gouveia and Netzer regarding the obstructions to convergence of the theta body hierarchy.
展开▼
