###### GROBNER BASES WITH APPLICATIONS IN GRAPH THEORY

###### Diploma

*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[*x*_{1}*,...,x _{n}*]. 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[

*x*

_{1}

*,...,x*] is Noetherian. That is, every ideal in

_{n}*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 *m*_{1}*,m*_{2}*,m*_{3 }∈
*R*.

1 ≤
*m*_{1 }and *m*_{1}*m*_{3 }≤ *m*_{2}*m*_{3 }whenever *m*_{1 }≤ *m*_{2}*.*

The lexicographic, or lex ordering, is
defined as follows. Let *m*_{1 }and
*m*_{2 }be any monomials in *R*. Let the *n*-tuples *a *= (*a*_{1}*,a*_{2}*,...,a _{n}*)
and

*b*= (

*b*

_{1}

*,b*

_{2}

*,...,b*) represent the exponents of

_{n}*m*

_{1 }and

*m*

_{2}, respectively. That is, let

*a*be the exponent of the variable

_{i }*x*in

_{i }*m*

_{1}, and let

*b*be the exponent of the variable

_{i }*x*in

_{i }*m*

_{2}. Let

*c*be the

*n*-tuple

*c*= (

*a*

_{1 }−

*b*

_{1}

*,...,a*−

_{n }*b*). If position

_{n}*i*is the first non-zero value in

*c*, then

*m*

_{1 }

*> m*

_{2 }if

*c*0 and

_{i }>*m*

_{1 }

*< m*

_{2 }if

*c*0. For example, under lex ordering with

_{i }<*x*

_{1 }

*> x*

_{2 }

*> x*

_{3 }we have:

*.*

The graded
lexicographic, or grlex ordering, uses total degrees. Let *m*_{1}, *m*_{2},
*a *and *b *be defined as before. Then the *total degree *of the monomial *m*_{1
}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 *x*_{1 }*> x*_{2 }*> x*_{3 }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 *∈ *I*i*.*

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
*= {*g*_{1}*,...,g _{m}*} of polynomials in

*I*whose leading monomials under that ordering generate the leading ideal of

*I*. That is,

hLM(*I*)i = hLM(*g*_{1})*,...,*LM(*g _{m}*)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 *= {*g*_{1}*,...,g _{m}*}.
This process is called the

*general polynomial division algorithm*, and it proceeds as follows.

1. Set
the remainder *r *and the quotients *q*_{1}*,...,q _{m }*to zero.

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

2.1. If
LT(*f*) is divisible by LT(*g _{i}*) then:

2.1.1. Add
(LT(*f*)*/*LT(*g _{i}*)) to
the quotient

*q*.

_{i}2.1.2. Replace
*f *by *f *− (LT(*f*)*/*LT(*g _{i}*))

*g*.

_{i}2.1.3. Set
*i *= 1 and return to step 2.

3. If
LT(*f*) is not divisible by any of {LT(*g _{i}*)

*,...,*LT(

*g*)} then:

_{m}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.

**Info!**For specific Project Format, Please upload the format at your dashboard after payment.