Recognizing graph theoretic properties with polynomial ideals
The electronic journal of combinatorics, Tome 17 (2010)
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.
@article{10_37236_386,
author = {Jes\'us A. De Loera and Christopher J. Hillar and Peter N. Malkin and Mohamed Omar},
title = {Recognizing graph theoretic properties with polynomial ideals},
journal = {The electronic journal of combinatorics},
year = {2010},
volume = {17},
doi = {10.37236/386},
zbl = {1210.05059},
url = {http://geodesic.mathdoc.fr/articles/10.37236/386/}
}
TY - JOUR AU - Jesús A. De Loera AU - Christopher J. Hillar AU - Peter N. Malkin AU - Mohamed Omar TI - Recognizing graph theoretic properties with polynomial ideals JO - The electronic journal of combinatorics PY - 2010 VL - 17 UR - http://geodesic.mathdoc.fr/articles/10.37236/386/ DO - 10.37236/386 ID - 10_37236_386 ER -
%0 Journal Article %A Jesús A. De Loera %A Christopher J. Hillar %A Peter N. Malkin %A Mohamed Omar %T Recognizing graph theoretic properties with polynomial ideals %J The electronic journal of combinatorics %D 2010 %V 17 %U http://geodesic.mathdoc.fr/articles/10.37236/386/ %R 10.37236/386 %F 10_37236_386
Jesús A. De Loera; Christopher J. Hillar; Peter N. Malkin; Mohamed Omar. Recognizing graph theoretic properties with polynomial ideals. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/386
Cité par Sources :