I've been working on a talk based on some stuff in Olver's "Classical Invariant Theory" book and have been wondering about a related graph enumeration problem.

Start with a triple $(n,v,e)$ of natural numbers. Take all $\mathbb{Q}$-linear combinations of directed graphs (allowing multiple edges, but no loops) with $v$ vertices, $e$ edges, and each vertex has at most $n$ edges going to it or coming from it. Now, take three relations (images scanned from Olver)

Rule 1: alt text

Rule 2: alt text

Rule 3: alt text

Where the function $v$ with a vertex as subscript next to a graph means that graph multiplied by $n$ minus the number of edges attached to that vertex. (So, for instance, an isolated vertex gets multiplied by $n$)

Denote the space after quotienting by these relations by $V_{n,v,e}$. And so, in final form, my question:

What is $\dim V_{n,v,e}$? Or at least, can we find relatively effective upper bounds?

EDIT: Some clarifications. The colorings on the vertices are just to mark them in the pictures to keep track of where everything goes, the graphs are not marked themselves. Additionally, as Rule 2 is slightly unclear from the scan, the $v$ function is always the vertex not attached to the arrow in the configuration.

  • $\begingroup$ Charles, what are the white and black vertices? $\endgroup$
    – Gil Kalai
    Jan 17, 2010 at 20:42
  • $\begingroup$ They're just markings to keep track of how the subgraph lies within the larger graph. So that the first rule says that you change signs if you change an orientation, the third is analgous to the Kauffman bracket in knot theory, and the second...the second is the one I don't have good intuition for, but seems to be the most useful one for showing equivalences. $\endgroup$ Jan 17, 2010 at 21:00
  • $\begingroup$ @CharlesSiegel What do Rules 2 and 3 mean from graph theory? $\endgroup$
    – Turbo
    Nov 24, 2017 at 23:02

2 Answers 2


The number ${\rm dim}\ V_{n,v,e}$ is the number of linearly independent covariants of degree $v$ and weight $e$ of a binary form of degree $n$. This is the multiplicity of the irreducible module $Sym^k(\mathbb{C}^2)$ in the plethysm $Sym^v(Sym^n(\mathbb{C}^2))$, where $k=nv-2e$. There is formula for that involving counting integer partitions (Cayley-Sylvester formula). The easiest way to derive it that I know of is by computing the character which is a Gaussian polynomial. I think the book by Mukai does that. You can also look up http://arxiv.org/abs/math/0110224

  • $\begingroup$ See also the discussion in comments to Bruce Westbury's answer. $\endgroup$ Jul 9, 2010 at 8:15

I've been fascinated by this and never got to the bottom of it. I hesitate to offer this as a reply but I think this question deserves some response. I apologise if you already know this.

As I understand it (and please correct me if I go wrong) the fundamental problem introduced back in Chapter 2 is to understand the space of covariants of given degree $n$, order $p$, weight $w$ (with relation (2.33)). In the language of representations we take the $p$-th symmetric power of the $n$-th symmetric power of the defining representation of $GL(2)$. Then we take the isotypic subspace corresponding to $\det^{-w}$. Judging by the table on page 40 and the accompanying discussion the dimensions of these spaces are difficult to compute. My understanding is that even with current computers it is still difficult.

Each graph gives a covariant by some process I find obscure and the the graphical relations correspond to linear relations. By the first and second fundamental theorems the vector spaces you ask about are identified with the spaces of covariants (although the names of the parameters seem to have been changed).

The dimensions of the spaces of covariants are normally expressed in terms of Hilbert series and these can in principle be calculated (using Molien's theorem). For each $n$ this is a rational function. These are known for $n=1,2,3$ but rapidly become unwieldy and uninformative. It would seem plausible that the asymptotics of the Hilbert series can be calculated without finding the rational function.

Again, I expect I am simply rephrasing the question, not answering it.

  • $\begingroup$ Doesn't Molien's Theorem only apply to invariants of finite groups? $\endgroup$ Jun 16, 2010 at 15:23
  • 1
    $\begingroup$ I think you can adapt it to compact groups using a group integral (in this case $U(2)$). You would also need to take into account that here we are looking for the multiplicity of a non-trivial representation. $\endgroup$ Jun 16, 2010 at 15:27
  • $\begingroup$ This is discussed with considerable detail in Section 4.4 in: MR2004218 (2004g:14002) Mukai, Shigeru . An introduction to invariants and moduli. Cambridge Studies in Advanced Mathematics, 81. Cambridge University Press, Cambridge, 2003. xx+503 pp. ISBN: 0-521-80906-1 $\endgroup$ Jun 16, 2010 at 15:39
  • $\begingroup$ Both Olver and Mukai do quadratic, cubic and quartic forms in detail. They have different numbers of generators and I am unable to explain this. $\endgroup$ Jun 16, 2010 at 19:46
  • $\begingroup$ With all due respect to Olver, I was never able to gain any insight from his book. On the other hand, if it's a question of computation of the $\textit{multiplicities}$ in the isotypical decomposition (as opposed to the $\textit{algebra generators}$), that is straightforward. The answer involves partitions, so if presented in a table format, the pattern may not be immediately recognizable. $\endgroup$ Jun 16, 2010 at 23:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .