Applications of Convex and Algebraic Geometry to Graphs & PolytopesAlgebra & Discrete Mathematics
|Speaker:||Mohamed Omar, UC Davis|
|Start time:||Thu, May 26 2011, 4:10PM|
We explore the application of nonlinear algebraic tools to problems on graphs and polytopes. We begin by exploring the use of systems of polynomial equations to makes steps toward an algebraic obstruction theory for some classical combinatorial properties: k-colorability in graphs, unique Hamiltonicity, and graphs having a trivial automorphism group. We then study the convex geometry of permutation polytopes - convex hulls of permutation matrices. We find volumes by computing unimodular triangulations and Ehrhart polynomials, particularly illuminating the beautiful symmetry afforded from their intrinsic group structure. Finally, we explore the foundational algebraic underpinnings of the theta body hierarchy of Gouveia, Parrilo and Thomas, extending their results and providing an algebraic characterization for nonnegativity on real varieties.