**Definition 12.6***
Let G = (V,E) be a graph such that
.
We say that G is a Gröbner graph if G is a directed acyclic
graph and for every v
V, either T(v,G) is the empty set or v lies in the ideal generated
by T(v,G).
*

**Definition 12.7***
Let G = (V,E) be a graph and v be a vertex of G. We will say that v
is a starting vertex if T(v,G) is the empty set.
*

The following proposition follows easily from the previous two definitions and mathematical induction. We omit the proof.

**Proposition 12.8***
Let G = (V,E) be a Gröbner graph, V be a finite set and v be
a vertex of G. Let
be the set of starting vertices of G. Every element of V lies in the
ideal generated by
.
*

**Remark 12.9***
The hypothesis of Proposition 12.8 can be strengthened. One can
replace the hypothesis that V be a finite set with the hypothesis
that every element of V has only finitely many ancestors.*

If one takes a subgraph
of a Gröbner graph *G* = (*V*,*E*) such that

then is a Gröbner graph. Other subgraphs of a Gröbner graph may be Gröbner, but the above mentioned subgraphs can be seen to be Gröbner from purely graph-theoretic arguments. We call these subgraphs subGröbner and formalize this with the following definition.ifvis a vertex of the graph andvis not a starting vertex of , then

**Definition 12.10***
A graph G = (V,E) will be called a subGröbner graph
with respect to a Gröbner graph
if G is a subgraph a
and for every v
V, either v is a starting vertex of G or T(v,G) = T(v,
).
*

Note that if one is given a Gröbner graph
and a set of vertices
, then there is a smallest graph
*G*=(*V*,*E*) such that and *G*
is subGröbner with respect to .

If and are graphs, then we let denote the graph and let denote the graph .

**Lemma 12.11***
Let
be a Gröbner graph. If
and
are subGröbner with respect to
, then
is subGröbner with respect to
and
where
denotes the set of starting vertices of
for any Gröbner graph
.
*

Proof. \ For ease of reference, let , and . We wish to show that . Since , and , it suffices to show that if and only if under the conditions that , or .

If , then if and only if , if and only if and . Therefore, if and only if which occurs if and only if .

If , then if and only if , and . Therefore, if and only if which occurs if and only if .

If , then , if and only if and . Therefore, if and only if which occurs if and only if .

In summary, .

Let *v* be a vertex of
which is not a starting vertex.
Therefore, .
Without loss of generality, assume that
. But then
and
. Therefore,
and so

Therefore, . This completes the proof of Lemma 12.11.

The following lemma follows trivially from the definition of immediate ancestor, the definition of a starting vertex (Definition 12.7) and the definition of subGröbner graph (Definition 12.10).

**Lemma 12.12***
Let
be a Gröbner graph. If
=
and
=
are subGröbner with respect to
,
then
is subGröbner with respcet to
.
*

The following technical lemma will be used in the proof of Proposition prop:generating:RR

**Lemma 12.13***
Let
= (V,E) be a Gröbner graph,
be a finite set,
and for each
,
let
if
is and element of
such that
card()
card()
for each
,
then
is empty for every starting vertex w of
.
*

Proof. \
Suppose, for the purpose of proof by contradiction, that there
exists a starting vertex of *w* of such
that
is not empty.
Since is not empty, there exists
which is subGröbner with
respect to
such that
*v* is a vertex of and every starting vertex
of is a member of .
By Lemma
12.11,
is subGröbner with respect to and
.
By the choice of , the
fact that is a subgraph of
and the
fact that ,
the graph
equals the graph and so
must be a subgraph of . But
then, since ,
*w* is a starting vertex of and *w* is a
vertex of , *w* is a member of
which is a contradiction. Thus
is empty
for every
starting vertex of *w* of .
This completes the proof of Lemma 12.13.

Wed Jul 3 10:27:42 PDT 1996