Gröbner Bases Tutorial Part II Graph Theory

Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery Gröbner Bases Tutorial Part II: A Sampler of Recent Developments The Generic Gröbner Walk Phylogenetic Invariants Department of Mathematics and Computer Science Outline Gröbner Bases Tutorial The original plan was to cover five topics: Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants • Graph Theory • Geometric Theorem Discovery • The Generic Gröbner Walk • Alternatives to the Buchberger Algorithm ← Too hard • Moduli of Quiver Representations ← Too complicated The new plan is to cover four topics: • Graph Theory • Geometric Theorem Discovery • The Generic Gröbner Walk • (New) Phylogenetic Invariants Graph Colorings Gröbner Bases Tutorial Let G = (V , E ) be a graph with vertices V = {1, . . . , n}. Graph Theory Definition A k-coloring of G is a function from V to a set of k colors such that adjacent vertices have distinct colors. Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Example vertices = 81 squares edges = links between: • squares in same column • squares in same row • squares in same 3 × 3 Colors = {1, 2, . . . , 9} Goal: Extend the partial coloring to a full coloring. 3 5 1 7 6 2 2 9 2 6 5 3 4 3 9 5 8 1 3 4 4 6 3 1 7 Graph Ideal Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Definition The k-coloring ideal of G is the ideal IG,k ⊆ C[xi | i ∈ V ] generated by: for all i ∈ V : xik − 1 for all ij ∈ E : xik −1 + xik −2 xj + · · · + xi xjk −2 + xjk −1 . Phylogenetic Invariants Lemma V(IG,k ) ⊆ Cn consists of all k-colorings of G for the set of colors consisting of the k th roots of unity µn = {1, ζk , ζk2 , . . . , ζkk −1 }, Proof. (xik − 1) − (xjk − 1) xi − xj ζk = e2π i/k . = xik −1 + xik −2 xj + · · · + xjk −1 . The Existence of Colorings Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery Two Observations G has a k-coloring ⇐⇒ V(IG,k ) 6= 0. / Hence the Consistency Theorem gives a Gröbner basis criterion for the existence of a k-coloring. The Generic Gröbner Walk 3-Colorings Phylogenetic Invariants For 3-colorings, the ideal IG,3 is generated by for all i ∈ V : xi3 − 1 for all ij ∈ E : xi2 + xi xj + xj2 . These equations can be hard to solve! Theorem 3-colorability is NP-complete. Example Gröbner Bases Tutorial This example of a graph with a 3-coloring is due to Chao and Chen (1993). 1 2 5 Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Hillar and Windfeldt (2006) compute the reduced Gröbner basis of the graph ideal IG,3 for lex with x1 > · · · > x12 . 6 12 7 11 8 10 9 The reduced Gröbner basis is: 4 3 {x12 − 1, x7 − x12 , x4 − x12 , x3 − x12 , 2 2 x11 + x11 x12 + x12 , x9 − x11 , x6 − x11 , x2 − x11 , x10 + x11 + x12 , x8 + x11 + x12 , x5 + x11 + x12 , x1 + x11 + x12 }. Note x8 − x10 , x5 − x10 , x1 − x10 ∈ IG,3 . 3 Uniquely k -Colorable Graphs Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants The Chao/Chen graph has essentially only one 3-coloring. Definition A graph G is uniquely k-colorable if it has a unique k-coloring up the permutation of the colors. Hillar and Windfeldt show that unique k-colorability is easy to detect using Gröbner bases. We start with a k-coloring of G that uses all k colors. Assume the k colors occur among the last k vertices. Then: Use variables x1 , . . . , xn−k , y1 , . . . , yk with lex order x1 > · · · > xn−k > y1 > · · · > yk . Use these variables to label the vertices of G. Some Interesting Polynomials Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Consider the following polynomials: ykk − 1 hj (yj , . . . , yk ) = xi − yj , αj ∑αj +···+αk =j yj · · · ykαk , j = 1, . . . , k − 1 color(xi ) = color(yj ), j ≥ 2 xi + y2 + · · · + yk , color(xi ) = color(y1 ). Phylogenetic Invariants In this notation, the Gröbner basis given earlier is: {y33 − 1, h2 (y2 , y3 ) = y22 + y2 y3 + y32 , h1 (y1 , y2 , y3 ) = y1 + y2 + y3 , x7 − y3 , x4 − y3 , x3 − y3 , x9 − y2 , x6 − y2 , x2 − y2 , x8 + y2 + y3 , x5 + y2 + y3 , x1 + y2 + y3 }. A Theorem Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Summary: G has vertices x1 , . . . , xn−k , y1 , . . . , yk . G has a k-coloring where y1 , . . . , yk get all the colors. C[x, y] has lex with x1 > · · · > xn−k > y1 > · · · > yk . Using this data, we create: The coloring ideal IG,k ⊆ C[x, y]. The n polynomials g1 , . . . , gn given by ykk − 1, hj (yj , . . . , yk ), xi − yj , xi + y2 + · · · + yk , Theorem The following are equivalent: G is uniquely k-colorable. g1 , . . . , gn ∈ IG,k . {g1 , . . . , gn } is the reduced Gröbner basis for IG,k . Remarks Gröbner Bases Tutorial When G is uniquely k-colorable, the theorem implies Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants −1 hLT(IG,k )i = hykk , ykk−1 , . . . , y22 , y1 , xn−k , . . . , x1 i. Since dim C[x, y]/IG,k = #monomials not in hLT(IG,k )i, and IG,k is radical, a uniquely k-colorable graph has #k-colorings = dim C[x, y]/IG,k = k · (k − 1) · · · 2 · 1 = k!. Hillar and Windfeldt have a version of this result that doesn’t assume we know a k-coloring in advance. Final Comment Gröbner Bases Tutorial Other aspects of graphs can be coded algebraically. Here is an example from de Loera, Lee, Margulies, and Onn (2007). Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Let G = (V , E ) with V = {1, . . . , n}. Consider variables x1 , . . . , xn and y1 , . . . , yn and fix a positive integer L. Theorem G has a cycle of length L ⇐⇒ the following equations have a solution: y1 + · · · + yn = L yi (yi − 1) = 0, 1 ≤ i ≤ n ∏ns=1 (xi − s) = 0, 1 ≤ i ≤ n yi ∏ (xi − yj xi + yj )(xi − yj xi − yj (L − 1)) = 0, 1 ≤ i ≤ n. ij∈E A Final Amusement Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants To solve this sudoku, use: • 81 variables xij , 1 ≤ i, j ≤ 9. • Relabel the 9 variables for red squares as y1 , . . . , y9 . • The graph ideal IG,9 . • The 9 polynomials y9 9 − 1, h8 (y8 , y9 ), h7 (y7 , y8 , y9 ), h6 (y6 , y7 , y8 , y9 ), . . . , h1 (y1 , . . . , y9 ) = y1 + · · · + y9 . • The 16 polynomials x31 − y7 , x33 − y6 , x37 − y2 , . . . 3 5 1 7 6 2 2 9 2 6 5 3 4 3 9 5 8 1 3 4 4 6 7 3 1 Assuming a unique solution, the Gröbner basis of the ideal generated by these polynomials will contain x11 − yi , etc. This will tell us how to fill in the blank squares! References Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants C.-Y. Chao, Z. Chen, On uniquely 3-colorable graphs, Discrete Mathematics 112 (1993), 21–27. C. Hillar, T. Windfeldt, Algebraic characterization of uniquely vertex colorable graphs, J. Comb. Th., to appear. J. A. de Loera, Gröbner bases and graph colorings, Beiträge zur Algebra un Geometrie 36 (1995), 89–96. J. A. de Loera, J. Lee, S. Margulies, S. Onn, Expressing combinatorial optimization problems by systems of polynomial equations and the Nullstellensatz, arXiv:0706.0578 [math.CO].