Recognizing Graph Theoretic Properties with Polynomial Ideals

Authors

Jesus A. De Loera, University of California - Davis
Christopher J. HIllar, Mathematical Sciences Research Institute
Peter N. Malkin, University of California - Davis
Mohamed Omar, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

2010

Abstract

Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect k-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Gröbner bases, toric algebra, convex programming, and real algebraic geometry.

Comments

First published in The Electronic Journal of Combinatorics.

Rights Information

© 2010 Jesús A. De Loera, Christopher J. Hillar, Peter N. Malkin, Mohamed Omar

Recommended Citation

De Loera, J., Hillar, C., Malkin, P., and Omar, M. Recognizing Graph Theoretic Properties with Polynomial Ideals., Electronic Journal of Combinatorics. Vol 17, R114 (2010).