Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Recognizing Graph Theoretic Properties with Polynomial Ideals. | Recognizing Graph Theoretic Properties with Polynomial Ideals Jesus A. De Loera University of California Davis Davis CA 95616 deloera@ Christopher J. Hillar Mathematical Sciences Research Institute Berkeley CA 94120 chillar@ Peter N. Malkin University of California Davis Davis CA 95616 malkin@ Mohamed OmaA University of California Davis Davis CA 95616 momar@ Submitted Mar 10 2010 Accepted Jul 15 2010 Published Aug 16 2010 Mathematics Subject Classification 05C25 05E40 52B55 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 Grobner bases toric algebra convex programming and real algebraic geometry. 1The first and third author are partially supported by NSF grant DMS-0914107 and an IBM OCR award. The second author is partially supported by an NSA Young Investigator Grant and an NSF AllInstitutes Postdoctoral Fellowship administered by the Mathematical Sciences Research Institute through its core grant DMS-0441170. iThe fourth author is partially supported by NSERC Postgraduate Scholarship 281174. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R114 1 1 Introduction In his well-known survey 1 Noga Alon used the term polynomial method to refer to the use of nonlinear polynomials when solving combinatorial problems. Although the polynomial method is not yet as widely used as its linear counterpart increasing numbers of researchers are using the algebra of multivariate polynomials to solve interesting problems see for example 2 12 13 17 19 23 24 32 .
