Algebraic invariants of graphs; a study based on computer exploration

Nicolas M. Thiéry

Not printed

Abstract: We consider the ring In of polynomial invariants over weighted graphs on n vertices. Our primary interest is the use of this ring to define and explore algebraic versions of isomorphism problems of graphs, such as Ulam's reconstruction conjecture.

There is a huge body of literature on invariant theory which provides both general results and algorithms. However, there is a combinatorial explosion in the computations involved and, to our knowledge, the ring In has only been completely described for n≤4.

This led us to study the ring In in its own right. We used intensive computer exploration for small n, and developed PerMuVAR , a library for MuPAD , for computing in invariant rings of permutation groups.

We present general properties of the ring In, as well as results obtained by computer exploration for small n, including the construction of a medium sized generating set for I5. We address several conjectures suggested by those results (low degree system of parameters, unimodality), for In as well as for more general invariant rings. We also show that some particular sets are not generating, disproving a conjecture of Pouzet related to reconstruction, as well as a lemma of Grigoriev on the invariant ring over digraphs. We finally provide a very simple minimal generating set of the field of invariants.

Introduction

Let K be a field of characteristic zero, n be a positive integer, and {x{1,2}, ..., x{n-1,n}} be a set of (
n
2
) variables indexed by the pairs {i,j} of {1,...,n}. The symmetric group Sn acts naturally on those variables by
σ⋅ x
 
{i,j}
:=x
 
{σ(i),σ(j)}
.
Let K[x{i,j}] be the ring of polynomials in x{i,j}. We study the subring In:=K[x{i,j}] Sn of the polynomials which remain invariant under the action of Sn.

Our motivation comes from graph theory and in particular from graph reconstruction. Pouzet [21, 22] formulated an algebraic reconstruction conjecture for In, which implies Ulam's famous reconstruction conjecture for weighted graphs [2]. We disprove Pouzet's conjecture. Kocay proposed a similar conjecture, by introducing the algebra of subgraphs [19, 3]. This algebra is a quotient of In; however this quotient is not graded, and we cannot apply our method to disprove Kocay's conjecture.

The ring In can also be used to study the shape of sets of vectors [1]. Our primary goal is to construct complete systems of invariants (systems that separate weighted graphs up to isomorphism), and in particular minimal generating sets of In.

In § 1, we introduce the representation Gn of the symmetric group Sn over the vector space Vn of weighted graphs on n vertices, and the associated invariant ring In. We review classical results and tools provided by invariant theory (finite generation, grading, Hilbert series). Since Gn is a permutation group, there is a combinatorial interpretation of the invariant ring, and a reasonably fast algorithm for computing the Hilbert series. We also review some general properties of minimal generating sets, and the definition of the smallest degree bound β( In).

§ 2 is devoted to generating sets of In. We provide a finite generating set. By studying the Hilbert series, we show that two other sets are not generating, disproving Pouzet's conjecture. We also prove that, for many common monomial orders, In has no finite SAGBI basis.

Finding a good degree bound is crucial. In § 3, we recall how Hironaka decompositions of In can be used to obtain the degree bound β( In)≤(
æ
è
n
2
ö
ø
2
)-µn, where µn is a non-negative O(n) integer. We calculate µn by constructing minimal multigraphs without odd automorphisms.

In § 4, we try to refine the degree bound by constructing low degree systems of parameters. The study of the Hilbert series for n≤21, combined with a conjecture of Mallows and Sloane, suggests the existence of a system of parameters composed of invariants of degrees 1,2,...,n, 2,3,..., (
n-1
2
). This would give β( In)≤(
æ
è
n-1
2
ö
ø
2
)-µn. We propose a natural construction for such a low degree system of parameters, and check its validity for n≤5 using a Gröbner basis computation. Unfortunately, this computation is intractable for n≥6. Such a system of parameters seems to have nearly optimally low degrees; therefore, this technique cannot be refined much further in order to get better degree bounds.

§ 5 is devoted to the computation of minimal generating sets. For n=4, a minimal generating set was first constructed by hand by Aslaksen, Chan et Gulliksen [1]; it can now be computed in a few seconds by invariant theory software (e.g. Kemper's packages in Maple  [16] or Magma  [17]). However, for n≥5, these software packages are unable to compute even partial minimal generating sets. We wrote PerMuVAR  [32], a library of invariant theory routines for MuPAD , which uses the usual algorithms [29, 17], but is specialized for permutation groups. This allows us to go a step further: for n=5, we compute a partial minimal generating set, containing 57 polynomials of degree ≤ 91. This suggests a much better degree bound: β( In)=(
n
2
) -1.

In § 6, we prove that the invariant ring In is Gorenstein when n is even. This fact could be used to accelerate the computations of Hironaka decompositions [32].

We introduce in § 7 the chain product (a naive interpretation of Stanley-Reisner rings [11]). This allows for faster computations of generating sets at the expense of non-minimality [32]: we obtain a generating set of I5 containing about one thousand polynomials of degree ≤22.

In § 8 the projective limit I∞ is used to obtain results about In; this includes the lower bound β( In)≥ ⌊n/2⌋.

§ 9 presents various unimodality properties revealed by computer exploration, for In as well as for more general invariant rings.

Grigoriev [14] introduces a related invariant ring over digraphs. In § 10, we apply the Hilbert series tool of § 2 to disprove lemma 1 of [14]. We also provide a simple counter-example. Finally, in § 11, we study the field of invariants. Grigoriev [14] gives a non-constructive proof for the existence of a small generating set of the field of invariants (the proof of the degree bound is incorrect though, since it relies on lemma 1 of [14]). We construct such a small generating set, composed of the elementary symmetric polynomials and a very simple invariant of degree 2; to the contrary of Grigoriev's assertion, it is not a complete system of invariants. We also derive a minimality property of the invariant ring, by using basic Galois theory on the field of invariants.

The results presented in this paper are part of the Ph. D. thesis [30] of the author. We refer to this document for the detailed proofs.

1   The invariant ring over graphs

1.1   Valuated graphs as a vector space

Let V be a K-vector space of finite dimension m, and G be a finite subgroup of GL(V). Tacitly, we interpret G as a group of m× m matrices or as a representation on V. Two vectors v and w are isomorphic, or in the same G-orbit (for short orbit), if σ⋅v=w for some σ∈ G.

Let n be a positive integer. We consider labelled, undirected graphs on the vertices {1,...,n}, without loops, and whose edges are weighted in K. A simple graph is a graph with weights in {0,1}, and a multigraph is a graph with weights in N. For any pair {i,j}, let e{i,j} be the simple graph with one single edge {i,j}. The set of all graphs is a K-vector space Vn of dimension m:=(
n
2
) with basis {e{1,2},...,e{n-1,n}}. Indeed, any graph g can be written uniquely as g:=∑ g{i,j}e{i,j}, where g{i,j} is the weight of the edge {i,j}. Let {x{1,2},...,x{n-1,n}} be the dual basis (x{i,j}(g) is the weight g{i,j} of the graph g on the edge {i,j}).

Throughout the text, we denote objects attached to Vn by cursive symbols, and objects attached to the generic vector space V by ordinary symbols. Let Sn be the symmetric group of all permutations of the n vertices. Our group Gn is the linear representation of Sn defined on the basis of Vn by σ⋅e{i,j}:=e{σ(i),σ(j)}. The notion of isomorphism defined above coincides with the usual notion of isomorphism of graphs. Orbits of labelled graphs are called unlabelled graphs. Unless otherwise stated, all graphs are unlabelled.

The representation of Gn on Vn splits into three irreducible components: [n]⊕[n-1,1]⊕[n-2,2], where [n-2,2] represents the irreducible representation of Sn indexed by the partition λ=(n-2,2) of n [1, 10]. The first component has dimension 1 and corresponds to the vector space spanned by the complete graph. The sum [n]⊕[n-1,1] of the first two components is of dimension n, and corresponds to the vector space spanned by the n stars E1,...,En, where Ei:=∑j≢ i e{i,j}. This representation is the natural representation of Sn by permutation of E1,...,En. Let X1,...,Xn be the basis of the dual, defined by Xi:=∑j≢ i x{i,j}. If g is a graph, Xi(g) is the degree of the vertex i of g. Finally, the last irreducible component [n-2,2] is the orthogonal of the two previous components, that is the subspace of all 0-regular graphs (graphs where each vertex as degree 0).

1.2   The invariant ring

Recall that if G acts on V, a complete system of invariants is a set S of functions such that two elements v and w of V are in the same orbit if and only if they give the same value to all functions in S (i.e. p(v)=p(w) for all p∈ S). Our primary goal is to construct, or at least find information about, complete systems of invariants. We introduce the invariant ring of G which provides a mechanical way to do this. We refer to [27, 29, 5, 26, 17] for classical literature on invariant theory of finite groups. Parts of what follows are strongly inspired by [17].

Let (x1,...,xm) be a basis of the dual of V; for Vn, we take (x1,...,xm):=(x{1,2},...,x{n-1,n}). Let K[x1,...,xm] be the ring of polynomials over V. The action of G on V extends naturally to an action of G on K[x1,...,xm] by σ⋅ p:=p∘ σ-1. An invariant polynomial, or invariant, is a polynomial p∈ K[x1,...,xm] such that σ⋅ p=p for all σ∈ G. The invariant ring I(G) is the set of all invariants. We call In:=I( Gn) the invariant ring over graphs. Note that σ⋅ x{i,j}:=x{i,j}∘σ-1=x{σ(i),σ(j)}.

Obviously, I(G) is a K-algebra. Hilbert's famous theorem states that I(G) is finitely generated: there exists a finite set S of invariants such that any invariant can be expressed as a polynomial combination of invariants in S. We call S a generating set. If no proper subset of S is generating, S is a minimal generating set. Since I(G) is finitely generated, there exists a degree bound d such that I(G) is generated by the set of all invariants of degree at most d. We denote by β(I(G)) the smallest degree bound.

There exist algorithms to compute (minimal) generating sets, and a basic result of invariant theory states that they are complete systems of invariants. However, this often leads to very intensive computations, and rather large complete systems of invariants.

1.3   Invariant ring of a permutation group

The most famous invariant ring is the ring of symmetric polynomials I( Sm), defined by the natural action of Sm on the variables (x1,...,xm). The fundamental theorem of symmetric polynomials [29, p. 2] states that I( Sm) is generated by m algebraically independent symmetric polynomials, for example the m elementary symmetric polynomials or the first m symmetric power sums.

Gn is a permutation group, since it acts by permuting the variables x{i,j}; thus, we also view Gn as a subgroup of the full group Sm of the permutations of m variables. This results in several convenient and powerful combinatorial interpretations of invariants:

(i) A labelled multigraph g:=(g{1,2},...,g{n-1,n}) can be identified with the monomial xg:=x{1,2}g{1,2}... x{n-1,n}g{n-1,n}. The exponential of g is the polynomial xgˆ*:=∑hxh, where h belongs to the orbit of g. The polynomial xgˆ* is invariant, and is well defined even if g is unlabelled. The exponential therefore identifies unlabelled graphs with some particular invariants. Moreover, the set of all invariants xgˆ*, where g is a multigraph, is a vector space basis of In. Note that the exponential differs from the usual Reynolds operator * by a multiplicative factor: xgˆ*=|Aut(g)|(xg)*, where |Aut(g)| is the size of the automorphism group of g.

(ii) Let g1 and g2 be two multigraphs on n vertices. The product xg1ˆ*xg2ˆ* is a linear combination of all possible superpositions of g1 and g2 (with, at times, counter-intuitive coefficients). For instance:
( )
ˆ*
 
 
 ×
( )
ˆ*
 
 
 =
( )
ˆ*
 
 
  +
( )
ˆ*
 
 
  +
( )
ˆ*
 
 
 .
Let n'>n, and consider the multigraphs g1 and g2 obtained by adding n'-n isolated vertices to g1 and g2. New superpositions, which fit in n' vertices but not in n vertices, may appear in the product xg1ˆ*xg2ˆ*. However, the use of a modified Reynolds operator ensures that the coefficients in the linear combination do not change. This makes the product somewhat independent of n (see § 8).

(iii) If g and h are simple graphs, xgˆ*(h) counts the number s(g,h) of subgraphs of h isomorphic to g. The following invariants can be used to count respectively the number of edges, the number of pairs of adjacent edges and the number of Hamiltonian cycles of h:
( )
ˆ*
 
 
 (h),
 
( )
ˆ*
 
 
 (h),
 
( )
ˆ*
 
 
 (h).
Manipulations of the quantities s(g,h) are the cornerstone of several results on reconstruction of graphs [2]; for the use of these algebraic considerations see [23].

1.4   Grading, Hilbert series and degree bound

Powerful properties of an invariant ring are its grading and the associated Hilbert series. As a K-vector space, I(G) is not finite dimensional. However, since the action of G preserves the degree of polynomials, I(G) decomposes into the direct sum of its homogeneous components:
I(G)=⊕
∞
 
d=0
I(G)d,
where I(G)d is the finite dimensional vector space of all homogeneous invariants of degree d. The Hilbert series of I(G) is the generating series of its dimensions:
H(I(G),z):=
∞
∑
d=0
zd dim I(G)d.

For general finite groups of matrices, this series can be computed by averaging over the group, through Molien's formula. However, since Gn is a permutation group, the set of all invariants xgˆ*, where g is a multigraph with d edges is a vector space basis of In,d. Therefore, computing H( In,z) reduces to a Pólya enumeration of multigraphs with respect to the number of edges [27]. Recall that the conjugacy classes Cλ of Sn are indexed by the partitions λ of n. Let σ be a permutation of the vertices in Cλ. The cycle type of the induced permutation of the edges is easily computed from the cycle type of σ, i.e. from the partition λ [15]. We denote by l1(λ),...,lm(λ) this cycle type. Then,
H( I
 
n
,z)=
1
n!
 
∑
λ
|C
 
λ
|
1
(1-zi)
li(λ)
 
,
where the sum is over all partitions λ of n. This provides an algorithm whose complexity is about O(n4exp(n0.8)). Concretely, we can compute H( In,z) for n≤21. It is sometimes useful to consider the multigraded Hilbert series, where each grading corresponds to one of the three irreducible components of the representation Gn. We can compute this multigraded Hilbert series for n≤15.

Given an integer d≥1, let K[I(G)<d] be the subalgebra of I(G) generated by invariants of degree <d, and K[I(G)<d]d its homogeneous component of degree d. Set s0(I(G)):=0 and sd(I(G)):=dim I(G)d - dim K[I(G)<d]d. The generating series s(I(G),z):=∑d=0∞zd sd(I(G)) is a polynomial of degree β(I(G)).

A set S is homogeneous if its elements are also homogeneous. The following lemma (valid for any graded algebra A, where A0 is the ground field K) summarizes some general properties of generating sets.
Lemma 1.1   Let S be a generating set of I(G).

(i) I(G) has a homogeneous minimal generating set composed of at most |S|β(I(G)) invariants of degree at most β(I(G)).

(ii) Assume S is homogeneous, and let Sd be the set of all invariants of S having degree d. Then, S is a minimal homogeneous generating set if and only if for all d, Sd is a vector space basis of a direct factor of K[I(G)<d]d in I(G)d. In particular, |Sd|=sd(I(G)).
Proof: (i) For each p∈ S and d, let pd be the homogeneous component of degree d of p. Since I(G) is graded, it is generated by the set {pd   |   p∈ S, 1≤ d≤β(I(G))}.

(ii) Use the grading and basic linear algebra. QED From (i), it is not very restrictive to consider only homogeneous generating sets, since non-homogeneous generating sets are not much smaller than homogeneous ones.

The Hilbert series provides a simple necessary condition to test if a set S of homogeneous invariants is generating. The following proposition is valid for any graded algebra A, where A0 is the ground field K. We stress the importance of the homogeneity of the invariants. A series s(z) is dominated by a series t(z) if the coefficients of s(z) are upper-bounded term by term by the coefficients of t(z).
Condition 1.2   Let S:=(p1,...,pt) be a homogeneous generating set, with respective degrees (d1,...,dt). Then, the Hilbert series H(I(G),z) is dominated by the series
F(d1,...,dt,z):=
1
(1-z
d1
 
)...(1-z
dt
 
)
.
Proof: As a vector space, the homogeneous component I(G)d is generated by the set of all the homogeneous products p1λ1... ptλt whose degree d1λ1+...+dtλt is d; those products are counted by the series F(d1,...,dt,z). QED This apparently weak condition is in fact very powerful. In particular, it leads to the proof of theorem 2.3, and to the disproving of Grigoriev's lemma 1 of [14] (see § 10).

2   Generating sets of In

For n=1,2,3, the invariant ring is the ring of symmetric polynomials; the elementary symmetric polynomials form a minimal generating set. For n=4, Aslaksen et al. [1] constructed by hand the following minimal generating set:
ì
í
î
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
 ,
( )
ˆ*
 
 
  ü
ý
þ		 .
At about the same time, we had proven independently a similar result through a Gröbner basis computation with CoCoA [4], using theorem 2.7.9 of [29]. However, our set was not minimal since we had not removed the invariant xcˆ* where c is the complete graph. The set above can now be computed in about one second with Kemper's implementation of Invar in Magma  [17].

We now provide a large, but reasonable, finite generating set of In. A multigraph is quasi-connected if it has, at most, one non-trivial connected component. For example, g1 below is quasi-connected, but not g2:
g1:=,   g2:=.
Proposition 2.1   (i) The homogeneous component In,d has for vector space basis the set of all invariants xc1ˆ*⋯xckˆ*, where each ci is a quasi-connected multigraph with ni non-isolated vertices and di edges, and where n1+...+nk≤ n and d1+...+dk=d.

(ii) The invariant ring In is generated by the set of all homogeneous invariants xgˆ*, where g is a quasi-connected multigraph with at most β( In) edges.
Proof: (i) Let g be a multigraph with n vertices and k>1 non-trivial connected components c1,...,ck. Let c1,...,c1 be the quasi-connected multigraphs on n vertices obtained by adding isolated vertices to the ci. Obviously, n1+...+nk≤ n, and d1+...+dk=d. Then:
x
g
 
ˆ*
 
=
x
c
1
 
ˆ*
 
⋯
x
c
k
 
ˆ*
 
-
 
∑
i
x
hi
 
ˆ*
 
,
where the hi are multigraphs with strictly less than k non-trivial connected components. For example:
( )
ˆ*
 
 
 =
( )
ˆ*
 
 
 ×
( )
ˆ*
 
 
  -
( )
ˆ*
 
 
  -
( )
ˆ*
 
 
 .
By induction on the number k of non-trivial connected components, g is a linear combination of products xc1ˆ*⋯xckˆ*. In fact, we just inverted a triangular linear system with ones on the diagonal, and uniqueness follows.

(ii) Use (i) and the definition of β( In). QED Obviously, in order to get a usable generating set, it is essential to have a good bound for β( In).

We tried to use the technique of SAGBI basis. This is a powerful tool, which generalizes Gröbner basis techniques for rings instead of ideals [24]. The main drawback is that there exist invariant rings with no finite SAGBI basis; this seems to be the case for In, at least for many common monomial orders.
Theorem 2.2   There are no finite SAGBI basis for In if the monomial order is either lexicographic, degree lexicographic, or degree reverse lexicographic with the n-1 smallest variables corresponding to adjacent edges.
Proof: We prove in each case that there is an infinite number of irreducible initial monomials (an initial monomial is irreducible if it cannot be written as product of two smaller initial monomials). For the lexicographic order, we can alternatively use Göbel's characterization of permutation groups with finite SAGBI basis [13]. QED

The following theorem states that some sets are not generating. (i) disproves a tempting generalization of the fundamental theorem of symmetric functions, whereas (ii) disproves Pouzet's conjecture [21], which would have implied Ulam's reconstruction conjecture.
Theorem 2.3   (i) For n≥5, the set of all invariants xgˆ*, where g is a simple graph, do not generate In.

(ii) For 11≤ n≤18, the set of all invariants xgˆ*, where g is a multigraph with at least one isolated vertex, do not generate In.
Proof: (i) For n=5,6,7,8, simple graphs can be counted with respect to the number of edges using Pólya enumeration [15]. The coefficient of degree d=4 of the series S(d1,..., dt) is strictly smaller than that of the Hilbert series. Therefore, condition 1.2 applies. For n≥9, no new isomorphism types of multigraphs with less than 4 edges appears, so the coefficient of degree 4 of both series is the same as for n=8. Condition 1.2 again applies.

(ii) By an argument similar to the proof of proposition 2.1, we have only to consider the set of all invariants xgˆ*, where g is a multigraph with a unique non-trivial connected component, which is of size <n. Those multigraphs can be counted from the total number of multigraphs by using a technique similar to that described in [15, § 4.2, p. 90]. For 11≤ n≤18, computations of both series shows that condition 1.2 fails. QED We could not check (ii) for n>18 since the computation were intractable. However, the results for n≤ 18 strongly suggest that, for d≈ 4n-24, the ratio between the coefficients of degree d of the two series is bounded by an expression of the form exp(-an)+0.17. This could probably be confirmed by an asymptotic study, and we conjecture that (ii) is true for any n≥11.

3   Decomposition of Hironaka

The smallest degree bound β( In) and furthermore the polynomial s( In,z) contains important information about the invariant ring, which would be very useful when the computation of a minimal generating set is intractable. But so far, we don't know how to calculate them except by explicitly computing such a minimal generating set.

Invariant theory provides only some bounds on β( In) and s( In,z) [25, 6]. Noether's theorem [29, p. 27] yields: β( In)≤ | Gn|=n!, which is not very informative. A much better bound exists for permutation groups: β( In)≤ (
m
2
)=(
æ
è
n
2
ö
ø
2
) [11]. However, our computations for small n shows that this is still a rather loose bound. This section introduces the tools that produce this bound, and possibly even better bounds.

A set of m homogeneous invariants (θ1,...,θm) of I(G) is called a homogeneous system of parameters or, for short, a system of parameters if the invariant ring I(G) is finitely generated over its subring K[θ1,...,θm]. That is, if there exist a finite number of invariants (η1,...,ηt) such that the invariant ring is the sum of the subspaces ηi.K[θ1,...,θm]. By Noether's normalization lemma, there always exists a system of parameters for I(G). Moreover, I(G) is Cohen-Macaulay, which means that I(G) is a free-module over any system of parameters. So, if the set (η1,...,ηt) is minimal for inclusion, I(G) decomposes into a direct sum:
I(G)=⊕i=1t ηi . K[θ1,...,θm].
This decomposition is called a Hironaka decomposition of the invariant ring. The θi are called primary invariants, and the ηi secondary invariants (in algebraic combinatorics literature, the θi are some times called quasi-generators and the ηi separators [11]). It should be emphasized that primary and secondary invariants are not uniquely determined, and that being a primary or secondary invariant is not an intrinsic property of an invariant p, but rather express the role of p in a particular generating set.

The primary and secondary invariants together form a generating set. From the degrees (d1,...,dm) of the primary invariants (θ1,...,θm) and the Hilbert series we can compute the number t and the degrees (e1,...,et) of the secondary invariants (η1,...,ηt) by the formula:
z
e1
 
+...+z
et
 
=(1-z
d1
 
)⋯(1-z
dm
 
) H(I(G),z).     (1)
Assuming d1≤...≤ dm and e1≤...≤ et, it can be proved that:
t =
d1⋯ dm
|G|
,et = d1+...+dm - m - µ,β(I(G))≤ max(dm,et),
    (2)
where µ is the smallest degree of a polynomial p such that σ⋅ p=det(σ) p for all σ∈ G [27, Proposition 3.8].

For example, if G is the symmetric group Sm, the m elementary symmetric polynomial (or the m first symmetric power sums) form a system of parameters, t=1, et=0 and η1=1. This is consistent with the fundamental theorem of symmetric polynomials.

More generally, for Gn as well as for any permutation group, the elementary symmetric polynomials still form a system of parameters. This yields the following information on In.
Proposition 3.1   For n≥4, consider the system of parameters of In composed of the elementary symmetric polynomials, and let (e1,...,et) be the degrees of secondary invariants. Then,
t =
m!
| G
 
n
|
=
æ
è
n
2
ö
ø		 !
n!
,
et = æ
è
m
2
ö
ø		 - µn = æ
ç
è
æ
è
n
2
ö
ø
2
ö
÷
ø		 - µn,
β( I
 
n
)≤ æ
ç
è
æ
è
n
2
ö
ø
2
ö
÷
ø		 -µn,
where µn=0 if n is even, and µn=⌈3/4(n-1)⌉ otherwise.
For example, β( I4)≤15, β( I5)≤42 and β( I6)≤104. Proof: We only have to check the value of µn. When n is even, det(σ)=1 for all σ∈ Gn. Therefore, p:=1 verifies the condition σ⋅ p=det(σ) p for all σ∈ Gn. We note that this is generally true for any Gorenstein ring (see § 6 and [27, § 8]). When n is odd, the sign of a permutation of the edges is the sign of the corresponding permutation of the vertices. Then, the smallest degree µn of a polynomial p such that σ⋅ p=signσ p is the smallest number of edges of multigraph with no odd automorphism. The following lemma completes the proof. QED

Lemma 3.2   The smallest number of edges of a multigraph gn on n≥4 vertices without odd automorphism is ⌈3/4(n-1)⌉.
Proof: Such multigraphs can be constructed for any n as follows: The minimality of the number of edges of such multigraphs can be proved by induction over n. QED

So, the knowledge of a system of parameters and of the Hilbert series provides both an upper bound on β( In), as well as bounds on the coefficients of s( In,z). Unfortunately, our experience has shown that generating sets composed of primary and secondary invariants are far from minimal (see Figures 4 and 2), so those bounds are quite loose. Moreover, to our knowledge, those bounds are the only obtainable information about a minimal generating set, without actually computing it.

4   Low degrees systems of parameters

We now search for a low degrees system of parameters for In, in order to improve the bound on β( In). Equation (3) can guide our quest by suggesting possible degrees. Indeed, there can only exist a system of parameters of degrees (d1,...,dm) if the expression (1-zd1)⋯(1-zdm) H(I(G),z) is a polynomial with positive integer coefficients. It has even been conjectured by Mallows and Sloane [20, 7] that the converse is true: if (1-zd1)⋯(1-zdm) H(I(G),z) is a polynomial with positive integer coefficient, then there exists a system of parameters of degrees (d1,...,dm). A counter-example has been found, but the conjecture still holds if the representation of G over V is irreducible, or when using a multigraded Hilbert series (one grading for each irreducible component) [7, p. 5].

By tweaking the Hilbert series for n≤21, and the multigraded Hilbert series for n≤15, we find that the degree sequence (1,...,n, 2,...,(
n-1
2
)) always produces a polynomial with positive integer coefficient. We also proved that, for any n, this degree sequence produces a polynomial. We are therefore somewhat confident with the following conjecture:
Conjecture 4.1   For all n≥3, there exists a system of parameters for In of degrees (1,...,n, 2,...,(
n-1
2
)). As a direct consequence, β( In)≤ (
n
2
)+(
æ
è
n-1
2
ö
ø
2
)-µn.
For example, β( I4)≤9, β( I5)≤22 and β( I6)≤60, which are much smaller degree bounds than those provided by proposition 3.1. Figure 1 displays the number of secondary invariants depending on the system of parameters.
[System of parameters: symmetric power sums] [Conjectured system of parameters]

Figure 1: Number of secondaries per degree

Next, we construct a reasonable system of parameters and check its validity for n=3,4,5, which proves conjecture 4.1 for those values. We note that Dixmier [7] constructed a system of parameters with degrees (2,3,4,5,6) for the representation [3,2] of S5, and proved its validity by hand. By using the decomposition of the representation G5 into [5]+[4,1]+[3,2], this also provides a system of parameters with the expected degrees.

The form of the degree sequence suggests starting from the (
n
2
) first symmetric power sums, and replacing the last n-1 degrees ((
n-1
2
)+1,... (
n
2
)) by some invariants of degree 2,...,n. Moreover, since the representation splits into [n]⊕[n-1,1] and [n-2,2] (see § 1.1), we get a system of parameters for the invariant ring of the whole representation, by taking systems of parameters for the invariant rings of each components and putting them together. Recall that the first component is the natural representation of Sn by permutations of the stars (E1,...,En). So, the invariant ring over this component is the ring of symmetric polynomials in the dual variables (X1,...,Xn), and the n first symmetric power sums in the Xi form a system of parameters for this component. Note that, up to a constant 2, the first symmetric power sum in the Xi is equal to the first symmetric power sum in the x{i,j}. All this leads to the following conjecture:
Conjecture 4.2   If n≥3, the following system of invariants is a system of parameters for In.
x
 
{1,2}
+...+x
 
{n-1,n}
,    ...,    x
æ
è
n-1
2
ö
ø
 
{1,2}
+...+x
æ
è
n-1
2
ö
ø
 
{n-1,n}
,
X1+...+Xn,  ...,   X1n+...+Xnn.
Proposition 4.3   Conjecture 4.2 holds for 3≤ n ≤5.
This is immediate for n=3, since the component [n-2,2] is trivial. To test the conjecture for other small cases, we used the following general characterization:
Caracterisation 4.4  [[29]]   A set of m homogeneous invariants (θ1,...,θm) is a system of parameters if and only if v=0 is the only common zero of the θi:
θ1(v)=...=θm(v)=0 ⇒ v=0
For n=4, this characterization is enough to prove conjecture 4.2 by hand.

For n≥5, we can try to check conjecture 4.2 as follow: compute a Gröbner basis for the θi, and verify that for each variable x{i,j} there is a polynomial in the Gröbner basis whose leading term is of the form x{i,j}k (see [29, Subroutine 2.5.2]; this is both a necessary and sufficient condition for the radical of the ideal generated by the θi to be the irrelevant ideal).

For n=3,4, the direct computation of this Gröbner basis takes less than one second, but for n=5 it seems to be intractable and fails. However, some equivalent Gröbner basis can be computed in about one minute, by using a suitable linear change of basis which respects the decomposition of the representation. The verification of characterization 4.4 is then straightforward.

For n=6, even with the same linear change of basis and using FGb  [9], the computation is intractable. In fact, the growth of the Gröbner basis seems to follow nearly the worst possible theoretical case [12].

Finally, as a by-product of the computation of minimal generating sets with PerMuVAR , we checked that for n≤8 and for the low-degree homogeneous components, the ring of invariants is indeed a free-module over K[θ1,...,θm]. This gives some confidence in conjecture 4.2, but so far we are unable to prove it.

If the above construction of a system of parameters is correct, we believe it to be nearly optimal: there exist no general construction of systems of parameters with lower degrees. Indeed, we calculated, for small values of n, the smallest degree sequence allowed by the multigraded Hilbert series. For 3,4,5, the degrees conjectured above are optimal. For n≥6, it was usually possible to divide some of the degrees by 2 or 3. For example, for n=6 and 7 the best degree sequences are respectively (1,...,6, 2,...,7,8/2,9/3,10/2) and (1,...,7, 2,...,7,8/2,9,...,13,14/2,15). We have not noticed any regularity in these case by case optimizations. Therefore, we don't think this technique can be refined much further in order to get better degree bounds.

5   Computing minimal generating sets

Since we can not get more a priori information on homogeneous minimal generating sets of In, we proceed with explicitly computing them. The computations are very intensive (even for n=5) but give some feeling of the size and degree of minimal generating sets. The bounds given by Hironaka decompositions seem very loose.

The basic principle of the classical algorithms is to construct generating sets degree by degree, from 1 up to the best degree bound known. Since the complexity of the computations involved usually increases quickly with increasing degree, the quality of the degree bound is crucial. One can take advantage of the existence of a Hironaka decomposition by computing secondary invariants and, while doing so, selecting the secondary invariants that are irreducible (i.e. that cannot be expressed as products of lower degree secondary invariants). The irreducible secondary invariants together with the primary invariants form a minimal generating set (some primary invariants may need to be removed).

Most software [16] relies on a precomputation of a Gröbner basis of the system of parameters to greatly speed up the rest of the computations. However, with In this precomputation is very hard, if not impossible (see § 4). Software that do not rely on this precomputation uses linear algebra on the homogeneous component of degree d of the whole ring of polynomials, whose dimension grows quickly with increasing d, and fail early.

Since our group is a permutation group, invariants can be stored as linear combinations of invariants xgˆ*. This saves a lot of memory (up to a factor of 1/| Gn| for monomials without symmetries, which happens to be the case for most of them). This data structure also allows for the same linear algebra operations inside the homogeneous component of degree d of the invariant ring which is considerably smaller. We therefore implemented our own invariant theory software PerMuVAR which takes advantage of the particular properties of permutation groups [32]. We chose the computer algebra system MuPAD , which is freely available (but alas not open source software), and allows modularity through object oriented programming. Moreover, MuPAD 's dynamic modules will allow for rewriting critical sections in a very efficient language like C++.

A sketch of the algorithm follows. We denote by ⟨θ1,...,θm⟩d the homogeneous component of degree d of the ideal generated by (θ1,...,θm) in I(G).
Algorithm 5.1  [Computing secondary invariants]   Input: a system of parameters (θ1,...,θm) and a function nextInvariant(d) which iterates through a set of invariants of degree d spanning I(G)d as a vector space.
Output: (irreducible) secondary invariants.
Some comments about this algorithm are in order:

(i) In the last loop, the Hilbert series provides a stopping condition, since the number of secondary invariants is known. To maintain efficiency, the elements of L are mutually reduced by Gauss elimination. Testing if p is in the vector space generated by L amounts to reducing it modulo L; inserting it into L amounts to further reducing the elements of L by p. Therefore, this algorithm is essentially a step by step matrix inversion by Gauss elimination, and the cost for each degree is about (dim I(G)d3.

(ii) The main waste of memory and time in this algorithm is the explicit computation of the vector space basis L of ⟨θ1,...,θm⟩d. It would be nice to work directly in the quotient of I(G) by the ideal ⟨θ1,...,θm⟩, as in the algorithm based on a Gröbner basis precomputation. This approach is further developed in [31].

(iii) By properly keeping track of the reductions in L, we can determine which primary invariants should be removed in order to obtain a minimal generating set. In addition, by properly choosing the nextInvariant function, we can check whether a given set of invariants is generating, and if not construct counter-examples.

For n=5, we could only compute a partial minimal generating set S5 up to degree 10, whereas the best a priori degree bound is β( In)≤22. However, s10( In)=0 (i.e. a minimal generating set contains no invariant of degree 10), and Figure 2 strongly suggested that sd( In)=0 for any d≥10. This has been checked by Kemper [18], using ad hoc computations, thus proving that S5 is a minimal generating set (see § 9 for a possible alternative approach). Therefore, β( I4)=5, and β( I5)=9.
Conjecture 5.2   If n≥4, β( In)=(
n
2
) -1.


Figure 2: sd( In): number of invariants per degree d in a minimal generating set of In

6   The Gorenstein property

In this section, we show that the invariant ring In is Gorenstein when n is even, which indicates several duality properties of In. In particular, et = d1+...+dm - m and there are as many secondary invariants of degree et-d and degree d. Actually, this could be used to considerably speed up the construction of secondary invariants [32].

Lemma 6.1   (i) Let σ be a permutation of the vertices, that is an element of Sn, and σ be the corresponding permutation of the edges in Gn. Then:
sign(
σ
)
=sign(σ)   if n is odd,
sign(
σ
)
=1   if n is even.

(ii) If n is even, Gn is a subgroup of the special linear group SL(V).

(iii) If n is odd, the representation of Sn on the irreducible component [n-2,2] is a subgroup of SL(V).
Proof: (i) If σ is a transposition of 2 vertices, then σ exchanges n-2 pairs of edges, and sign(σ)=(-1)n-2.

(iii) Take σ∈ Sn, and M the matrix of the representation of σ on the component [n-2,2]. The determinant of the representation of σ on Vn is sign(σ), whereas the sign of the representation of σ on the other component [n]⊕[n-1,1] is sign(σ) (natural representation of Sn). Therefore, det(M)=sign(σ)/sign(σ)=1, if n is odd. QED

Then, Watanabee's theorem [27, § 8] applies.
Theorem 6.2   (i) When n is even, In is Gorenstein.

(ii) When n is odd, the invariant ring over the irreducible component [n-2,2] is Gorenstein.

7   The chain product

We have discussed the power of the grading of the invariant ring. We now define another product on the invariant ring In, called the chain product, which preserves a finer grading and has a nice computational behavior. Most algebraic properties of the invariant ring with respect to the chain product transfer back to the usual product. We only construct and use the chain product for In, but it generalizes to any permutation group [32].

Let g be a multigraph. As in the following example, it can be interpreted as a superposition of simple graphs g1,g2,⋯,gk, where g1⊇g2⊇⋯⊇gk:
   ←→    ⊇ ⊇
Thus, g can be identified with the multichain (i.e. chain with repetitions) C(g):=g1⊇g2⊇⋯⊇gk of simple graphs. The shape λ(g) of g is the decreasing sequence of the sizes of the simple graphs in C(g). Here, λ(g)=(5,3,3). A polynomial is called finely-homogeneous if all its monomials have the same shape. Since two monomials xg and xg' in the same Sn-orbit have the same shape, any invariant decomposes into a sum of finely-homogeneous invariants. Therefore, the shape defines a fine grading on the invariant ring In, and we denote by In,(5,3,3) the finely homogeneous component of In for the shape (5,3,3).

The usual product does not preserve this grading:
( )
ˆ*
 
 
 
( )
ˆ*
 
 
 =
( )
ˆ*
 
 
 + 2
( )
ˆ*
 
 
 + 2
( )
ˆ*
 
 
 .
The chain product xg⋆xh of two monomials xg and xh is the usual product of xg and xh if the two multichains C(g) and C(h) can be merged into another multichain, and zero otherwise. The chain product extends to invariants, and yields for example:
( )
ˆ*
 
 
 ⋆
( )
ˆ*
 
 
 =
( )
ˆ*
 
 
 
The chain product preserves the fine grading of the invariant ring, since the shape xg⋆xh can be obtained by merging the shapes of g and h.

The invariant ring In together with the chain product is actually isomorphic to the Stanley-Reisner ring of the poset of unlabelled graphs on n vertices ordered by subgraph. Stanley-Reisner rings of posets have been intensively studied, in particular by Garsia and Stanton [11] to construct Hironaka decompositions of invariant rings of certain permutation groups. We did not succeed in using this theoretical framework to get a Hironaka decomposition of In. The need of taking the elementary symmetric polynomials as a system of parameters causes the main difficulty. Indeed, this is not a low degree system of parameters and there are too many secondary invariants. However, even our naive point of view of the Stanley-Reisner ring as an alternative product on In yields dramatic speed ups of the computations.

The following proposition is the heart of this technique.
Proposition 7.1  [[11]]   A Hironaka decomposition of In for the chain product, is also a Hironaka decomposition of In for the usual product.
The key of the proof is that, if p and q are finely homogeneous, the maximal finely homogeneous component of pq is exactly p⋆ q. The result follows by induction over the fine grading. We used the same principle to prove a similar result on generating sets.
Proposition 7.2   A generating set of In for the chain product is a generating set of In for the usual product.
In all our examples, however, minimal generating sets for the chain product were far from being minimal for the usual product.

The elementary symmetric polynomials form a system of parameters for the chain product. We do not know if there are other systems of parameters, since the usual characterization from proposition 4.4 does not apply for the chain product. In particular, the symmetric power sums do not form a system of parameters for the chain product. They are not even algebraically independent since ∑ x{i,j}k=(∑ x{i,j})k. Given the size of the minimal generating sets we computed, there are no systems of parameters for the chain product with degrees as low as in conjecture 4.1.

In [32], we describe how to use this product for faster computations. Practically, we could push the computation of a partial minimal generating set S for I5 up to the degree 22 instead of only 10. This is a significant progress, considering that the dimension of I5,22 is 174403, whereas the dimension of I5,10 is only 974. Unfortunately, we cannot use a low-degrees system of parameters, so the degree bound is 42 instead of 22. This means that there is still a lot of work to do to get a full minimal generating set for the chain product. On the other hand, this partial computation yields a generating set for the usual product, since β( I5)≤22.
Proposition 7.3   The computed set S is a generating set of I5 for the usual product. However, S has more than one thousand invariants of degree up to 22.

To conclude, the usual product allowed us to compute a small set, with is minimal, but not necessarily generating, whereas the chain product allowed us to compute a set which is generating, but far from being minimal.

8   The invariant ring for n=∞

In this section, we study the projective limit I∞ of the invariant ring, and get back some information on In.

A multigraph g on n'≤ n non-isolated vertices can be identified with a multigraph on n vertices by adding n-n' isolated vertices. This defines xgˆ* in In. The set Bn of all invariants xgˆ*, where g is a multigraph on less than n non-isolated vertices, is obviously a vector space basis of In. For n'≤ n, let Φn' be the linear projection from In to In' which maps xgˆ* (in In) to 0 if g has strictly more than n' non-isolated vertices, and to xgˆ* (in In') otherwise. Our definition of the exponential (see § 1.3) makes it a surjective morphism of graded algebra. The projective limit of In:
I
 
1
Φ1
 
 
I
 
2
Φ2
 
 
... I
 
n
Φn
 
 
... I
 
∞
,
defines a graded algebra I∞, with a canonical vector space basis B∞:={xgˆ*} indexed by the multigraphs g on a finite number of non-isolated vertices.

Proposition 8.1   (i) I∞ is the free polynomial ring over C:={xgˆ*  |   g is connected}.

(ii) The canonical morphism of graded algebra Φn: I∞ In is an isomorphism up to the degree ⌊n/2⌋.
Proof: (i) Following the proof of proposition 2.1 (ii), C generates I∞. Now, let g1,...,gk be k>0 connected multigraphs. In the product xg1ˆ*⋯xgkˆ*, there is a term xhˆ* with coefficient 1, where h is the disconnected multigraph whose connected components are precisely the gi. This term is a marker of the product xg1ˆ*⋯xgkˆ* in any non-trivial polynomial combination of elements of S. The algebraic independence follows.

Any multigraph with d edges and no isolated vertices has less than 2d vertices. (ii) follows. QED

Corollary 8.2   β( In)≥ ⌊n/2⌋.
This lower bound is loose: for n≤5, we know that β( In)≥(
n
2
)-1 and for 11≤ n≤18, it follows from theorem 2.3 (ii) that β( In)≥ n-2. We expect that refining this technique will yield much better lower bounds.

By (ii), the Hilbert series H( I∞,z) is the limit of the Hilbert series H( In,z) as n goes to infinity, and by (i)
H( I
 
∞
,z)=
∞
 
d=1
1
(1-zd)
nd
 
,
where nd is the number of connected multigraphs with d edges. We do not know how to directly compute H( In,z), or whether there exists a closed form formula. The only asymptotic studies we have seen in the literature deal with n fixed and d going to infinity [15].

9   Unimodality

A startling fact revealed by our computations of minimal generating sets (MGS) lies in Figure 2, which shows the coefficients of s( In,z). For n≤4 and most likely for n=5, this polynomial is unimodal: the coefficients first increase with the degree, and then decrease down to 0.
Conjecture 9.1   The polynomial s( In,z) is unimodal.
This would prove that the partial minimal generating set we computed for n=5 is generating, and provide a very nice stopping condition for algorithm 5.1.

To figure out which properties of Gn could be useful to prove this conjecture, we extend it to general groups of matrices. A finite subgroup G of GL(V) is MGS-unimodal if the polynomial s(I(G),z) is unimodal.
Problem 9.2   Characterize MGS-unimodal groups.
Not all groups are MGS-unimodal. Indeed, let G be the subgroup of GL(C2) generated by the matrix
M:=
é
ê
ë
j 0
0
j
ù
ú
û
,
where j and j are the two non-trivial third roots of unity. Obviously, (x1x2, x13, x23) is a minimal generating set of I(G), and s(G,z)=z+0z2+2z3, which is not unimodal.

Whereas the irreducible representations of the symmetric group are thoroughly described, their invariants rings are barely known. In an amazing but very technical paper [7], Dixmier has been able to construct by hand minimal generating sets for several irreducible representations of Sn, including all the irreducible representations of S1,..., S5, except [3,1,1]. It follows that the representations [n],[n-1,1], [2,2] and [3,2] are MGS-unimodal, whereas the representations [2,1n-2] for n≥4 and [2,2,1] are not. This proves the existence non-MGS-unimodal irreducible representations of the symmetric group.

The trivial group, the full symmetric group and multisymmetric polynomials are MGS-unimodal. We checked with PerMuVAR that several other small permutation groups are MGS-unimodal. It's tempting to conjecture that all permutation groups are MGS-unimodal, since they give rise to a lot of unimodality properties (see [28]; note that, as opposite to here, the corresponding series are always either log-concave or symmetric). However, for n≥4, the alternating group An is not MGS-unimodal. Indeed, I( An) is generated by the elementary symmetric polynomials of degrees 1,...,n together with the Van-der-Monde determinant ∏i<j (xi-xj) of degree (
n
2
).

Figure 1 also shows that, up to n=21, the generating series of the secondary invariants is unimodal (except at d=0 and possibly d=et), and very smooth.
Conjecture 9.3   Let G be a permutation group, and (θ1,...,θm) be a system of parameters of I(G). Then, the generating series of the secondary invariants is unimodal, except for d=0 and possibly d=et.
We recall that this series can be computed directly from the Hilbert series. Therefore a careful study of the Hilbert series might yield a simple proof of this conjecture.

10   The invariant ring over digraphs

In [14], Grigoriev introduced a related invariant ring, the invariant ring over digraphs (digraphs are directed graphs, with loops). The definition is similar to the one for the invariant ring over graphs, but there are n2 variables (x1,1,x1,2,...,xn,n), indexed by the pairs (i,j) of {1,...,n}. The action of Sn is then defined by σ⋅ xi,j:=xσ(i),σ(j). In this section, we denote by In the invariant ring over digraphs. More generally, Grigoriev defined the invariant ring over oriented k-hypergraphs, with nk variables indexed by k-uples of {1,...,n}.

Lemma 1 of [14] states that In is generated by the invariants xgˆ*, where g is a simple digraph. The proof is said to be an easy generalization of the usual proof of the fundamental theorem of symmetric functions. This surprised us, since we proved this was false in In (theorem 2.3 (ii)). Therefore, we checked the condition 1.2, which failed even for n=3 and degree 5. We then ran PerMuVAR to try to compute a minimal generating set using only simple digraphs. It failed as expected, and produced the two following very small invariants, which are not generated by simple digraphs:
( )
ˆ*
 
 
 ,
 
( )
ˆ*
 
 
 .
These counter-examples to lemma 1 of [14] can also easily be checked by hand.

This was disappointing. Indeed, the invariant ring In is the quotient ring of In by the ideal generated by xi,i=0 and xi,j=xj,i. Therefore, we could have used lemma 1 to prove that In is generated by the invariants where each variable appears with degree at most 2. This would provide a pretty good degree bound β( In)≤ 2(
n
2
). Moreover, we could use this together with computations of partial minimal generating sets to prove that I5 is generated by the invariants xgˆ*, where g is a multigraph with at least one isolated vertex, result of interest for the reconstruction problem.

Most of the results on In apply as well for In, but since the number of variables is greater, the computations are even harder than for In, even if we ignore loops.

11   The field of invariant fractions

The field of invariants K(x{i,j}) Sn is the subfield of all rational fractions of K(x{i,j}) which remain invariant under the action of the group. The following classical lemma is valid for any finite group of matrices.
Lemma 11.1   The field of invariant is exactly the field of fractions of the invariant ring.
Proof: By averaging over the group, write any invariant fraction as p/q where p and q are invariant polynomials. QED

In [14], Grigoriev used basic Galois theory to prove the existence of a generating set of the field of invariants composed of m+1 invariants of degree less than m. The principle is to first take the m elementary symmetric polynomials, and to consider the subfield of symmetric fractions. Since the ground field K has characteristic zero (this would be also the case for any normal ground field, like a finite field), the primitive element theorem applies: there exist a primitive element p which generates the field of invariants over the field of symmetric fractions. Therefore, the m elementary symmetric polynomials together with p generates the field of invariants.

However, Grigoriev did not provide a way to construct such an element. Moreover, the proof that it could be chosen of degree less than m was incorrect, since it relied on lemma 1 of [14] which we disproved in § 10.

Theorem 11.2   Let n≥4. The field of invariants over graphs (respectively over digraphs) is generated by the elementary symmetric polynomials together with:
p:=
( )
ˆ*
 
 
 ,
 
respectively p:=
( )
ˆ*
 
 
 .
Proof: Key fact: in both cases a permutation of the edges belongs to the group if and only if it leaves p invariant. QED

Grigoriev also stated that such a generating set would be a complete system of invariants. This is incorrect since, unlike a generating set of the invariant ring, a generating set of the field of fraction is not necessarily a complete system of invariants. For example, our generating sets do not separate the following pairs of non-isomorphic graphs:
{ , } ;
 
{ , } .

In some cases, the field of invariants can be used to indirectly apply Galois theory on the invariant ring.
Theorem 11.3   If n≢4,5,6,8, there is no intermediate invariant ring of matrix group between the ring of symmetric polynomials (respectively the ring of alternate polynomials for n even) and the ring of invariants In.
Proof: For n≢4,5,6,8, the group Gn is a maximal proper subgroup of the symmetric group Sm (respectively the alternate group Am for n even) [8]. Basic Galois theory then proves the theorem for the field of invariants, and lemma 11.1 transfers it back to the invariant ring. QED

12   Conclusion

Invariant theory provides both very general tools and algorithms to study the invariant ring In over graphs. Unfortunately, the computer exploration of small cases appears to be very hard and shows that those tools and algorithms lack accuracy and efficiency for our particular invariant ring. However, we could still obtain a few results, formulate conjectures related to In, and solve a problem arising from graph theory.

Acknowledgments

This research was partially funded by the Région Rhône-Alpes. We gratefully thank A. Garsia, J-C. Faugère and N. Wallach for the time invested trying to compute a Gröbner basis for conjecture 4.2. In particular, discussions with A. Garsia where very helpful, and raised decisive ideas. Finally, we would like to thank M. Pouzet for introducing and guiding us through this beautiful subject.

References

[1]
Aslaksen, H., Chan, S.-P., and Gulliksen, T. Invariants of S4 and the shape of sets of vectors. Appl. Algebra Engrg. Comm. Comput. 7, 1 (1996), 53--57.

[2]
Bondy, J. A. A graph reconstructor's manual. In Surveys in combinatorics, 1991 (Guildford, 1991), vol. 166 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 1991, pp. 221--252.

[3]
Cameron, P. J. Stories from the age of reconstruction. Congr. Numer. 113 (1996), 31--41. Festschrift for C. St. J. A. Nash-Williams.

[4]
Capani, A., Niesi, G., and Robbiano, L. Cocoa, a system for doing computations in commutative algebra. Available via anonymous ftp from: cocoa.dima.unige.it.

[5]
Cox, D., Little, J., and O'Shea, D. Ideals, varieties, and algorithms, second ed. Springer-Verlag, New York, 1997. An introduction to computational algebraic geometry and commutative algebra.

[6]
Derksen, H., and Kraft, H. Constructive invariant theory. In Algèbre non commutative, groupes quantiques et invariants (Reims, 1995). Soc. Math. France, Paris, 1997, pp. 221--244.

[7]
Dixmier, J. Sur les invariants du groupe symétrique dans certaines représentations. II. In Topics in invariant theory (Paris, 1989/1990), vol. 1478 of Lecture Notes in Math. Springer, Berlin, 1991, pp. 1--34.

[8]
Faradzev, I. A., Ivanov, A. A., Klin, M. H., and Woldar, A. J., Eds. Investigations in algebraic theory of combinatorial objects. Kluwer Academic Publishers Group, Dordrecht, 1994.

[9]
Faugère, J.-C. A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139, 1-3 (1999), 61--88. Effective methods in algebraic geometry (Saint-Malo, 1998).

[10]
Fulton, W., and Harris, J. Representation theory, vol. 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991 - 1996. A first course, Readings in Mathematics.

[11]
Garsia, A. M., and Stanton, D. Group actions of Stanley - Reisner rings and invariants of permutation groups. Adv. in Math. 51, 2 (1984), 107--201.

[12]
Garsia, A. M., and Wallach, N. Personnal communication, Feb. 1999.

[13]
Göbel, M. A constructive description of SAGBI bases for polynomial invariants of permutation groups. J. Symbolic Comput. 26, 3 (1998), 261--272.

[14]
Grigoriev, D. J. Two reductions of the graph isomorphism to problems for polynomials. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 88 (1979), 56--61, 237--238. Studies in constructive mathematics and mathematical logic, VIII.

[15]
Harary, F., and Palmer, E. M. Graphical enumeration. Academic Press, New York, 1973.

[16]
Kemper, G. The invar package for calculating rings of invariants. IWR Preprint 93-94, University of Heidelberg, 1993.

[17]
Kemper, G. Computational invariant theory. Queen's Papers in Pure and Applied Math. (Feb. 1998).

[18]
Kemper, G. Complete computation of a minimal generating set of the invariant rings over graphs on 5 nodes. personal communication, 2000.

[19]
Kocay, W. L. Some new methods in reconstruction theory. In Combinatorial mathematics, IX (Brisbane, 1981). Springer, Berlin, 1982, pp. 89--114.

[20]
Mallows, C. L., and Sloane, N. J. A. On the invariants of a linear group of order 336. Proc. Cambridge Philos. Soc. 74 (1973), 435--440.

[21]
Pouzet, M. Quelques remarques sur les résultats de Tutte concernant le problème de Ulam. Publ. Dép. Math. (Lyon) 14, 2 (1977), 1--8.

[22]
Pouzet, M. Note sur le problème de Ulam. J. Combin. Theory Ser. B 27, 3 (1979), 231--236.

[23]
Pouzet, M., and Thiéry, N. M. Algebraic invariants of graphs and reconstruction. Discrete Mathematics (2001). In preparation.

[24]
Robbiano, L., and Sweedler, M. Subalgebra bases. In Commutative algebra (Salvador, 1988). Springer, Berlin, 1990, pp. 61--87.

[25]
Schmid, B. J. Finite groups and invariant theory. In Topics in invariant theory (Paris, 1989/1990). Springer, Berlin, 1991, pp. 35--66.

[26]
Smith, L. Polynomial invariants of finite groups. A survey of recent developments. Bull. Amer. Math. Soc. (N.S.) 34, 3 (1997), 211--250.

[27]
Stanley, R. P. Invariants of finite groups and their applications to combinatorics. Bull. Amer. Math. Soc. (N.S.) 1, 3 (1979), 475--511.

[28]
Stanley, R. P. Log-concave and unimodal sequences in algebra, combinatorics, and geometry. In Graph theory and its applications: East and West (Jinan, 1986). New York Acad. Sci., New York, 1989, pp. 500--535.

[29]
Sturmfels, B. Algorithms in invariant theory. Springer-Verlag, Vienna, 1993.

[30]
Thiéry, N. M. Invariants algébriques de graphes et reconstruction; une étude expérimentale. PhD thesis, Université Lyon I, June 1999. N∘ d'ordre: 167-99.

[31]
Thiéry, N. M. Computing minimal generating sets of invariant rings of permutation groups with SAGBI-Gröbner basis. In International conference DM-CCG, Discrete Models - Combinatorics, Computation and Geometry, Paris, July 2-5 2001 (2001). Submitted.

[32]
Thiéry, N. M. PerMuVAR, a library for computing in invariant rings of permutation groups. Journal of Symbolic Computations (2001). In preparation.
1
Using ad hoc computations, Kemper [18] checked recently that this system was indeed a complete minimal generating set, thus proving that β( I5)=9.
This document was translated from LATEX by HEVEA.