Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-25T09:51:04.407Z Has data issue: false hasContentIssue false
  • English
  • Français

Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz

Published online by Cambridge University Press:  01 July 2009

J. A. LOERA ,
J. LEE ,
S. MARGULIES  and
S. ONN
J. A. LOERA
Affiliation:
Department of Mathematics, University of California, Davis, California, USA (e-mail: [email protected])
J. LEE
Affiliation:
IBM T. J. Watson Research Center, Yorktown Heights, New York, USA (e-mail: [email protected])
S. MARGULIES
Affiliation:
Department of Computer Science, University of California, Davis, California, USA (e-mail: [email protected])
S. ONN
Affiliation:
Davidson Faculty of IE & M, Technion – Israel Institute of Technology, Haifa, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colourable, Hamiltonian, etc.) if and only if a related system of polynomial equations has a solution.

For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P = NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimum degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows.

In the first part of the paper, we show that the minimum degree of a Nullstellensatz certificate for the non-existence of a stable set of size greater than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set of G. In contrast, for non-3-colourability, we proved that the minimum degree of a Nullstellensatz certificate is at least four. Our efforts so far have only yielded graphs with Nullstellensatz certificates of precisely that degree.

In the second part of this paper, for the purpose of computation, we construct new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colourable subgraph. We include some applications to graph theory.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 4 , July 2009 , pp. 551 - 582
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. (1999) Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 7–29.CrossRefGoogle Scholar
[2]Alon, N. and Tarsi, M. (1992) Colorings and orientations of graphs. Combinatorica 12 125–134.CrossRefGoogle Scholar
[3]Babson, E., Onn, S. and Thomas, R. R. (2003) The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. Adv. Appl. Math. 30 529–544.CrossRefGoogle Scholar
[4]Bachoc, C. and Vallentin, F. (2008) New upper bounds for kissing numbers from semidefinite programming. J. Amer. Math. Soc. 21 909–924.CrossRefGoogle Scholar
[5]Bayer, D. A. (1982) The division algorithm and the Hilbert scheme. PhD thesis, Harvard University.Google Scholar
[6]Brownawell, W. D. (1987) Bounds for the degrees in the Nullstellensatz. Ann. of Math. 126 577–591.CrossRefGoogle Scholar
[7]Buss, S. and Pitassi, T. (1996) Good degree bounds on Nullstellensatz refutations of the induction principle. In IEEE Conference on Computational Complexity, pp. 233–242.CrossRefGoogle Scholar
[8]Chao, C.-Y. and Chen, Z. (1993) On uniquely 3-colorable graphs. Discrete Math. 112 374–383.CrossRefGoogle Scholar
[9]Cox, D., Little, J. and O'Shea, D. (1992) Ideals, Varieties and Algorithms, Springer Undergraduate Texts in Mathematics.CrossRefGoogle Scholar
[10]Cox, D., Little, J. and O'Shea, D. (1998) Using Algebraic Geometry, Springer Graduate Texts in Mathematics.CrossRefGoogle Scholar
[11]De Loera, J. A. (1995) Gröbner bases and graph colorings. Beitrage zur Algebra und Geometrie 36 89–96.Google Scholar
[12]de Klerk, E., Pasechnik, D. and Schrijver, A. (2007) Reduction of symmetric semidefinite programs using the regular *-representation. Math. Programm. Ser. B 109 613–624.CrossRefGoogle Scholar
[13]Dyer, M. and Greenhill, C. (2000) On Markov chains for independent sets. J. Algorithms 35 17–49.CrossRefGoogle Scholar
[14]Eliahou, S. (1992) An algebraic criterion for a graph to be four-colourable. In Aportaciones Matemáticas, Vol. 6 of Soc. Matemática Mexicana, Notas de Investigacion, pp. 3–27.Google Scholar
[15]Fischer, K. G. (1988) Symmetric polynomials and Hall's theorem. Discrete Math. 69 225–234.CrossRefGoogle Scholar
[16]Garey, M. and Johnson, D. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman.Google Scholar
[17]Hillar, C. J. and Windfeldt, T. (2008) An algebraic characterization of uniquely vertex colorable graphs. J. Combin. Theory Ser. B 98 400–414.CrossRefGoogle Scholar
[18]Impagliazzo, P., Pudlák, P. and Sgall, J. (1999) Lower bounds for polynomial calculus and the Groebner basis algorithm. Comput. Complexity 8 127–144.CrossRefGoogle Scholar
[19]Jin, G. (1995) Triangle-free four-chromatic graphs. Discrete Math. 145 151–170.CrossRefGoogle Scholar
[20]Kollár, J. (1988) Sharp effective Nullstellensatz. J. Amer. Math. Soc. 1 963–975.CrossRefGoogle Scholar
[21]Kreuzer, M. and Robbiano, L. (2000) Computational Commutative Algebra I, Springer, Heidelberg.CrossRefGoogle Scholar
[22]Lasserre, J. B. (2001) Polynomials nonnegative on a grid and discrete optimization. Trans. Amer. Math. Soc. 354 631–649.CrossRefGoogle Scholar
[23]Laurent, M. (2007) Semidefinite representations for finite varieties. Math. Programm. 109 1–26.CrossRefGoogle Scholar
[24]Laurent, M. and Rendl, F. (2005) Semidefinite programming and integer programming. In Handbook on Discrete Optimization (Aardal, K., Nemhauser, G. and Weismantel, R., eds), Elsevier, pp. 393–514.CrossRefGoogle Scholar
[25]Lazard, D. (1977) Algèbre linéaire sur [X 1,. . .,X n] et élimination. Bull. Soc. Math. France 105 165–190.CrossRefGoogle Scholar
[26]Li, S. R. and Li, W. W. (1981) Independence number of graphs and generators of ideals. Combinatorica 1 55–61.CrossRefGoogle Scholar
[27]Lovász, L. (1994) Stable sets and polynomials. Discrete Math. 124 137–153.CrossRefGoogle Scholar
[28]Lovász, L. (2002) Oberwolfach Meeting on Geometric Convex Combinatorics, Mathematisches Forschungsinstitut Oberwolfach, Germany, June 2002.Google Scholar
[29]Margulies, S. (2008) Computer algebra, combinatorics, and complexity: Hilbert's Nullstellensatz and NP-complete problems. PhD dissertation, UC Davis.Google Scholar
[30]Matiyasevich, Y. (1974) A criteria for colorability of vertices stated in terms of edge orientations (in Russian). Discrete Analysis (Novosibirsk) 26 65–71.Google Scholar
[31]Matiyasevich, Y. (2001) Some algebraic methods for calculation of the number of colorings of a graph (in Russian). Zapiski Nauchnykh Seminarov POMI 293 193–205 (available via www.pdmi.ras.ru).Google Scholar
[32]Mnuk, M. (2001) Representing graph properties by polynomial ideals. In Computer Algebra in Scientific Computing CASC 2001: Proc. Fourth International Workshop on Computer Algebra in Scientific Computing, Konstanz 2001 (Ganzha, V. G., Mayr, E. W. and Vorozhtsov, E. V., eds), Springer, pp. 431–444.CrossRefGoogle Scholar
[33]Onn, S. (2004) Nowhere-zero flow polynomials. J. Combin. Theory Ser. A 108 205–215.CrossRefGoogle Scholar
[34]Parrilo, P. (2002) An explicit construction of distinguished representations of polynomials nonnegative over finite sets. IfA Technical Report AUT02-02.Google Scholar
[35]Parrilo, P. (2003) Semidefinite programming relaxations for semialgebraic problems. Math. Programm. Ser. B 96 293–320.CrossRefGoogle Scholar
[36]Schnyder, W. (1989) Planar graphs and poset dimension, Order 5 323–343.CrossRefGoogle Scholar
[37]Schrijver, A. (1986) Theory of Linear and Integer Programming, Wiley InterScience Series in Discrete Mathematics and Optimization, Wiley, Chichester.Google Scholar
[38]Shauger, S. E. (1998) Results on the Erdős–Gyárfás conjecture in K 1,m-free graphs. In Proc. Twenty-ninth Southeastern International Conference on Combinatorics Graph Theory and Computing (Boca Raton, FL, 1998). Congr. Numer. 134 61–65.Google Scholar
[39]Simis, A., Vasconcelos, W. and Villarreal, R. (1994) On the ideal theory of graphs. J. Algebra 167 389–416.CrossRefGoogle Scholar
[40]Yannakakis, M. (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43 441–466.CrossRefGoogle Scholar