UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Applications of Convex and Algebraic Geometry to Graphs & Polytopes

Algebra & Discrete Mathematics

Speaker: Mohamed Omar, UC Davis
Location: 2212 MSB
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.