GROBNER BASES WITH APPLICATIONS IN GRAPH THEORY

Postgraduate

ABSTRACT
Gr¨obner basis theory has been applied to the problem of graph coloring with interesting results. A graph on n vertices is represented by a polynomial in n variables with degree equal to the number of edges in the graph. In the polynomial ring in n variables, the question of k-colorability is equivalent to determining if the polynomial which represents the graph is contained in a specific ideal. By finding a Gr¨obner basis for this ideal, the problem becomes greatly simplified. We review two different approaches used to solve this problem, and demonstrate the techniques with examples. We also give a new algebraic characterization of the Gr¨obner basis of a particular ideal when there is a unique k-coloring of a graph.

Introduction

The theory of Gr¨obner bases is applied to the problem of graph coloring in [2]. A graph with n vertices is represented by a polynomial in n variables. This polynomial lies in a particular ideal if and only if the graph is k-colorable. Thus, the problem of k-coloring a graph is equivalent to an ideal membership problem. A Gr¨obner basis is given for this ideal. This method has the advantages that the ideal is identical for any graph on n vertices, and the polynomials in the Gr¨obner basis are homogeneous. It is also shown in [8] that this Gr¨obner basis is universal, meaning it is a Gr¨obner basis under any monomial ordering. The Gr¨obner basis contains  polynomials, and for larger graphs, computations become unwieldy.

In [2], another ideal is described, which has a Gr¨obner Basis consisting of n+e generators, where e is the number of edges in the graph. The underlying field may be the complex numbers, where the colors are defined to be the k-th roots of unity, or the underlying field may be a finite field. In this approach, however, a different Gr¨obner basis must be computed for each graph.

In chapter two, we review the theory of Gr¨obner bases; more information can be found in [3] and [6]. In the third chapter, we review this first method of describing the graph coloring problem via Gr¨obner bases, and give examples to demonstrate the theory. We also describe the situation of uniquely colorable graphs, and give an algebraic interpretation of the results. In the fourth chapter, we describe the alternate method, and demonstrate the results when the graph is bipartite.


Gr¨obner Bases

Let F be any field, and let R be the polynomial ring F[x1,...,xn]. A ring with unity is called Noetherian if every ideal contained in it is finitely generated. Hilbert’s basis theorem states that if a ring Q is Noetherian, then so is its ring of polynomials Q[x]. By induction on n, we can see that the polynomial ring R = F[x1,...,xn] is Noetherian. That is, every ideal in R is finitely generated.

In order to define the leading term of a polynomial in more than one variable, we need to specify a monomial ordering. A monomial ordering is a well-ordering of monomials from the ring R. This means that the following two conditions are satisfied for all monomials m1,m2,m3 R.

1 ≤ m1 and m1m3 m2m3 whenever m1 m2.

The lexicographic, or lex ordering, is defined as follows. Let m1 and m2 be any monomials in R. Let the n-tuples a = (a1,a2,...,an) and b = (b1,b2,...,bn) represent the exponents of m1 and m2, respectively. That is, let ai be the exponent of the variable xi in m1, and let bi be the exponent of the variable xi in m2. Let c be the n-tuple c = (a1 b1,...,an bn). If position i is the first non-zero value in c, then m1 > m2 if ci > 0 and m1 < m2 if ci < 0. For example, under lex ordering with x1 > x2 > x3 we have:

.

The graded lexicographic, or grlex ordering, uses total degrees. Let m1, m2, a and b be defined as before. Then the total degree of the monomial m1 is defined to be. Under the grlex ordering, monomials are sorted by total degree first,

that is,. Any monomials that have the same total

degree are then sorted by the lex ordering. For example, under grlex ordering with x1 > x2 > x3 we have:

.

The graded reverse lexicographic, or grevlex ordering, again sorts monomials by total degree. Any monomials with the same total degree are sorted in the reverse of the lex ordering. For example, under grevlex ordering we have:

.

Given a monomial ordering, we can then define the leading term of a polynomial f R. We will write LT(f) for the leading term of f. Additionally, we will write LM(f) for the leading monomial of f, and LC(f) for the leading coefficient of the leading term. Therefore, LT(f) = LC(f) · LM(f). Let I be an ideal of R. The leading ideal of I, written hLM(I)i, is defined to be the ideal generated by the leading monomials of all polynomials in I. That is,

hLM(I)i = hLM(f)|f Ii.

Note that the leading ideal is also generated by the leading terms of all f in I. If the generating set of an ideal consists entirely of monomials, then I is called a monomial ideal.

A Gr¨obner basis for an ideal I with respect to a particular monomial ordering is a set G = {g1,...,gm} of polynomials in I whose leading monomials under that ordering generate the leading ideal of I. That is,

hLM(I)i = hLM(g1),...,LM(gm)i.

Under any monomial ordering, it can be shown that every non-zero ideal I R has a Gr¨obner basis.

Once a monomial ordering is specified, we can divide a polynomial f by an ordered set G = {g1,...,gm}. This process is called the general polynomial division algorithm, and it proceeds as follows.

1.    Set the remainder r and the quotients q1,...,qm to zero.

2.    For i = 1,2,...,m do:

2.1.    If LT(f) is divisible by LT(gi) then:

2.1.1.    Add (LT(f)/LT(gi)) to the quotient qi.

2.1.2.    Replace f by f − (LT(f)/LT(gi))gi.

2.1.3.    Set i = 1 and return to step 2.

3.    If LT(f) is not divisible by any of {LT(gi),...,LT(gm)} then:

3.1.    Add LT(f) to the remainder r.

3.2.    Replace f by f − LT(f).

4.    Return to step 2 until f is zero.