text:
# The critical group of a directed graph

## 1. Introduction.

We use the word *graph* to refer to a finite, possibly directed, multigraph. If a graph is undirected then we consider each of its edges to represent a pair of directed edges with opposite orientations. (In particular, an undirected loop represents two directed loops.) The *adjacency matrix* $`A(G)`$ of a graph $`G=(V,E)`$ is indexed by $`V\times V`$, with $`vw`$–entry $`A_{vw}`$ being the number of directed edges of $`G`$ with initial vertex $`v`$ and terminal vertex $`w`$. The matrix $`\mathrm{\Delta }(G)`$ is indexed by $`V\times V`$, with diagonal entry $`\mathrm{\Delta }_{vv}:=_{wV}A_{vw}`$ being the outdegree of the vertex $`v`$, and with zero off-diagonal entries. The *Laplacian matrix* of $`G`$ is $`Q(G):=\mathrm{\Delta }(G)A(G)`$.

The (*full*) *critical group* $`𝒦(G)`$ of $`G=(V,E)`$ is the cokernel of the transpose of its Laplacian matrix acting on $`𝐙^V`$; that is,

$$𝒦(G):=𝐙^V/Q^{}(G)𝐙^V.$$

This is a finitely generated abelian group. Also, we define the *reduced critical group* $`K(G)`$ of $`G`$ to be the torsion subgroup of $`𝒦(G)`$; that is, the subgroup of $`𝒦(G)`$ consisting of all elements of finite order. For a connected, undirected graph $`G`$, this $`K(G)`$ is the ‘Jacobian group’ defined by Bacher, de la Harpe, and Nagnibeda  and studied further by Biggs  under the term ‘critical group’. Our goal here is to investigate the relationship between the combinatorial structure of graphs and the algebraic structure of their critical groups as generally as possible. Since the Laplacian matrix is insensitive to loops in a graph, we might as well restrict attention to loopless graphs; it is only in Section 9, however, that we really require this restriction.

Section 2 contains some preliminary observations. In Section 3, we determine the rank of $`𝒦(G)`$ combinatorially. In Section 4, we consider the minimal number of generators of $`K(G)`$; this is a much more difficult invariant of $`G`$ than the rank of $`𝒦(G)`$, and we obtain only a weak upper bound for it. In Sections 5 and 6, we show that $`𝒦(G/\pi )`$ is (isomorphic to) a subgroup of $`𝒦(G)`$ when $`\pi `$ is an equitable partition of a strongly connected graph $`G`$. In Section 7, we prove some isomorphism theorems, with the consequence that for an undirected graph $`G`$, the reduced critical group $`K(G)`$ depends only on the graphic matroid of $`G`$. In Section 8, we show that, for a connected undirected graph $`G`$, there is no ‘natural’ bijection between $`K(G)`$ and the set of spanning trees of $`G`$, even though these sets are equicardinal. In Section 9, we revisit the ‘dollar game’ of Biggs  in the more general setting of strongly connected graphs. The theory is almost the same as for undirected graphs, with one interesting new complication. Throughout the paper, we indicate various conjectures and open problems.

## 2. Preliminaries.

Let $`G`$ be a graph with $`n(G)`$ vertices. By the structure theorem for finitely generated abelian groups, there are nonnegative integers $`g_1`$,…, $`g_n`$ such that $`g_i`$ divides $`g_{i+1}`$ for each $`1in1`$ and

$$𝒦(G)(𝐙/g_1𝐙)(𝐙/g_2𝐙)\mathrm{}(𝐙/g_n𝐙).$$

(Of course, $`𝐙/1𝐙=0`$ is the trivial group and $`𝐙/0𝐙=𝐙`$.) These integers are computed by reducing $`Q(G)`$ to its Smith normal form. Say that two $`n`$-by-$`n`$ integer matrices $`M`$ and $`M^{}`$ are *equivalent*, denoted by $`MM^{}`$, if and only if there exist $`n`$-by-$`n`$ integer matrices $`L`$ and $`N`$ with determinant $`\pm 1`$ such that $`LMN=M^{}`$. That is, $`M`$ can be transformed to $`M^{}`$ by applying elementary row and column operations which are invertible over the integers. It is not difficult to verify that every $`n`$-by-$`n`$ integer matrix $`M`$ is equivalent to a diagonal matrix $`\mathrm{diag}(g_1,g_2,\mathrm{},g_n)`$ of nonnegative integers such that $`g_i`$ divides $`g_{i+1}`$ for each $`1in1`$, and that this matrix $`\mathrm{snf}(M)`$ is determined uniquely by $`M`$. This is the *Smith normal form* of $`M`$.

We define the *dual critical group* of $`G`$ to be

$$𝒦^{}(G):=𝐙^V/Q(G)𝐙^V,$$

the cokernel of the Laplacian of $`G`$ acting on $`𝐙^V`$. It is clear that for any square integer matrix $`M`$, $`\mathrm{snf}(M^{})=\mathrm{snf}(M)`$, from which Proposition 2.1 follows.

###### Proposition 2.1.

For any graph $`G`$, $`𝒦^{}(G)`$ is isomorphic to $`𝒦(G).`$

Of course, $`G`$ is undirected if and only if $`Q^{}=Q`$, in which case $`𝒦^{}(G)=𝒦(G)`$. In general, however, the isomorphism in Proposition 2.1 depends on a choice of matrices $`L`$ and $`N`$ such that $`LQN=\mathrm{snf}(Q)=N^{}Q^{}L^{}`$, and hence is not natural. These dual critical groups will be useful in Section 6.

If $`G`$ is a graph with weak components $`G_1,\mathrm{},G_c`$, then $`Q(G)=Q(G_1)\mathrm{}Q(G_c)`$ is block-diagonal, from which Proposition $`2.2`$ follows.

###### Proposition 2.2.

If $`G`$ is a graph with weak components $`G_1,\mathrm{},G_c`$, then

$$𝒦(G)=𝒦(G_1)\mathrm{}𝒦(G_c).$$

Proposition $`2.3`$ is essentially the Matrix-Tree Theorem; see Theorem 6.3 of Biggs  or Theorem 7.3 of Biggs .

###### Proposition 2.3.

If $`G`$ is connected and undirected then the order of $`K(G)`$ is $`\kappa (G)`$, the number of spanning trees of $`G`$.

We use the slightly odd but convenient notations $`M_{vw}`$ for the $`(v,w)`$-entry of a $`V`$-by-$`V`$ matrix $`M`$, but $`x(v)`$ for the $`v`$-th entry of a $`V`$-indexed vector $`𝐱`$. Also, $`\mathrm{𝟏}`$ denotes the all-ones vector, and $`\mathrm{𝟎}`$ denotes the zero vector.

## 3. The torsion-free part of $`𝒦(G)`$.

For each natural number $`g`$, let $`\mu _g(G)`$ denote the multiplicity with which $`g`$ occurs on the diagonal of $`\mathrm{snf}(Q^{}(G))`$. Thus, $`\mu _0(G)`$ is the rank of $`𝒦(G)`$, so that $`𝒦(G)K(G)𝐙^{\mu _0(G)}.`$ In this section we determine the combinatorial meaning of $`\mu _0(G)`$ for any graph $`G`$.

Since

$$(𝐙/g𝐙)𝐑=\{\begin{array}{cc}𝐑\hfill & \mathrm{if}g=0,\hfill \\ 0\hfill & \mathrm{if}g0,\hfill \end{array}$$

for all nonnegative integers $`g`$, and since tensor product distributes across direct sums, we see that

$$\mu _0(G)=dim_𝐑𝒦(G)𝐑=dim_𝐑𝐑^V/Q^{}𝐑^V=dim_𝐑\mathrm{ker}(Q^{}).$$

The results of this section, determining $`dim_𝐑\mathrm{ker}(Q^{})`$ combinatorially, are well-known, but we repeat the short proofs for completeness and the readers’ convenience.

###### Lemma 3.1.

Let $`G`$ be a strongly connected graph.
(a) The kernel of $`Q`$ acting on $`𝐑^V`$ is $`𝐑\mathrm{𝟏}`$, the span of the all-ones vector.
(b) If $`T`$ is a diagonal matrix with nonnegative real entries, then either $`T=O`$ or $`Q+T`$ is invertible over $`𝐑`$.

###### Proof.

We prove (a) and (b) together by showing that for $`T`$ as in part (b) and $`𝐳\mathrm{𝟎}`$, if $`(Q+T)𝐳=\mathrm{𝟎}`$ then $`T=O`$ and $`𝐳=c\mathrm{𝟏}`$ for some $`c𝐑`$. With these hypotheses, choose any vertex $`vV`$ such that $`|z(v)|>0`$ is maximum. Then, since $`(\mathrm{\Delta }+T)𝐳=A𝐳`$ we see that

$$(\mathrm{\Delta }_{vv}+T_{vv})z(v)=\underset{wV}{}A_{vw}z(w).$$

Since there are $`\mathrm{\Delta }_{vv}`$ terms on the right side (considering $`A_{vw}`$ as the multiplicity of the term $`z(w)`$) and each of these has absolute value at most $`|z(v)|`$, it follows that $`T_{vv}=0`$ and $`z(w)=z(v)`$ for all $`wV`$ such that $`A_{vw}0`$. Now, we may repeat this argument with any such vertex $`w`$ in place of $`v`$, *et cetera*. Since $`G`$ is strongly connected, it follows that $`T=O`$ and $`𝐳=z(v)\mathrm{𝟏}`$, completing the proof. ∎

###### Proposition 3.2.

Let $`G`$ be a strongly connected graph. There is a unique vector $`𝐡𝐑^V`$ such that $`Q^{}𝐡=\mathrm{𝟎}`$, the entries of $`𝐡`$ are positive integers, and $`\mathrm{gcd}\{h(v):vV\}=1`$. Moreover, $`\mathrm{ker}(Q^{})=\mathrm{𝐑𝐡}`$.

###### Proof.

If $`G`$ has a single vertex then the result is trivial, so assume $`n(G)2`$. Now, since $`G`$ is strongly connected, the matrix $`\mathrm{\Delta }`$ is invertible. Since $`\mathrm{ker}(Q)`$ is one-dimensional, $`\mathrm{ker}(Q^{})`$ is also one-dimensional; hence there is a unique (nonzero) vector $`𝐳`$ such that $`Q^{}𝐳=\mathrm{𝟎}`$ and $`\mathrm{𝟏}^{}\mathrm{\Delta }𝐳=1`$. Then $`(\mathrm{\Delta }𝐳)^{}\mathrm{\Delta }^1A=𝐳^{}A=(\mathrm{\Delta }𝐳)^{}`$, so $`\mathrm{\Delta }𝐳`$ is the stationary distribution of the Markov chain represented by the stochastic matrix $`\mathrm{\Delta }^1A`$. Since $`G`$ is strongly connected, every state of this Markov chain is recurrent, so every entry of $`𝐳`$ is positive. Since $`𝐳`$ solves the system $`Q^{}𝐳=\mathrm{𝟎}`$, which has integer coefficients, every entry of $`𝐳`$ is rational. Finally, there is a unique positive integer multiple of $`𝐳`$ which gives the vector $`𝐡`$ with the desired properties. ∎

For a strongly connected graph $`G`$, the vector $`𝐡`$ defined in Proposition 3.2 will be significant for several results in what follows. We refer to $`h(v)`$ as the *activity* of the vertex $`vV`$, for reasons which will be seen in Section 9.

For $`S`$ a strong component of $`G`$, if $`𝐱𝐑^V`$ then let $`𝐱|_S`$ be the restriction of $`𝐱`$ to $`V(S)`$, and if $`M`$ is a $`V`$-by-$`V`$ matrix then let $`M|_S`$ denote the submatrix of $`M`$ indexed by rows and columns from $`V(S)`$.

###### Lemma 3.3.

For any graph $`G`$, if $`𝐳\mathrm{ker}(Q^{})`$ and $`S`$ is a non-terminal strong component of $`G`$, then $`𝐳|_S=\mathrm{𝟎}`$.

###### Proof.

Let $`S_1,\mathrm{},S_c`$ be a list of the strong components of $`G`$ such that if there is a directed edge from $`vS_i`$ to $`wS_j`$, then $`ij`$. We prove the claim by induction on $`1jc`$. For the basis of induction ($`j=1`$), and for the induction step ($`j2`$), we may assume that $`𝐳|_{S_i}=\mathrm{𝟎}`$ for all $`1i<j`$ such that $`S_i`$ is a non-terminal strong component of $`G`$. If $`S_j`$ is a terminal strong component of $`G`$ then there is nothing to prove. Otherwise, there is at least one directed edge with initial vertex in $`S_j`$ and terminal vertex not in $`S_j`$. Therefore, $`Q(G)|_{S_j}=Q(S_j)+T`$ for some nonzero diagonal matrix $`T`$ of nonnegative integers. Now, since $`𝐳|_{S_i}=\mathrm{𝟎}`$ for all $`1i<j`$ such that $`S_i`$ non-terminal,

$$\mathrm{𝟎}=(Q^{}(G)𝐳)|_{S_j}=(Q^{}(S_j)+T)(𝐳|_{S_j}),$$

and by Lemma 3.1(b) we conclude that $`𝐳|_{S_j}=\mathrm{𝟎}`$. ∎

###### Theorem 3.4.

Let $`G`$ be any graph, and let the terminal strong components of $`G`$ be $`S_1,\mathrm{},S_t`$. Then

$$\mathrm{ker}(Q^{}(G))\mathrm{ker}(Q^{}(S_1))\mathrm{}\mathrm{ker}(Q^{}(S_t)).$$

###### Proof.

Let $`𝐳\mathrm{ker}(Q^{}(G))`$. By Lemma 3.3, $`𝐳|_S=\mathrm{𝟎}`$ if $`S`$ is not a terminal strong component of $`G`$. Hence, if $`S`$ is a terminal strong component of $`G`$, then

$$\mathrm{𝟎}=(Q^{}𝐳)|_S=Q^{}(S)(𝐳|_S),$$

so that $`𝐳|_S\mathrm{ker}(Q^{}(S)).`$ Conversely, if $`𝐳_i\mathrm{ker}(Q^{}(S_i))`$ for each terminal strong component of $`G`$ then the $`𝐳𝐑^V`$ defined by

$$𝐳|_S:=\{\begin{array}{cc}𝐳_i\hfill & \mathrm{if}S=S_i\mathrm{for}\mathrm{some}1it,\hfill \\ \mathrm{𝟎}\hfill & \mathrm{otherwise},\hfill \end{array}$$

is in the kernel of $`Q^{}(G)`$. ∎

###### Corollary 3.5.

For any graph $`G`$, $`\mu _0(G)`$ is the number of terminal strong components of $`G`$.

## 4. The minimal number of generators of $`K(G)`$.

Let $`\nu (G)`$ denote the minimal number of generators of the reduced critical group of $`G`$, so $`K(G)`$ is the direct sum of $`\nu (G)`$ nontrivial finite cyclic groups. This is a rather difficult numerical invariant of $`G`$, as it depends on the arithmetic properties of $`Q(G)`$. Clearly, $`\mu _1(G)+\nu (G)+\mu _0(G)=n(G)`$. We give an upper bound on $`\nu (G)`$ by proving a combinatorial lower bound on $`\mu _1(G)`$. It must be admitted, however, that this bound is generally quite weak.

Let $`G`$ be a weakly connected graph, with Laplacian matrix $`Q`$. A *reduction sequence* in $`G`$ is a sequence $`(v_1,w_1),\mathrm{},(v_s,w_s)`$ of pairs of vertices such that:
$``$ the vertices $`v_1,\mathrm{},v_s`$ are pairwise distinct,
$``$ the vertices $`w_1,\mathrm{},w_s`$ are pairwise distinct,
$``$ for each $`1is`$$`Q_{v_iw_i}\{1,1\}`$, and
$``$ for each $`2js`$, either $`Q_{v_iw_j}=0`$ for all $`1i<j`$, or $`Q_{v_jw_i}=0`$ for all $`1i<j`$.
Let $`\sigma (G)`$ denote the maximum length of a reduction sequence in $`G`$.

###### Proposition 4.1.

If $`G`$ is a weakly connected graph, then $`\mu _1(G)\sigma (G)`$, and hence $`\nu (G)n(G)\mu _0(G)\sigma (G)`$.

###### Proof.

Let $`(v_1,w_1),\mathrm{},(v_s,w_s)`$ be a reduction sequence in $`G`$, and let $`Q`$ be the Laplacian matrix of $`G`$.

The first claim is that we may apply elementary row and column operations to $`Q`$, involving only rows $`v_1,\mathrm{},v_s`$ and columns $`w_1,\mathrm{},w_s`$, so that these rows and columns of the resulting matrix induce an $`s`$-by-$`s`$ identity matrix. We prove this by induction on $`s`$, the basis $`s=1`$ being clear. For the induction step, since $`(v_1,w_1),\mathrm{},(v_{s1},w_{s1})`$ is a reduction sequence of length $`s1`$, the induction hypothesis gives elementary operations involving only rows $`v_1,\mathrm{},v_{s1}`$ and columns $`w_1,\mathrm{},w_{s1}`$, which, when applied to $`Q`$, result in a matrix $`Q^{}`$ in which these rows and columns induce an $`(s1)`$-square identity matrix. By the last condition defining a reduction sequence, we have either $`Q_{v_iw_s}=0`$ for all $`1i<s`$, or $`Q_{v_sw_i}=0`$ for all $`1i<s`$. Examining the way in which $`Q^{}`$ was obtained from $`Q`$, we see that either $`Q_{v_iw_s}^{}=0`$ for all $`1i<s`$, or $`Q_{v_sw_i}^{}=0`$ for all $`1i<s`$. Now, elementary row or column operations can be used to cancel any nonzero entries $`Q_{v_iw_s}^{}0`$ or $`Q_{v_sw_i}^{}0`$ with $`1i<s`$, and the value of $`Q_{v_sw_s}^{}`$ is left unchanged. Finally, multiplying row $`v_s`$ by $`1`$ if necessary produces the $`s`$-by-$`s`$ identity submatrix, as claimed.

Having produced this $`s`$-by-$`s`$ identity submatrix, we use elementary column operations to zero out all entries in rows $`v_1,\mathrm{},v_s`$ except for the $`1`$s in the $`(v_i,w_i)`$ positions $`(1is)`$. Then we use elementary row operations to zero out all entries in columns $`w_1,\mathrm{},w_s`$ except for the $`1`$s in the $`(v_i,w_i)`$ positions $`(1is)`$. The result is a matrix, equivalent to $`Q`$, which is also equivalent to a matrix with the block structure $`I_sM`$ for some $`(ns)`$-square matrix $`M`$. Therefore, $`1`$ occurs at least $`s`$ times in the Smith normal form of $`Q`$. Considering a reduction sequence of maximum length $`s=\sigma (G)`$ completes the proof. ∎

The bound of Proposition 4.1 is likely to be very far from the true value of $`\nu (G)`$, since it makes no use of the arithmetic structure of $`Q(G)`$. With this in mind, here are a few conjectures. Let $`𝒢(n,p)`$ denote a random simple, undirected graph with $`n`$ vertices and edge-probability $`0p1`$. As is is well-known (see Theorem 4.3.1 of Palmer ), if $`p(n)>c\mathrm{log}(n)/n`$ with $`c>1`$ then, as $`n\mathrm{}`$, the probability that $`𝒢(n,p)`$ is connected converges to $`1`$.

###### Conjecture 4.2.

If $`c>1`$ and $`c\mathrm{log}(n)/n<p(n)<1o(\mathrm{log}(n)/n)`$ then, as $`n\mathrm{}`$, the probability that $`K(𝒢(n,p))`$ is cyclic converges to $`1`$.

That is, the conjecture is that almost every connected undirected simple graph has a cyclic reduced critical group. (The edge-probability must be bounded away from $`1`$ to avoid complete graphs and complete multipartite graphs, but I don’t really know what the ‘right’ bound should be.) There is some experimental evidence for this, but it is not extensive. The following weak form is probably more accessible.

###### Conjecture 4.3.

If $`c>1`$ and $`c\mathrm{log}(n)/n<p(n)<1o(\mathrm{log}(n)/n)`$ then, as $`n\mathrm{}`$, the expected value of $`\nu (𝒢(n,p))`$ remains bounded.

By considering Smith normal forms and using Proposition 2.3, it is easy to see that for a connected undirected graph $`G`$, if $`\kappa (G)`$ is square-free then $`K(G)`$ is cyclic (or trivial). Since the density of square-free natural numbers is asymptotically $`6/\pi ^2`$, this motivates the third conjecture.

###### Conjecture 4.4.

If $`c>1`$ and $`c\mathrm{log}(n)/n<p(n)<1o(\mathrm{log}(n)/n)`$ then, as $`n\mathrm{}`$, the probability that $`\kappa (𝒢(n,p))`$ is square-free is $`(1o(1))6/\pi ^2`$.

## 5. Equitable partitions of graphs.

See Chapter 5 of Godsil  for further development and application of the theory of equitable partitions of undirected graphs.

Consider a graph $`G`$, and let $`\pi =(\pi _1,\mathrm{},\pi _p)`$ be an ordered partition of $`V`$ into pairwise disjoint nonempty blocks. The partition $`\pi `$ is *equitable* for $`G`$ provided that there exist nonnegative integers $`F_{ij}`$ and $`R_{ij}`$ for all $`1i,jp`$ such that every vertex in $`\pi _i`$ is the initial vertex of exactly $`F_{ij}`$ directed edges of $`G`$ which have their terminal vertices in $`\pi _j`$, and every vertex in $`\pi _j`$ is the terminal vertex of exactly $`R_{ij}`$ directed edges of $`G`$ which have their initial vertices in $`\pi _i`$. (The letters $`F`$ and $`R`$ are mnemonic for ‘forward’ and ‘reverse’, respectively.) These integers define $`p\times p`$ matrices $`F`$ and $`R`$, and we regard $`F`$ as the adjacency matrix of a graph $`G/\pi `$ on the vertex-set $`\{1,\mathrm{},p\}`$, called the *quotient of $`G`$ by $`\pi `$*. It will be convenient to use the notations $`A`$, $`\mathrm{\Delta }`$ and $`Q`$ for $`A(G)`$, $`\mathrm{\Delta }(G)`$, and $`Q(G)`$, and to use $`F`$, $`D`$ and $`\widehat{Q}`$ for $`A(G/\pi )`$, $`\mathrm{\Delta }(G/\pi )`$, and $`Q(G/\pi )`$.

For $`\pi `$ an equitable partition of $`G`$, let $`P`$ be the matrix indexed by $`V\times \{1,\mathrm{},p\}`$, with entries

$$P_{vi}:=\{\begin{array}{cc}1\hfill & \mathrm{if}v\pi _i,\hfill \\ 0\hfill & \mathrm{if}v\pi _i.\hfill \end{array}$$

Then $`B:=P^{}P`$ is the invertible $`p\times p`$ diagonal matrix with entries $`B_{ii}=\mathrm{\#}\pi _i`$ for each $`1ip`$. For each $`1i,jp`$, by counting in two ways the directed edges of $`G`$ with initial vertex in $`\pi _i`$ and terminal vertex in $`\pi _j`$ we see that $`B_{ii}F_{ij}=R_{ij}B_{jj},`$ yielding the matrix equations $`BF=RB`$ and $`B^1R=FB^1`$. For any vertex $`v\pi _i`$ we have

$$\mathrm{\Delta }_{vv}=\underset{wV}{}A_{vw}=\underset{j=1}{\overset{p}{}}F_{ij}=D_{ii},$$

or, in matrix form, $`\mathrm{\Delta }=PDB^1P^{}`$. Therefore, $`\mathrm{\Delta }P=PD`$. Also, for $`v\pi _i`$, and any $`1jp`$,

$$(AP)_{vj}=\underset{w\pi _j}{}A_{vw}=F_{ij}=(PF)_{vj},$$

so that $`AP=PF`$. It follows that $`QP=P\widehat{Q}`$. Finally, consider any $`1ip`$ and $`v\pi _j`$. Then

$$(B^1P^{}A)_{iv}=B_{ii}^1\underset{w\pi _i}{}A_{wv}=B_{ii}^1R_{ij}=F_{ij}B_{jj}^1=(FB^1P^{})_{iv},$$

so that $`B^1P^{}A=FB^1P^{}`$. Also, since

$$B^1P^{}\mathrm{\Delta }=B^1P^{}PDB^1P^{}=DB^1P^{},$$

we conclude that $`B^1P^{}Q=\widehat{Q}B^1P^{}`$.

## 6. Critical groups of graph quotients.

We continue with the notation of the previous section. The matrix $`P`$ defines a group homomorphism $`P:𝐙^p𝐙^V`$, and $`P\widehat{Q}𝐙^p=QP𝐙^VQ𝐙^V`$. Therefore, $`P`$ induces a homomorphism

$$\rho :𝒦^{}(G/\pi )𝒦^{}(G)$$

between the dual critical groups, which is well-defined by $`\rho (𝐱+\widehat{Q}𝐙^p):=P𝐱+Q𝐙^V.`$

Theorem 6.1 was inspired by Theorem 10.2 of Biggs .

###### Theorem 6.1.

Let $`G`$ be a strongly connected graph, and let $`\pi `$ be an equitable partition of $`G`$. Then the natural homomorphism $`\rho :𝒦^{}(G/\pi )𝒦^{}(G)`$ is injective.

###### Proof.

To show that $`\rho :𝒦^{}(G/\pi )𝒦^{}(G)`$ is injective, we must show that if $`𝐱𝐙^p`$ is such that $`P𝐱Q𝐙^V`$, then $`𝐱\widehat{Q}𝐙^p`$. Accordingly, assume that $`𝐱𝐙^p`$ and $`𝐯𝐙^V`$ satisfy $`P𝐱=Q𝐯`$. Let $`𝐲:=B^1P^{}𝐯`$. Then

$$𝐱=B^1P^{}P𝐱=B^1P^{}Q𝐯=\widehat{Q}B^1P^{}𝐯=\widehat{Q}𝐲.$$

The entries of $`𝐲`$ are rational numbers, but we need to find $`𝐮𝐙^p`$ such that $`𝐱=\widehat{Q}𝐮`$. To do this, notice that

$$Q𝐯=P𝐱=P\widehat{Q}𝐲=QP𝐲,$$

so that $`Q(𝐯P𝐲)=\mathrm{𝟎}`$. Since $`G`$ is strongly connected, the kernel of $`Q`$ is $`𝐑\mathrm{𝟏}`$, and this implies that $`𝐯P𝐲=c\mathrm{𝟏}`$ for some $`c𝐑`$. Now $`𝐯=P𝐲+c\mathrm{𝟏}=P(𝐲+c\mathrm{𝟏})`$, and since every entry of $`𝐯`$ is an integer, every entry of $`𝐮:=𝐲+c\mathrm{𝟏}`$ is an integer. Finally, since $`\widehat{Q}\mathrm{𝟏}=\mathrm{𝟎}`$ it follows that $`𝐱=\widehat{Q}𝐲=\widehat{Q}𝐮`$, which shows that $`𝐱\widehat{Q}𝐙^p`$ and completes the proof. ∎

Of course, under the hypotheses of Theorem 6.1, the natural homomorphism

$$\rho :K^{}(G/\pi )K^{}(G)$$

is also injective.

###### Example 6.2.

*The hypothesis that $`G`$ is strongly connected can not be dropped from Theorem 6.1, as the following example shows. Let*

$$Q=\left[\begin{array}{ccc}\hfill 2& \hfill 1& \hfill 1\\ \hfill 0& \hfill 0& \hfill 0\\ \hfill 0& \hfill 0& \hfill 0\end{array}\right]\mathrm{and}\widehat{Q}=\left[\begin{array}{cc}\hfill 2& \hfill 2\\ \hfill 0& \hfill 0\end{array}\right].$$

*Then $`Q`$ is the Laplacian matrix of a weakly connected graph $`G`$ with vertex-set $`\{1,2,3\}`$ and $`\widehat{Q}`$ is the Laplacian of the quotient of $`G`$ by the equitable partition $`\pi =\{\{1\},\{2,3\}\}`$ of $`G`$. However, by computing the Smith normal forms of $`Q`$ and $`\widehat{Q}`$ one sees that*

$$𝒦^{}(G)𝐙𝐙\mathrm{and}𝒦^{}(G/\pi )(𝐙/2𝐙)𝐙.$$

*Hence, the homomorphism $`\rho :𝒦^{}(G/\pi )𝒦^{}(G)`$ is not injective in this case.*

###### Example 6.3.

*With the hypotheses of Theorem 6.1, $`K^{}(G/\pi )`$ is regarded as a subgroup of $`K^{}(G)`$ *via* the natural inclusion $`\rho `$. However, $`K^{}(G/\pi )`$ might not be a direct summand of $`K^{}(G)`$, as the following example shows. The nine-cycle $`C_9`$ has an equitable partition $`\pi `$ for which the quotient graph $`C_9/\pi `$ is the three-cycle $`C_3`$, but $`K^{}(C_3)𝐙/3𝐙`$ is not a direct summand of $`K^{}(C_9)𝐙/9𝐙`$.*

## 7. Matroid invariance of $`K(G)`$.

Let $`G`$ be a strongly connected graph, and let $`𝐡`$ be the vector of vertex activities defined in Proposition 3.2. If vertex $`vV`$ is such that $`h(v)=1`$ then we say that $`v`$ is a *simple* vertex of $`G`$.

###### Lemma 7.1.

Let $`G`$ be a strongly connected graph, and let $`v,wV(G)`$. If $`w`$ is simple then the Laplacian matrix $`Q(G)`$ is equivalent to the matrix $`Q^{}`$ obtained from $`Q`$ by replacing every entry in either column $`v`$ or row $`w`$ by zero.

###### Proof.

Let $`𝐡`$ be the vector of vertex activities of $`G`$. Use elementary column operations to add column $`u`$ to column $`v`$ for all $`vuV`$. Then use elementary row operations to add $`h(u)`$ times row $`u`$ to row $`w`$ for all $`wuV`$. The resulting matrix $`Q^{}`$ is equivalent to $`Q`$ and has the required form, since $`Q^{}𝐡=Q\mathrm{𝟏}=\mathrm{𝟎}`$. ∎

###### Proposition 7.2.

Let $`G`$ and $`H`$ be vertex-disjoint strongly connected graphs, and let $`vV(G)`$ and $`wV(H)`$. Denote by $`(GH)/vw`$ the graph obtained from $`GH`$ by identifying $`v`$ and $`w`$. If $`w`$ is a simple vertex of $`H`$ then

$$𝒦(GH)𝒦((GH)/vw)𝐙$$

and

$$K(GH)K((GH)/vw).$$

###### Proof.

Let $`M`$ be the submatrix of $`Q(G)`$ obtained by deleting the row and column indexed by $`v`$; so we have

$$Q(G)=\left[\begin{array}{cc}M\hfill & \overline{𝐯}\hfill \\ 𝐯\hfill & \mathrm{\Delta }(G)_{vv}\hfill \end{array}\right]$$

for some row vector $`𝐯`$ and column vector $`\overline{𝐯}`$. Since $`Q(G)\mathrm{𝟏}=\mathrm{𝟎}`$, we have

$$Q(G)Q^{}(G):=\left[\begin{array}{cc}M\hfill & \mathrm{𝟎}\hfill \\ 𝐯\hfill & 0\hfill \end{array}\right].$$

Similarly, let $`N`$ be the submatrix of $`Q(H)`$ obtained by deleting the row and column indexed by $`w`$; so we have

$$Q(H)=\left[\begin{array}{cc}\mathrm{\Delta }(H)_{ww}\hfill & 𝐰\hfill \\ \overline{𝐰}\hfill & N\hfill \end{array}\right]$$

for some row vector $`𝐰`$ and column vector $`\overline{𝐰}`$. Since $`w`$ is a simple vertex of $`H`$, Lemma 7.1 implies that $`Q(H)[0]N`$.

Now, since $`Q(GH)=Q(G)Q(H)`$ we see that $`Q(GH)Q^{}(G)[0]N`$. Also, since $`w`$ is a simple vertex of $`H`$ we see that

$$Q((GH)/vw)=\left[\begin{array}{ccc}M\hfill & \overline{𝐯}\hfill & O\hfill \\ 𝐯\hfill & d\hfill & 𝐰\hfill \\ O\hfill & \overline{𝐰}\hfill & N\hfill \end{array}\right]\left[\begin{array}{ccc}M\hfill & \mathrm{𝟎}\hfill & O\hfill \\ 𝐯\hfill & 0\hfill & \mathrm{𝟎}\hfill \\ O\hfill & \mathrm{𝟎}\hfill & N\hfill \end{array}\right]=Q^{}(G)N$$

(here, $`d:=\mathrm{\Delta }(G)_{vv}+\mathrm{\Delta }(H)_{ww}`$). Since $`Q(GH)Q((GH)/vw)[0]`$ we have $`\mathrm{snf}(GH)=\mathrm{snf}((GH)/vw)[0]`$, from which the result follows. ∎

Let $`G`$ and $`H`$ be vertex-disjoint weakly connected directed graphs, let $`v_1v_2`$ be distinct vertices of $`G`$, and let $`w_1w_2`$ be distinct vertices of $`H`$. The graph $`GH:=(GH)/\{v_1w_1,v_2w_2\}`$ is obtained from $`GH`$ by identifying $`v_1`$ and $`w_1`$, and identifying $`v_2`$ and $`w_2`$. The graph $`GH:=(GH)/\{v_1w_2,v_2w_1\}`$ is obtained from $`GH`$ by identifying $`v_1`$ and $`w_2`$, and identifying $`v_2`$ and $`w_1`$. We say that $`GH`$ and $`GH`$ are related by *twisting a two-vertex cut*.

###### Proposition 7.3.

Let $`G`$ and $`H`$ be vertex-disjoint strongly connected graphs, and use the notation of the above paragraph. If both $`w_1`$ and $`w_2`$ are simple vertices of $`H`$ then

$$𝒦(GH)𝒦(GH).$$

###### Proof.

For $`i=1,2`$, let $`𝐯_i`$ be the row vector with entries $`Q(G)_{v_iz}`$ for each $`zV(G)\{v_1,v_2\}`$, and let $`\overline{𝐯}_i`$ be the column vector with entries $`Q(G)_{zv_i}`$ for each $`zV(G)\{v_1,v_2\}`$. For $`i=1,2`$, let $`𝐰_i`$ be the row vector with entries $`Q(H)_{w_iz}`$ for each $`zV(H)\{w_1,w_2\}`$, and let $`\overline{𝐰}_i`$ be the column vector with entries $`Q(H)_{zw_i}`$ for each $`zV(H)\{w_1,w_2\}`$. Then the matrices $`Q(GH)`$ and $`Q(GH)`$ have the block forms as shown:

$$\left[\begin{array}{cccc}M\hfill & \overline{𝐯}_1\hfill & \overline{𝐯}_2\hfill & O\hfill \\ 𝐯_1\hfill & a_{11}\hfill & a_{12}\hfill & 𝐰_1\hfill \\ 𝐯_2\hfill & a_{21}\hfill & a_{22}\hfill & 𝐰_2\hfill \\ O\hfill & \overline{𝐰}_1\hfill & \overline{𝐰}_2\hfill & N\hfill \end{array}\right]\mathrm{and}\left[\begin{array}{cccc}M\hfill & \overline{𝐯}_1\hfill & \overline{𝐯}_2\hfill & O\hfill \\ 𝐯_1\hfill & b_{11}\hfill & b_{12}\hfill & 𝐰_2\hfill \\ 𝐯_2\hfill & b_{21}\hfill & b_{22}\hfill & 𝐰_1\hfill \\ O\hfill & \overline{𝐰}_2\hfill & \overline{𝐰}_1\hfill & N\hfill \end{array}\right]$$

$$Q(GH)Q(GH)$$

Here, $`M`$ is the submatrix of $`Q(G)`$ induced by rows and columns in $`V(G)\{v_1,v_2\}`$, $`N`$ is the submatrix of $`Q(H)`$ induced by rows and columns in $`V(H)\{w_1,w_2\}`$, and

$$a_{ij}:=Q(G)_{v_iv_j}+Q(H)_{w_iw_j}\mathrm{and}b_{ij}:=Q(G)_{v_iv_j}+Q(H)_{w_{3i},w_{3j}}$$

for $`1i2`$.

Since both $`w_1`$ and $`w_2`$ are simple vertices of $`H`$, an argument analogous to the proof of Lemma 7.1 shows that $`Q(GH)`$ and $`Q(GH)`$ are equivalent to

$$\left[\begin{array}{cccc}M\hfill & \overline{𝐯}_1\hfill & \mathrm{𝟎}\hfill & O\hfill \\ 𝐯_1\hfill & a_{11}\hfill & 0\hfill & 𝐰_1\hfill \\ 𝐯_1+𝐯_2\hfill & c_{21}\hfill & 0\hfill & \mathrm{𝟎}\hfill \\ O\hfill & \overline{𝐰}_1\hfill & \mathrm{𝟎}\hfill & N\hfill \end{array}\right]\mathrm{and}\left[\begin{array}{cccc}M\hfill & \overline{𝐯}_1\hfill & \mathrm{𝟎}\hfill & O\hfill \\ 𝐯_1\hfill & b_{11}\hfill & 0\hfill & 𝐰_2\hfill \\ 𝐯_1+𝐯_2\hfill & c_{21}\hfill & 0\hfill & \mathrm{𝟎}\hfill \\ O\hfill & \overline{𝐰}_2\hfill & \mathrm{𝟎}\hfill & N\hfill \end{array}\right]$$

$$Q^{}(GH)Q^{}(GH)$$

respectively, in which $`c_{21}=Q(G)_{v_1v_1}+Q(G)_{v_2v_1}`$.

Let $`𝐡`$ denote the vector of activities of $`H`$, so that $`𝐡^{}Q(H)=\mathrm{𝟎}`$. Then the sum over all $`zV(H)\{w_1,w_2\}`$ of $`h(z)`$ times the $`z`$-th row of $`N`$ is equal to $`𝐰_1𝐰_2`$, since both $`w_1`$ and $`w_2`$ are simple in $`H`$. Since the columns of $`Q(H)`$ sum to $`\mathrm{𝟎}`$, the columns of $`N`$ sum to $`\overline{𝐰}_1\overline{𝐰}_2`$. Now, for $`zV(H)\{w_1,w_2\}`$, add $`h(z)`$ times row $`z`$ of $`Q^{}(GH)`$ to the row indexed by $`v_1w_2`$. Then, for $`zV(H)\{w_1,w_2\}`$, add column $`z`$ of the resulting matrix to the column indexed by $`v_1w_2`$. The result is the matrix

$$Q^{\prime \prime }(GH)=\left[\begin{array}{cccc}\hfill M& \hfill \overline{𝐯}_1& \hfill \mathrm{𝟎}& \hfill O\\ \hfill 𝐯_1& \hfill c_{11}& \hfill 0& \hfill 𝐰_1\\ \hfill 𝐯_1+𝐯_2& \hfill c_{21}& \hfill 0& \hfill \mathrm{𝟎}\\ \hfill O& \hfill \overline{𝐰}_1& \hfill \mathrm{𝟎}& \hfill N\end{array}\right]$$

in which

$`c_{11}`$ $`=`$ $`b_{11}+{\displaystyle \underset{zV(H)\{w_1,w_2\}}{}}h(z)\overline{w}_2(z){\displaystyle \underset{zV(H)\{w_1,w_2\}}{}}w_1(z)`$
$`=`$ $`b_{11}Q(H)_{w_2w_2}Q(H)_{w_2w_1}+Q(H)_{w_1w_1}+Q(H)_{w_2w_1}`$
$`=`$ $`b_{11}\mathrm{\Delta }(H)_{w_2w_2}+\mathrm{\Delta }(H)_{w_1w_1}`$
$`=`$ $`\mathrm{\Delta }(G)_{v_1v_1}+\mathrm{\Delta }(H)_{w_2w_2}\mathrm{\Delta }(H)_{w_2w_2}+\mathrm{\Delta }(H)_{w_1w_1}`$
$`=`$ $`a_{11}`$
Finally, by multiplying the last $`n(H)2`$ rows and columns of $`Q^{\prime \prime }(GH)`$ by $`1`$, we obtain the matrix $`Q^{}(GH)`$. This shows that $`Q(GH)`$ and $`Q(GH)`$ are equivalent, so that $`\mathrm{snf}(Q(GH))=\mathrm{snf}(Q(GH))`$ and $`𝒦(GH)𝒦(GH)`$. ∎

###### Example 7.4.

*The hypothesis in Proposition 7.3 that $`w_1`$ and $`w_2`$ are simple vertices of $`H`$ can not be removed, as the following example shows. Let $`G`$ and $`H`$ both have Laplacian matrix*

$$Q(G)=Q(H)=\left[\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 2& \hfill 2\end{array}\right],$$

*and note that the vertex activities are $`2`$ and $`1`$ in each graph. Then*

$$Q(GH)=\left[\begin{array}{cc}\hfill 2& \hfill 2\\ \hfill 4& \hfill 4\end{array}\right]\mathrm{and}Q(GH)=\left[\begin{array}{cc}\hfill 3& \hfill 3\\ \hfill 3& \hfill 3\end{array}\right],$$

*and by calculating Smith normal forms we see that*

$$𝒦(GH)(𝐙/2𝐙)𝐙\mathrm{and}𝒦(GH)(𝐙/3𝐙)𝐙.$$

A strongly connected directed graph $`G`$ is *balanced* if, for each vertex $`vV(G)`$, the indegree of $`v`$ equals the outdegree of $`v`$. Undirected graphs are thus a special case of balanced graphs. Equivalently, $`G`$ is balanced if and only if $`Q^{}\mathrm{𝟏}=\mathrm{𝟎}`$, *i.e.* every vertex of $`G`$ is simple.

###### Corollary 7.5.

Let $`G`$ and $`H`$ be vertex-disjoint balanced graphs, and let $`vV(G)`$ and $`wV(H)`$. Then

$$𝒦(GH)𝒦((GH)/vw)𝐙$$

and

$$K(GH)K((GH)/vw).$$

###### Corollary 7.6.

Let $`G`$ and $`H`$ be vertex-disjoint balanced graphs, let $`v_1v_2`$ in $`V(G)`$, and let $`w_1w_2`$ in $`V(H)`$. With the notation introduced above,

$$𝒦(GH)𝒦(GH).$$

Whitney  characterized those pairs of undirected graphs $`G,H`$ which have isomorphic graphic matroids as being exactly those pairs for which $`G`$ may be transformed into $`H`$ by some sequence of splittings or mergings of one-vertex cuts and twistings of two-vertex cuts. Corollary 7.7 follows immediately.

###### Corollary 7.7.

Let $`G`$ and $`H`$ be undirected graphs. If the graphic matroids of $`G`$ and $`H`$ are isomorphic, then $`K(G)K(H)`$.

###### Example 7.8.

*The converse of Corollary 7.7 does not hold. In fact, for undirected graphs, the Tutte polynomial $`T(G;x,y)`$ is not computable from the critical group $`𝒦(G)`$, as the following example shows. Let $`v`$ be a vertex of $`C_3`$ and let $`w`$ be a vertex of $`C_4`$, where the cycles are vertex-disjoint. Then*

$`𝒦((C_3C_4)/vw)`$ $``$ $`(𝐙/3𝐙)(𝐙/4𝐙)𝐙`$
$``$ $`(𝐙/12𝐙)𝐙𝒦(C_{12}).`$
*However,*

$$T((C_3C_4)/vw;x,y)=(y+x+x^2)(y+x+x^2+x^3)$$

*and*

$$T(C_{12};x,y)=y+x+x^2+\mathrm{}+x^{11}.$$

Finally, I conjecture that the critical group is not computable from the Tutte polynomial, either.

###### Conjecture 7.9.

There exist connected undirected graphs $`G`$ and $`H`$ such that $`T(G;x,y)=T(H;x,y)`$ and $`𝒦(G)\simeq ̸𝒦(H)`$.

## 8. Inequivalence of $`𝒯(G)`$ and $`K(G)`$.

For this section we consider only connected undirected graphs. By Proposition 2.3, in this case the reduced critical group $`K(G)`$ is a finite abelian group of order $`\kappa (G)`$, the cardinality of the set $`𝒯(G)`$ of spanning trees of $`G`$. It is thus reasonable to consider the problem of constructing a bijection from $`𝒯(G)`$ to $`K(G)`$ in a ‘natural’ way. We will show that, in general, this is not possible. To allow more flexibility in the construction, we consider the complex vector spaces $`𝐂𝒯(G)`$ and $`𝐂K(G)`$, and ask for an isomorphism of vector spaces $`\psi _G:𝐂𝒯(G)𝐂K(G)`$ which is constructed naturally from $`G`$. The naturality condition means that $`\psi _G`$ should depend only on the isomorphism class of $`G`$, but we must first state this more precisely.

For any graph isomorphism $`f:GH`$, there is an induced bijection $`f_𝒯:𝒯(G)𝒯(H)`$ defined by sending each spanning tree of $`G`$ to its image under $`f`$. This extends linearly to an isomorphism from $`𝐂𝒯(G)`$ to $`𝐂𝒯(H)`$ which we also denote by $`f_𝒯`$. Let $`\mathrm{\Phi }`$ be the matrix indexed by $`V(H)\times V(G)`$, with

$$\mathrm{\Phi }_{vw}:=\{\begin{array}{cc}1\hfill & \mathrm{if}f(w)=v,\hfill \\ 0\hfill & \mathrm{if}f(w)v.\hfill \end{array}$$

Then $`\mathrm{\Phi }:𝐙^{V(G)}𝐙^{V(H)}`$ is an isomorphism, and $`\mathrm{\Phi }Q^{}(G)=Q^{}(H)\mathrm{\Phi }`$. It follows that $`\mathrm{\Phi }Q^{}(G)𝐙^{V(G)}=Q^{}(H)𝐙^{V(H)}`$, and so $`f`$ induces a group isomorphism

$$f_𝒦:𝒦(G)\stackrel{}{}𝒦(H)$$

well-defined by $`f_𝒦(𝐱+Q^{}(G)𝐙^{V(G)}):=\mathrm{\Phi }𝐱+Q^{}(H)𝐙^{V(H)}.`$ For reduced critical groups, we also have a group isomorphism

$$f_K:K(G)\stackrel{}{}K(H)$$

induced by $`f`$, and we extend this linearly to obtain an isomorphism from $`𝐂K(G)`$ to $`𝐂K(H)`$, also denoted by $`f_K`$.

The naturality condition on $`\psi _G`$ is that, for any multigraph isomorphism $`f:GH`$, the diagram

$$\begin{array}{ccc}𝐂𝒯(G)\hfill & \stackrel{\psi _G}{}& \hfill 𝐂K(G)\\ f_𝒯\hfill & & \hfill f_K\\ 𝐂𝒯(H)\hfill & \stackrel{\psi _H}{}& \hfill 𝐂K(H)\end{array}$$

is commutative; that is to say, $`\psi _Hf_𝒯=f_K\psi _G`$. This means that $`\psi _H`$ is ‘the same as’ $`\psi _G`$, after relabelling the vertices according to $`f`$.

###### Theorem 8.1.

There exist connected undirected graphs $`G`$ for which there is no natural isomorphism $`\psi _G:𝐂𝒯(G)𝐂K(G)`$.

###### Proof.

In particular, the naturality condition must hold when $`G=H`$ and $`f`$ is in the automorphism group $`\mathrm{Aut}(G)`$ of $`G`$. In this situation, the assignment $`ff_𝒯`$ gives a representation of $`\mathrm{Aut}(G)`$ acting on $`𝐂𝒯(G)`$ and the assignment $`ff_K`$ gives a representation of $`\mathrm{Aut}(G)`$ acting on $`𝐂K(G)`$. (All the representation theory we need is in Chapter 1 of Ledermann .) Commutativity of the diagram means that $`\psi _G`$ is an $`\mathrm{Aut}(G)`$-equivariant isomorphism, so these two representations are linearly equivalent. A representation of a finite group is determined up to linear equivalence by its group character, so $`\psi _G`$ exists if and only if the characters $`\chi _𝒯`$ and $`\chi _K`$ of these two representations are equal. Since these are permutation representations, their characters are given by counting fixed points; that is, for each $`f\mathrm{Aut}(G)`$,

$$\chi _𝒯(f)=\mathrm{\#}\{T𝒯(G):f_𝒯(T)=T\}$$

and

$$\chi _K(f)=\mathrm{\#}\{𝐱K(G):f_K(𝐱)=𝐱\},$$

respectively.

Thus, to show that a natural construction of $`\psi _G`$ is impossible, it suffices to find a connected undirected graph $`G`$ and automorphism $`f\mathrm{Aut}(G)`$ such that $`\chi _𝒯(f)\chi _K(f)`$. This is easy: let $`G`$ be a circulant graph with at least three vertices, and let $`f\mathrm{Aut}(G)`$ be a cyclic permutation of all of $`V(G)`$. Every spanning tree of $`G`$ has both leaves and non-leaf vertices, and so it can not be left fixed by $`f`$. Thus, $`\chi _𝒯(f)=0`$. On the other hand, the $`\mathrm{𝟎}`$ element of $`K(G)`$ is such that $`f_K(\mathrm{𝟎})=\mathrm{𝟎}`$, since $`f_K`$ is a group automorphism. Thus, $`\chi _K(f)1`$, and since $`\chi _𝒯\chi _K`$ it follows that $`\psi _G`$ does not exist. ∎

I have not thought much about the following problem, but the question seems interesting.

###### Problem 8.2.

*With notation as in the proof of Theorem 8.1, does there exist a vertex-transitive connected undirected graph $`G`$, with at least three vertices, such that the characters $`\chi _𝒯`$ and $`\chi _K`$ of $`\mathrm{Aut}(G)`$ are equal?*

Note, in particular, that for such a graph every automorphism fixes at least one spanning tree; together with vertex-transitivity, this seems to be quite restrictive.

In contrast with Theorem 8.1, a negative result, if one fixes a total order $``$ on the edge-set of $`G`$ then the automorphism group of the pair $`(G,)`$ is trivial (as long as $`G`$ has at least three vertices), so the naturality condition for these structures becomes vacuous and the possibility arises of constructing a bijection from $`𝒯(G)`$ to $`K(G)`$ relative to $``$. Jonathan Dumas (personal communication, August 2000) has recently found such a construction which, moreover, behaves well regarding the external activities of spanning trees with respect to $``$.

## 9. The dollar game for strongly connected graphs.

For undirected graphs, a combinatorial understanding of the critical group has been developed by Biggs . We generalize this to the case of strongly connected graphs; the theory is essentially the same as in the undirected case, with one interesting extra complication.

Let $`G=(V,E)`$ be a strongly connected graph with no loops, and let $`\$`$ denote a designated vertex of $`G`$, which we call the *bank*. A *configuration* is an integer vector $`𝐜𝐙^V`$ such that $`\mathrm{𝟏}^{}𝐜=0`$, so that $`c(\$)=_{v\$}c(v)`$. We say that a configuration $`𝐜`$ is *nonnegative* when $`c(v)0`$ for all $`\$vV`$. A vertex $`v\$`$ is *legal* for $`𝐜`$ when $`c(v)\mathrm{\Delta }_{vv}`$, the outdegree of $`v`$. The configuration $`𝐜`$ is *stable* when $`c(v)<\mathrm{\Delta }_{vv}`$ for all $`v\$`$; in this case, and in this case only, the bank vertex $`\$`$ is *legal* for $`𝐜`$. For a configuration $`𝐜`$ and vertex $`v`$, the effect of *firing $`v`$ from* $`𝐜`$ is the configuration $`𝐜|v:=𝐜Q^{}\widehat{v}`$, in which $`\widehat{v}𝐙^V`$ denotes the characteristic vector of the vertex $`vV`$. More explicitly, for each $`wV`$, $`(c|v)(w)`$ is defined by

$$(c|v)(w)=\{\begin{array}{cc}c(v)\mathrm{\Delta }_{vv}\hfill & \mathrm{if}w=v,\hfill \\ c(w)+A_{vw}\hfill & \mathrm{if}wv.\hfill \end{array}$$

If one considers a nonnegative configuration $`𝐜`$ as representing $`c(v)`$ dollars at each vertex $`v\$`$, then the effect of firing a legal vertex $`v`$ is to send one dollar along each edge with initial vertex $`v`$. More generally, if $`v_1\mathrm{}v_k`$ is a sequence of vertices in which $`vV`$ occurs $`m(v)`$ times, then the effect of firing this sequence of vertices from the configuration $`𝐜`$ is $`𝐜|v_1\mathrm{}v_k=𝐜Q^{}𝐦`$, in which $`𝐦=\widehat{v}_1+\mathrm{}+\widehat{v}_k`$ is the vector of multiplicities. The sequence $`v_1\mathrm{}v_k`$ is *legal for* $`𝐜`$ provided that $`v_i`$ is legal for $`𝐜|v_1\mathrm{}v_{i1}`$ for each $`1ik`$. For a configuration $`𝐜`$, let $`𝒮(𝐜)`$ denote the set of all configurations $`𝐛`$ such that $`𝐛=𝐜|v_1\mathrm{}v_k`$ for some sequence $`v_1\mathrm{}v_k`$ of vertices which is legal for $`𝐜`$ and does not contain the bank vertex $`\$`$.

###### Proposition 9.1.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$. For every configuration $`𝐜`$ on $`(G,\$)`$, the set $`𝒮(𝐜)`$ is finite. If $`𝐜`$ is nonnegative then every configuration in $`𝒮(𝐜)`$ is also nonnegative.

###### Proof.

If $`𝐜`$ is nonnegative and $`v`$ is legal for $`𝐜`$, then $`𝐜|v`$ is nonnegative. From this it follows that if $`𝐜`$ is nonnegative then every configuration in $`𝒮(𝐜)`$ is nonnegative. More generally, for any configuration $`𝐜`$, define the configuration $`𝐜^{}`$ by

$$c^{}(v):=\{\begin{array}{cc}c(v)\hfill & \mathrm{if}v\$\mathrm{and}c(v)<0,\hfill \\ 0\hfill & \mathrm{if}v\$\mathrm{and}c(v)0,\hfill \end{array}$$

and $`c^{}(\$):=_{v\$}c^{}(v)`$. If $`v_1\mathrm{}v_k`$ is a legal sequence for $`𝐜`$ which does not contain $`\$`$, then it is a legal sequence for $`𝐜𝐜^{}`$. Since $`𝐜𝐜^{}`$ is nonnegative, it follows that $`𝐜|v_1\mathrm{}v_k𝐜^{}`$ is nonnegative. That is, $`𝐛𝐜^{}`$ is nonnegative for all $`𝐛S(𝐜)`$.

For each $`vV`$, let $`d(v)`$ denote the length of a shortest directed path from $`v`$ to $`\$`$ in $`G`$, and let $`r:=\mathrm{max}\{d(v):vV\}`$. For each configuration $`𝐜`$, define the ‘label’ of $`𝐜`$ to be $`\mathrm{}(𝐜):=(\mathrm{}_1,\mathrm{},\mathrm{}_r)`$, in which $`\mathrm{}_i:=\{c(v):vV\mathrm{and}d(v)=i\}`$. Define a total order $``$ on $`𝐙^r`$ as follows: $`(p_1,\mathrm{},p_r)(q_1,\mathrm{},q_r)`$ if and only if either $`p_1+\mathrm{}+p_r<q_1+\mathrm{}+q_r`$, or $`p_1+\mathrm{}+p_r=q_1+\mathrm{}+q_r`$ and $`p_1=q_1`$, $`p_2=q_2`$,…$`p_{i1}=q_{i1}`$, $`p_i>q_i`$ for some $`1ir`$. Notice that $`(𝐙^r,)`$ has the same order type as $`(𝐙,<)`$. Also notice that if $`v\$`$ and $`v`$ is legal for $`𝐜`$, then

$$\mathrm{}(𝐜^{})\mathrm{}((𝐜|v)^{})\mathrm{}(𝐜|v)\mathrm{}(𝐜).$$

It follows that, for any configuration $`𝐜`$, the set $`\{\mathrm{}(𝐛):𝐛𝒮(𝐜)\}`$ is finite. But for any $`𝐪𝐙^r`$, the set of configurations $`\{𝐛:\mathrm{}(𝐛)=𝐪\}`$ is also finite. These two observations suffice to show that $`𝒮(𝐜)`$ is finite. ∎

###### Lemma 9.2.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$. Let $`𝐜`$ be a configuration on $`(G,\$)`$, let $`v,wV`$, and let $`𝐜|w:=𝐜Q^{}\widehat{w}`$. If $`vw`$ then $`(c|w)(v)c(v)`$. In particular, if $`v\{w,\$\}`$ and $`v`$ is legal for $`𝐜`$, then $`v`$ is legal for $`𝐜|w`$.

###### Proof.

This follows immediately from the facts that the off-diagonal elements of $`Q`$ are nonpositive, and that a vertex $`v`$ is legal for a configuration $`𝐜`$ if and only if $`c(v)\mathrm{\Delta }_{vv}`$. ∎

###### Lemma 9.3.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$. Let $`𝐜`$ be a configuration on $`(G,\$)`$, let $`𝐦𝐍^V`$, and let $`v_1\mathrm{}v_k`$ be a sequence of vertices, with multiplicity vector $`𝐧:=\widehat{v}_1+\mathrm{}+\widehat{v}_k`$. Produce the sequence $`w_1\mathrm{}w_{\mathrm{}}`$ by deleting the first $`\mathrm{min}\{m(z),n(z)\}`$ occurrences of vertex $`z`$ from the sequence $`v_1\mathrm{}v_k`$, for each $`zV`$. If $`v_1\mathrm{}v_k`$ is legal for $`𝐜`$ and $`n(\$)=0`$, then $`w_1\mathrm{}w_{\mathrm{}}`$ is legal for $`𝐜^{}:=𝐜Q^{}𝐦`$.

###### Proof.

We proceed by induction on $`k`$, the length of $`v_1\mathrm{}v_k`$.

For the basis of induction, $`k=1`$, assume that $`v\$`$ is legal for $`𝐜`$. If $`m(v)1`$ then the empty sequence is legal for $`𝐜^{}`$, as required. Otherwise, write $`𝐦=\widehat{u}_1+\mathrm{}+\widehat{u}_r`$ for some sequence of vertices $`u_1\mathrm{}u_r`$. Since $`m(v)=0`$, $`v`$ does not occur in the sequence $`u_1\mathrm{}u_r`$. The previous lemma and induction on $`r`$ now show that $`v`$ is legal for $`𝐜^{}`$, as required.

For the induction step, assume the result for sequences of length $`k1`$, and consider $`v_1\mathrm{}v_k`$. First, assume that $`m(v_1)1`$, and consider $`𝐛:=𝐜|v_1`$ and $`𝐦^{}:=m\widehat{v}_1`$. Then $`𝐜^{}=𝐛Q^{}𝐦^{}`$ and $`v_2\mathrm{}v_k`$ is legal for $`𝐛`$. Applying the induction hypothesis to $`𝐛`$, $`𝐦^{}`$, and $`v_2\mathrm{}v_k`$, we see that $`w_1\mathrm{}w_{\mathrm{}}`$ is legal for $`𝐜^{}`$. For the remaining case, assume that $`m(v_1)=0`$, so that $`w_1=v_1`$. As in the basis of induction, since $`v_1`$ is legal for $`𝐜`$, $`v_1`$ is legal for $`𝐜^{}`$. Now apply the induction hypothesis to $`𝐛:=𝐜|v_1`$, $`𝐦`$, and $`v_2\mathrm{}v_k`$ to conclude that $`w_2\mathrm{}w_{\mathrm{}}`$ is legal for $`𝐜^{}|v_1`$. Hence, $`w_1\mathrm{}w_{\mathrm{}}`$ is legal for $`𝐜^{}`$, completing the induction step and the proof. ∎

###### Proposition 9.4.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$. For every configuration $`𝐜`$ on $`(G,\$)`$, the set $`𝒮(𝐜)`$ contains a unique stable configuration.

###### Proof.

Let $`𝒟`$ be the graph with vertex-set $`𝒮(𝐜)`$ and directed edges $`𝐛𝐛|v`$ when $`v\$`$ is legal for $`𝐛𝒮(𝐜)`$. Then $`𝒟`$ is a nonempty graph, and, by the proof of Proposition 9.1, since $`\mathrm{}(𝐛|v)\mathrm{}(𝐛)`$ for all $`𝐛𝒮(𝐜)`$ $`𝒟`$ contains no directed cycles. Therefore, $`𝒟`$ has at least one sink vertex, which is a stable configuration on $`(G,\$)`$.

Now suppose that $`𝐚`$ and $`𝐛`$ are two stable configurations in $`𝒮(𝐜)`$. Let $`v_1\mathrm{}v_k`$ and $`u_1\mathrm{}u_r`$ be sequences of vertices which are legal for $`𝐜`$, do not contain $`\$`$, and are such that $`𝐜|v_1\mathrm{}v_k=𝐚`$ and $`𝐜|u_1\mathrm{}u_r=𝐛`$. Let $`𝐧:=\widehat{v}_1+\mathrm{}+\widehat{v}_k`$ and let $`𝐦:=\widehat{u}_1+\mathrm{}+\widehat{u}_r`$. The hypothesis of Lemma 9.3 is satisfied, so produce the subsequence $`w_1\mathrm{}w_{\mathrm{}}`$ of $`v_1\mathrm{}v_k`$ as in that lemma. Now, since $`w_1\mathrm{}w_{\mathrm{}}`$ is a legal sequence for $`𝐜Q^{}𝐦=𝐜|u_1\mathrm{}u_r=𝐛`$ which does not contain $`\$`$, and since $`𝐛`$ is stable, it follows that $`w_1\mathrm{}w_{\mathrm{}}`$ is the empty sequence. From the construction of $`w_1\mathrm{}w_{\mathrm{}}`$, it follows that $`m(z)n(z)`$ for each $`zV`$. By symmetry, we may repeat this argument with $`v_1\mathrm{}v_k`$ and $`u_1\mathrm{}u_r`$ interchanged, and deduce that $`n(z)m(z)`$ for each $`zV`$. Finally, since $`𝐦=𝐧`$ we conclude that $`𝐚=𝐜Q^{}𝐧=𝐜Q^{}𝐦=𝐛`$, finishing the proof. ∎

We define the *stabilization* of a configuration $`𝐜`$ to be the unique stable configuration in $`𝒮(𝐜)`$. If $`𝐜`$ is a stable configuration, then we define the *successor* $`\sigma (𝐜)`$ of $`𝐜`$ to be the stabilization of $`𝐜|\$`$. Thus, $`\sigma `$ is an endofunction on the set of stable configurations on $`(G,\$)`$. We say that a stable configuration $`𝐜`$ is *critical* when $`\sigma ^k(𝐜)=𝐜`$ for some positive integer $`k`$. (Here, $`\sigma ^k`$ denotes the $`m`$-th functional iterate of $`\sigma `$.)

###### Lemma 9.5.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$.
(a) Every critical configuration on $`(G,\$)`$ is nonnegative.
(b) For every stable configuration $`𝐜`$ on $`(G,\$)`$, there is a nonnegative integer $`m`$ such that $`\sigma ^m(𝐜)`$ is nonnegative.
(b) For every stable configuration $`𝐜`$ on $`(G,\$)`$, there is a nonnegative integer $`m`$ such that $`\sigma ^m(𝐜)`$ is critical.

###### Proof.

For part (a), let $`𝐜`$ be a critical configuration, and let $`v_1\mathrm{}v_k`$ be a nonempty legal sequence of vertices for $`𝐜`$, such that $`𝐜|v_1\mathrm{}v_k=𝐜`$. Then $`𝐧:=\widehat{v}_1+\mathrm{}+\widehat{v}_k`$ is a nonzero vector of nonnegative integers such that $`𝐜=𝐜Q^{}𝐧`$, so that $`Q^{}𝐧=\mathrm{𝟎}`$. By Proposition 3.2, it follows that $`𝐧=\lambda 𝐡`$ is a positive integer multiple of the vector $`𝐡`$ of vertex activities. Every $`vV`$ is fired in the sequence $`v_1\mathrm{}v_k`$ exactly $`\lambda h(v)`$ times, hence at least once, and so $`c(v)0`$ for all $`v\$`$.

For part (b), we use the strategy of the proof of Proposition 9.1, but with a different definition of the label of a configuration. For a configuration $`𝐜`$, define $`𝐜^{}`$ as in the proof of Proposition 9.1. If $`𝐜^{}\mathrm{𝟎}`$, then for each $`v\$`$, let $`d(v)`$ denote the length of a shortest directed path which begins at $`v`$ and ends at a vertex $`w\$`$ such that $`c(w)<0`$, and let $`r`$ be the maximum value of $`d(v)`$ for all $`v\$`$ such that $`c(v)0`$. For $`1jr`$, let $`\mathrm{}_j:=\{c(v):d(v)=j\}`$, and define the ‘label’ of $`𝐜`$ to be $`\mathrm{}(𝐜):=(𝐜^{},\mathrm{}_1,\mathrm{},\mathrm{}_r)`$. Define a partial order on the set of all labels as follows: $`(𝐚,k_1,\mathrm{},k_s)(𝐛,\mathrm{}_1,\mathrm{},\mathrm{}_r)`$ if either $`𝐛𝐚`$ and $`𝐛𝐚`$ is nonnegative (except at $`\$`$), or $`𝐛=𝐚\mathrm{𝟎}`$ (in which case $`s=r>0`$) and $`k_1=\mathrm{}_1`$, $`k_2=\mathrm{}_2`$,…, $`k_{j1}=\mathrm{}_{j1}`$, $`k_j<\mathrm{}_j`$ for some $`1jr`$.

Notice that for any configuration $`𝐚`$ with $`𝐚`$ nonnegative, there are only finitely many stable configurations $`𝐜`$ such that $`𝐜^{}=𝐚`$ (in fact, the number of them is $`\{\mathrm{\Delta }_{vv}:v\$\mathrm{and}a(v)=0\}`$). It follows that the set of all stable configurations, partially ordered by the order $``$ on their labels, has no infinite ascending chains. Now, if $`v`$ is legal for $`𝐜`$ and $`𝐜^{}\mathrm{𝟎}`$, then $`\mathrm{}(𝐜)\mathrm{}(𝐜|v)`$, even when $`v=\$`$. Hence, if $`𝐜`$ is stable but not nonnegative, then $`\mathrm{}(𝐜)\mathrm{}(\sigma (𝐜))`$. Since there are no infinite ascending chains, there is a nonnegative integer $`m`$ such that $`\sigma ^m(𝐜)`$ is maximal, and this must be a stable, nonnegative configuration.

For part (c), let $`𝐜`$ be any stable configuration. By part (b), we may assume that $`𝐜`$ is nonnegative. There are exactly $`\{\mathrm{\Delta }_{vv}:v\$\}`$ nonnegative stable configurations on $`(G,\$)`$, and the successor function acts as an endofunction on this set. Since this set is finite, for any $`𝐜`$ in it there exists a nonnegative integer $`m`$ and positive integer $`k`$ such that $`\sigma ^{m+k}(𝐜)=\sigma ^m(𝐜)`$. That is, $`\sigma ^m(𝐜)`$ is critical. ∎

Let $`𝒞(G,\$)`$ denote the set of all critical configurations of $`(G,\$)`$. For critical configurations $`𝐚`$ and $`𝐛`$ on $`(G,\$)`$, we say that $`𝐚`$ and $`𝐛`$ are *coeval* if $`\sigma ^m(𝐚)=𝐛`$ for some nonnegative integer $`m`$.

###### Lemma 9.6.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$. Coevalence is an equivalence relation on $`𝒞(G,\$)`$, and each Coevalence class has cardinality divisible by $`h(\$)`$, in which $`𝐡`$ is the vector of vertex activities.

###### Proof.

That coevalence is an equivalence relation is easy to see. Let $`𝐜`$ be a critical configuration on $`(G,\$)`$, let $`v_1\mathrm{}v_k`$ be a nonempty sequence of vertices which is legal for $`𝐜`$, such that $`𝐜|v_1\mathrm{}v_k=𝐜`$, and as short as possible subject to these conditions, and let $`𝐧:=\widehat{v}_1+\mathrm{}+\widehat{v}_k`$. As in the proof of Lemma 9.5(a), we see that $`𝐧=\lambda 𝐡`$ for some positive integer $`\lambda `$. Since the bank vertex occurs $`\lambda h(\$)`$ times in the sequence $`v_1\mathrm{}v_k`$ it follows that $`𝐜`$ is coeval with exactly $`\lambda h(\$)`$ critical configurations. ∎

###### Proposition 9.7.

Let $`G=(V,E)`$ be a loopless strongly connected graph, and let $`\$`$ be a simple vertex of $`G`$. Then every coevalence class of $`𝒞(G,\$)`$ is a singleton.

###### Proof.

Let $`𝐡`$ be the vector of vertex activities of $`G`$. Let $`𝐜`$ be any critical configuration of $`(G,\$)`$, and let $`v_1\mathrm{}v_k`$ be a nonempty sequence of vertices which is legal for $`𝐜`$ and such that $`𝐜|v_1\mathrm{}v_k=𝐜`$. Let $`𝐧:=\widehat{v}_1+\mathrm{}+\widehat{v}_k`$ be the multiplicity vector of $`v_1\mathrm{}v_k`$; as in Lemma 9.5(a) we have $`𝐧=\lambda 𝐡`$ for some positive integer $`\lambda `$.

Since $`𝐜`$ is stable, $`v_1=\$`$. If this is the only occurrence of $`\$`$ in the sequence $`v_1\mathrm{}v_k`$, then $`\sigma (𝐜)=𝐜`$ and it follows that the coevalence class of $`𝐜`$ is the singleton $`\{𝐜\}`$. Otherwise, let $`1=p_1<p_2<\mathrm{}<p_rk`$ be all the indices from $`1`$ to $`k`$ such that $`v_{p_i}=\$`$, and let $`p_{r+1}=k+1`$. Since $`𝐧=\lambda 𝐡`$ and $`h(\$)=1`$, we see that $`\lambda =r`$.

Now, $`v_2\mathrm{}v_{p_21}`$ is a legal sequence for $`𝐜|\$`$ which does not contain any occurrence of $`\$`$. Applying Lemma 9.3 with $`𝐦=𝐡\widehat{\$}`$, let $`w_1\mathrm{}w_{\mathrm{}}`$ be the sequence so produced. This sequence is legal for $`(𝐜|\$)Q^{}𝐦=𝐜Q^{}𝐡=𝐜`$, and since $`𝐜`$ is stable, it follows that $`w_1\mathrm{}w_{\mathrm{}}`$ is the empty sequence. Therefore, for each $`\$uV`$, the multiplicity of $`u`$ in $`v_2\mathrm{}v_{p_21}`$ is at most $`h(u)`$.

Since $`𝐛:=𝐜|\$v_2\mathrm{}v_{p_21}`$ is critical, we may repeat the argument of the above paragraph, using $`𝐛|\$`$ and $`v_{p_2+1}\mathrm{}v_{p_31}`$. As above, we conclude that for each $`\$uV`$, the multiplicity of $`u`$ in $`v_{p_2+1}\mathrm{}v_{p_31}`$ is at most $`h(u)`$. For each $`1ir`$, let $`𝐧_i:=\widehat{v}_{p_i+1}+\mathrm{}+\widehat{v}_{p_{i+1}1}`$. Applying the above argument for each sequence $`v_{p_i+1}\mathrm{}v_{p_{i+1}1}`$, we see that $`n_i(u)h(u)`$ for each $`1ir`$ and $`\$uV`$. But $`𝐧_1+\mathrm{}+𝐧_r+r\widehat{\$}=𝐧=r𝐡`$, from which it follows that $`𝐧_1=\mathrm{}=𝐧_r=𝐡\widehat{\$}`$. Therefore, $`𝐜|\$v_2\mathrm{}v_{p_21}=𝐜Q^{}𝐡=𝐜`$, so that $`\sigma (𝐜)=𝐜`$, and it follows that the coevalence class of $`𝐜`$ is the singleton $`\{𝐜\}`$, completing the proof. ∎

###### Example 9.8.

*As the following example shows, if $`\$`$ is not a simple vertex of $`G`$, then it may happen that some coevalence class of $`𝒞(G,\$)`$ has cardinality strictly greater than $`h(\$)`$. Consider the graph $`G`$ with Laplacian matrix and vector of vertex activities*

$$Q=\left[\begin{array}{cccc}\hfill 2& \hfill 1& \hfill 1& \hfill 0\\ \hfill 0& \hfill 2& \hfill 2& \hfill 0\\ \hfill 1& \hfill 0& \hfill 2& \hfill 1\\ \hfill 1& \hfill 1& \hfill 0& \hfill 2\end{array}\right]\mathrm{and}𝐡=\left[\begin{array}{c}\hfill 3\\ \hfill 5\\ \hfill 8\\ \hfill 4\end{array}\right].$$

*Denoting the vertices by $`1`$, $`2`$, $`3`$, $`4`$ corresponding to the matrix indices, take $`\$=1`$ for the bank vertex. Denoting a configuration $`𝐜`$ for this $`(G,\$)`$ by the triple $`c(2)c(3)c(4)`$, we see that the nonnegative stable configurations are mapped by the successor function as*

$$\begin{array}{ccccccccccccc}000& & & & 101& & & & & & & & \\ & & & & & & & & & & & & \\ 110& & 100& & 011& & 001& & 111& & 101& & 110.\end{array}$$

*Thus, $`𝒞(G,\$)`$ has a single coevalence class of cardinality six.*

Finally, we connect the critical group of $`G`$ with the results of this section; this should be compared with Theorems 3.8 and 8.1 of Biggs . Let $`𝐜`$ be any configuration on $`(G,\$)`$, and let $`\overline{𝐜}`$ be the stabilization of $`𝐜`$. From Lemma 9.5(c), there is a nonnegative integer $`m_0`$ such that $`\sigma ^m(\overline{𝐜})`$ is critical for all $`mm_0`$. These critical configurations are all coeval with one another, and this coevalence class is determined uniquely by $`𝐜`$; we denote it by $`[𝐜]`$.

###### Theorem 9.9.

Let $`G=(V,E)`$ be a loopless strongly connected graph with bank vertex $`\$`$, and let $`U𝐙^V`$ consist of those vectors $`𝐮𝐙^V`$ such that $`\mathrm{𝟏}^{}𝐮=0`$. Then $`K(G)`$ is the subgroup $`U/Q^{}𝐙^V`$ of $`𝒦(G)`$, and the elements of $`K(G)`$ correspond bijectively with coevalence classes of critical configurations on $`(G,\$)`$ *via* the correspondence $`𝐮+Q^{}𝐙^V[𝐮]`$.

###### Proof.

For $`𝐱𝐙^V`$ the element $`𝐳+Q^{}𝐙^V`$ of $`𝒦(G)`$ is in $`K(G)`$ if and only if $`\lambda 𝐳Q^{}𝐙^V`$ for some positive integer $`\lambda `$. Since every column $`𝐪`$ of $`Q^{}`$ satisfies $`\mathrm{𝟏}^{}𝐪=0`$, if $`𝐳+Q^{}𝐙^V`$ is in $`K(G)`$ then $`\mathrm{𝟏}^{}𝐳=0`$. Conversely, if $`\mathrm{𝟏}^{}𝐳=0`$ then $`𝐳=Q^{}𝐰`$ for some rational $`V`$-indexed vector $`𝐰`$, since the rank of $`Q^{}`$ is $`n(G)1`$. Hence, $`\lambda 𝐳Q^{}𝐙^V`$ for some positive integer $`\lambda `$, so that $`𝐳+Q^{}𝐙^V`$ is in $`K(G)`$. This proves that $`K(G)=U/Q^{}𝐙^V`$.

For the second claim, consider two configurations $`𝐛`$ and $`𝐜`$ on $`(G,\$)`$, so that $`𝐛,𝐜U`$. If $`[𝐛]=[𝐜]`$ then there are nonnegative integers $`p,q`$ such that $`\sigma ^p(\overline{𝐛})=\sigma ^q(\overline{𝐜})`$. Therefore, there are $`V`$-indexed vectors $`𝐦,𝐧`$ of nonnegative integers such that $`𝐛Q^{}𝐦=𝐜Q^{}𝐧`$, so that $`𝐛𝐜`$ is in $`Q^{}𝐙^V`$. This proves that the map $`𝐮+Q^{}𝐙^V[𝐮]`$ is injective. Since this map is clearly surjective, the theorem is proved. ∎

###### Problem 9.10.

*Given a strongly connected graph $`G`$ and bank vertex $`\$V`$, say that $`\$`$ is *small* when every coevalence class of $`𝒞(G,\$)`$ has cardinality $`h(\$)`$, and that $`\$`$ is *fair* when all coevalence classes of $`𝒞(G,v)`$ have equal cardinality. Are there polynomial-time algorithms for determining whether a given vertex is small, or is fair?*


format: text

text:
# Description of Vorticity by Grassmann Variables and an Extension to Supersymmetry

## 1 Précis of Fluid Mechanics (With No Vorticity)

Let me begin with a précis of fluid mechanical equations . An isentropic fluid is described by a matter density field $`\rho `$ and a velocity field $`𝒗`$, which satisfy a continuity equation involving the current $`𝒋=\rho 𝒗`$:

$$\dot{\rho }+\mathbf{}(\rho 𝒗)=0$$
(1)
and a force equation involving the pressure $`P`$:

$$\dot{𝒗}+𝒗\mathbf{}𝒗=\frac{1}{\rho }\mathbf{}P.$$
(2)
(Over-dot denotes differentiation with respect to time.) For isentropic fields, the pressure $`P`$ is a function only of the density, and the right side of (2) may also be written as $`\mathbf{}V^{}(\rho )`$, where $`V^{}(\rho )`$ is the enthalpy, $`P(\rho )=\rho V^{}(\rho )V(\rho )`$, and $`\sqrt{\rho V^{\prime \prime }(\rho )}=\sqrt{P^{}(\rho )}`$ is the sound speed (prime denotes differentiation with respect to argument).

Equations (1) and (2) can be obtained by bracketing the dynamical variables $`\rho `$ and $`𝒗`$ with the Hamiltonian $`H(\rho ,𝒗)`$

$$H(\rho ,𝒗)=\mathrm{d}r\left(\frac{1}{2}\rho v^2+V(\rho )\right)$$
(3)
$`\dot{\rho }`$ $`=`$ $`\{H,\rho \}`$ (4a)
$`\dot{𝒗}`$ $`=`$ $`\{H,𝒗\}`$ (4b)
provided the nonvanishing brackets of the fundamental variables $`(\rho ,𝒗)`$ are taken to be

$`\{v^i(𝒓),\rho (𝒓^{})\}`$ $`=`$ $`_i\delta (𝒓𝒓^{})`$ (5a)
$`\{v^i(𝒓),v^j(𝒓^{})\}`$ $`=`$ $`{\displaystyle \frac{\omega _{ij}(𝒓)}{\rho (𝒓)}}\delta (𝒓𝒓^{}).`$ (5b)
(The fields in the brackets are at equal times, hence the time argument is suppressed.) Here $`\omega _{ij}`$ is the vorticity, defined as the curl of $`v^i`$:

$$\omega _{ij}=_iv^j_jv^i.$$
(6)
One naturally asks whether there is a canonical 1-form that leads to the symplectic structure (5); that is, one seeks a Lagrangian whose canonical variables can be used to derive (5) from canonical brackets. When the velocity is irrotational, the vorticity vanishes, $`𝒗`$ can be written as the gradient of a velocity potential $`\theta `$, $`𝒗=\mathbf{}\theta `$, and (5) is satisfied by postulating that

$$\{\theta (𝒓),\rho (𝒓^{})\}=\delta (𝒓𝒓^{})$$
(7)
that is, the velocity potential is conjugate to the density, so that the Lagrangian can be taken as

$$L|_{\mathrm{irrotational}}=\mathrm{d}r\theta \dot{\rho }H|_{𝒗=\mathbf{}\theta }$$
(8)
where $`H`$ is given by (3) with $`𝒗=\mathbf{}\theta `$.

## 2 Extending the Formalism to Include Vorticity

The traditional method of including vorticity in a Lagrangian formalism  involves writing the velocity in a more elaborate potential representation, the so-called Clebsch parameterization ,

$$𝒗=\mathbf{}\theta +\alpha \mathbf{}\beta $$
(9)
which supports nonvanishing vorticity

$$\omega _{ij}=_i\alpha _j\beta _j\alpha _i\beta .$$
(10)
The Lagrangian

$$L=\mathrm{d}r\rho (\dot{\theta }+\alpha \dot{\beta })H|_{𝒗=\mathbf{}\theta +\alpha \mathbf{}\beta }$$
(11)
identifies canonical pairs to be $`\{\theta ,\rho \}`$ (as in the irrotational case) and also $`\{\beta ,\alpha \rho \}`$. It then follows that the algebra (5) is satisfied, provided $`𝒗`$ is given by (9). The quantities $`(\alpha ,\beta )`$ are called the “Gauss potentials”.

The situation here is similar to the electromagnetic force law: The Lorentz equation can be presented in terms of the electric and magnetic field strengths, but a Lagrangian for the motion requires describing the fields in terms of potentials.

## 3 Some Further Observations on the
Clebsch Decomposition of the Vector Field $`𝒗`$

In three dimensions, (9) involves the same number of functions on the left and right sides of the equality: three. The total number of dynamical variables $`(\rho ,𝒗)`$ is even – four – so an appropriate phase space can be constructed from the four potentials $`(\rho ,\theta ,\alpha ,\beta )`$. Nevertheless the Gauss potentials are not uniquely determined by $`𝒗`$. The following is the reason why a canonical formulation of (5) requires using the Clebsch decomposition (9). Although the algebra (5) is consistent in that the Jacobi identity is satisfied, it is degenerate in that the kinematic helicity $`h`$

$$h\frac{1}{2}\mathrm{d}^3r𝒗(\mathbf{}\times 𝒗)=\frac{1}{2}\mathrm{d}^3r𝒗𝝎$$
(12)
($`\omega ^i=\frac{1}{2}\epsilon ^{ijk}\omega _{jk}`$) has vanishing bracket with $`\rho `$ and $`𝒗`$. (Note that $`h`$ is just the Abelian Chern-Simons term of $`𝒗`$ .) Consequently, a canonical formulation requires eliminating the kernel of the algebra, that is, neutralizing $`h`$. This is achieved by the Clebsch decomposition: $`𝒗=\mathbf{}\theta +\alpha \mathbf{}\beta `$, $`𝝎=\mathbf{}\alpha \times \mathbf{}\beta `$, $`𝒗𝝎=\mathbf{}\theta (\mathbf{}\alpha \times \mathbf{}\beta )=\mathbf{}(\theta \mathbf{}\alpha \times \mathbf{}\beta )`$. Thus in the Clebsch parameterization the helicity is given by a surface integral $`h=\frac{1}{2}\mathrm{d}𝑺\theta (\mathbf{}\alpha \times \mathbf{}\beta )`$ – it possesses no bulk contribution, and the obstruction to a canonical realization of (5) is removed .

In two spatial dimensions, the Clebsch parameterization is redundant, involving three functions to express the two velocity components. Moreover, the kernel of (5) in two dimensions comprises an infinite number of quantities

$$k_n=\mathrm{d}^2r\rho \left(\frac{\omega }{\rho }\right)^n$$
(13)
for which the Clebsch parameterization offers no simplification. (Here $`\omega `$ is the two-dimensional vorticity $`\omega _{ij}=\epsilon _{ij}\omega `$.) Nevertheless, a canonical formulation in two dimensions also uses Clebsch variables to obtain an even-dimensional phase space.

## 4 Kinematical Grassmann Variables for Vorticity

Rather than using the Gauss potentials $`(\alpha ,\beta )`$ of the Clebsch parameterization (9) in the description of vorticity (10), we propose an alternative that makes use of Grassmann variables . We write

$$𝒗=\mathbf{}\theta \frac{1}{2}\psi _a\mathbf{}\psi _a$$
(14)
where $`\psi _a`$ is a multicomponent, real Grassmann spinor $`\psi _a^{}=\psi _a`$, $`(\psi _a\psi _b)^{}=\psi _a^{}\psi _b^{}`$. (The number of components depends on spatial dimensionality.) Evidently the nonvanishing vorticity is

$$\omega _{ij}=_i\psi _a_j\psi _a.$$
(15)
Moreover, the canonical 1-form in the Lagrangian that replaces (11) reads

$$L=\mathrm{d}r\rho (\dot{\theta }\frac{1}{2}\psi _a\dot{\psi }_a)H|_{𝒗=\mathbf{}\theta \frac{1}{2}\psi \mathbf{}\psi }$$
(16)
The Hamiltonian retains its (bosonic) form (3), but the Grassmann variables are hidden in the formula for the velocity. From the canonical 1-form, we deduce that $`(\theta ,\rho )`$ remain a conjugate pair \[see (7)\] and that the canonically independent Grassmann variables are $`\sqrt{\rho }\psi `$. Thus we postulate, in addition to the Poisson bracket (7) satisfied by $`(\theta ,\rho )`$, a Poisson antibracket for the Grassmann variables

$$\{\psi _a(𝒓),\psi _b(𝒓^{})\}=\frac{\delta _{ab}}{\rho (𝒓)}\delta (𝒓𝒓^{})$$
(17)
and this, together with (7), has the further consequence that the following brackets hold:

$$\{\theta (𝒓),\psi (𝒓^{})\}=\frac{1}{2\rho (𝒓)}\delta (𝒓𝒓^{})$$
(18)
$$\{𝒗(𝒓),\psi (𝒓^{})\}=\frac{\mathbf{}\psi (𝒓)}{\rho (𝒓)}\delta (𝒓𝒓^{}).$$
(19)
The algebra (5) follows.

One may state that it is natural to describe vorticity by Grassmann variables: vortex motion is associated with spin, and the Grassmann description of spin within classical physics is well known. In the model as developed thus far the Grassmann variables have no role beyond the kinematical one of parameterizing vorticity (15) and providing the correct bracket structure. They do not contribute to the equations of motion for $`\rho `$ and $`𝒗`$, (1) and (2) \[even though they are hidden in the formula (14) for $`𝒗`$\]. Moreover, they satisfy a free equation: from (16) it follows that

$$\dot{\psi }+𝒗\mathbf{}\psi =0.$$
(20)
## 5 Dynamical Grassmann Variables for
Supersymmetry

Thus far the Grassmann variables’ only role has been to parameterize the velocity/vorticity (14), (15) and to provide canonical variables for the symplectic structure (5). The equations for the fluid (1), (2) are not polluted by them and they do not appear in the Hamiltonian, beyond their hidden contribution to $`𝒗`$. Thus the equation for the Grassmann fields is free (20).

But now we enquire whether we can add a Grassmann term to the Hamiltonian so that the Grassmann variables enter the dynamics and the entire model enjoys supersymmetry.

We have succeeded for a specific form of the potential $`V(\rho )`$:

$$V(\rho )=\frac{\lambda }{\rho }$$
(21)
and for the specific dimensionalities of space-time: (2+1) and (1+1). The reason for these specificities will be explained in the next Section.

The potential (21), with $`\lambda >0`$, leads to negative pressure

$$P(\rho )=\rho V^{}(\rho )V(\rho )=2\lambda /\rho $$
(22)
and sound speed

$$s=\sqrt{P^{}(\rho )}=\sqrt{2\lambda }/\rho $$
(23)
(hence $`\lambda >0`$). This model is called the “Chaplygin gas”.

Chaplygin introduced his equation of state as a mathematical approximation to the physically relevant adiabatic expressions $`V(\rho )\rho ^n`$ with $`n>0`$ . (Constants are arranged so that the Chaplygin formula is tangent at one point to the adiabatic profile.) Also it was realized that certain deformable solids can be described by the Chaplygin equation of state . These days negative pressure is recognized as a possible physical effect: exchange forces in atoms give rise to negative pressure; stripe states in the quantum Hall effect may be a consequence of negative pressure; the recently discovered cosmological constant may be exerting negative pressure on the cosmos, thereby accelerating expansion.

### 5.1 Planar model

In (2+1) dimensions the Grassmann variables possess 2-components and two real $`2\times 2`$ Dirac “$`\alpha `$”-matrices act on them: $`\alpha ^1=\sigma ^1`$, $`\alpha ^2=\sigma ^3`$. The supersymmetric Hamiltonian is

$$H=\mathrm{d}^2r\left\{\frac{1}{2}\rho v^2+\frac{\lambda }{\rho }+\frac{\sqrt{2\lambda }}{2}\psi 𝜶\mathbf{}\psi \right\}$$
(24)
where it is understood that $`𝒗=\mathbf{}\theta \frac{1}{2}\psi \mathbf{}\psi `$ . While the continuity equation retains its form (1), the force equation acquires a contribution from the Grassmann variables

$$\dot{𝒗}+𝒗\mathbf{}𝒗=\mathbf{}\frac{\lambda }{\rho ^2}+\frac{\sqrt{2\lambda }}{\rho }(\mathbf{}\psi )𝜶\mathbf{}\psi $$
(25)
and $`\psi `$ is no longer free:

$$\dot{\psi }+𝒗\mathbf{}\psi =\frac{\sqrt{2\lambda }}{\rho }𝜶\mathbf{}\psi .$$
(26)
These equations of motion, together with (1), ensure that the following supercharges are time independent:

$`Q`$ $`={\displaystyle \mathrm{d}^2r\left\{\rho 𝒗(𝜶\psi )+\sqrt{2\lambda }\psi \right\}}`$ (27a)
$`\stackrel{~}{Q}`$ $`={\displaystyle \mathrm{d}^2r\rho \psi }.`$ (27b)
They generate the following transformations:

$`\delta \rho `$ $`=\mathbf{}\left[\rho (\eta 𝜶\psi )\right]`$ $`\stackrel{~}{\delta }\rho `$ $`=0`$ (28a)
$`\delta \psi `$ $`=(\eta 𝜶\psi )\mathbf{}\psi 𝒗𝜶\eta {\displaystyle \frac{\sqrt{2\lambda }}{\rho }}\eta `$ $`\stackrel{~}{\delta }\psi `$ $`=\eta `$ (28b)
$`\delta 𝒗`$ $`=(\eta 𝜶\psi )\mathbf{}v+{\displaystyle \frac{\sqrt{2\lambda }}{\rho }}(\eta \mathbf{}\psi )`$ $`\stackrel{~}{\delta }𝒗`$ $`=0`$ (28c)
where $`\eta `$ is a two-component constant Grassmann spinor. The antibrackets of the supercharges produce other conserved quantities:

$`\{Q_a,Q_b\}`$ $`=2\delta _{ab}H`$ (29a)
$`\{\stackrel{~}{Q}_a,\stackrel{~}{Q}_b\}`$ $`=\delta _{ab}N`$ (29b)
$`\{\stackrel{~}{Q}_a,Q_b\}`$ $`=𝜶_{ab}𝑷+\sqrt{2\lambda }\delta _{ab}\mathrm{\Omega }.`$ (29c)
Here $`N`$ is the conserved number $`\mathrm{d}^2r\rho `$, $`𝑷`$ is the conserved momentum $`\mathrm{d}^2r\rho 𝒗`$, and $`\mathrm{\Omega }`$ is a center given by the volume of space $`\mathrm{d}^2r`$.

### 5.2 Lineal model

In (1+1) dimensions the Chaplygin gas equation can be written in compact form in terms of the Riemann coordinates

$$R_\pm =v\pm \sqrt{2\lambda }/\rho .$$
(30)
Both eqs. (1) and (2) are equivalent to

$$\dot{R}_\pm =R_{}\frac{}{x}R_\pm .$$
(31)
It is known that this system is completely integrable . One hint for this is the existence of an infinite number of constants of motion:

$$I_\pm ^n=\mathrm{d}x\rho (R_\pm )^n$$
(32)
are time-independent by virtue of (31).

The supersymmetric Hamiltonian makes use of a real, 1-component Grassmann field $`\psi `$ :

$$H=\mathrm{d}x\left(\frac{1}{2}\rho v^2+\frac{\lambda }{\rho }+\frac{\sqrt{2\lambda }}{2}\psi \frac{}{x}\psi \right).$$
(33)
The velocity is given by $`v=\frac{}{x}\theta \frac{1}{2}\psi \frac{}{x}\psi `$ and the equations of motion for the bosonic variables retain the same form as the absence of $`\psi `$, that is, (1), (2) continue to hold. The Grassmann field satisfies

$$\dot{\psi }+R_{}\frac{}{x}\psi =0$$
(34)
and a general solution follows immediately with the help of (31): $`\psi `$ is an arbitrary function of $`R_+`$.

$$\psi =\mathrm{\Psi }(R_+)$$
(35)
Thus the system remains completely integrable.

The supersymmetry charges and transformation laws are obvious dimensional reductions of (27)–(28):

$`Q`$ $`={\displaystyle \mathrm{d}x\rho R_+\psi }`$ (36a)
$`\stackrel{~}{Q}`$ $`={\displaystyle \mathrm{d}x\rho \psi }`$ (36b)
$`\delta \rho `$ $`=\eta {\displaystyle \frac{}{x}}(\rho \psi )`$ $`\stackrel{~}{\delta }\rho `$ $`=0`$ (37a)
$`\delta \psi `$ $`=\eta \psi \psi ^{}\eta R_+`$ $`\stackrel{~}{\delta }\psi `$ $`=\eta `$ (37b)
$`\delta v`$ $`=\eta (\psi v)^{}+\eta R_+\psi ^{}`$ $`\stackrel{~}{\delta }v`$ $`=0.`$ (37c)
The algebra of these is

$`\{Q,Q\}`$ $`=2H`$ (38a)
$`\{\stackrel{~}{Q},\stackrel{~}{Q}\}`$ $`=N`$ (38b)
$`\{\stackrel{~}{Q},Q\}`$ $`=P+\sqrt{2\lambda }\mathrm{\Omega }.`$ (38c)
In view of (35), we see that evaluating the supercharges $`Q`$ and $`\stackrel{~}{Q}`$ on the solution gives expressions of the same form as the bosonic conserved charges (33).

Indeed, we recognize that two charges in (36) are the first two in an infinite tower of conserved supercharges, which generalizes the infinite number of bosonic conserved quantities (32):

$$Q_n=\mathrm{d}x\rho R_+^n\psi .$$
(39)
## 6 The Origins of Our Models

We have succeeded in supersymmetrizing a specific model – the Chaplygin gas – in specific dimensionalities – the 2-dimensional plane and the 1-dimensional line – leading to nonrelativistic, supersymmetric fluid mechanics in (2+1)- and (1+1)-dimensional space-time. The reason for these specificities is that both models descend from Nambu-Goto models for extended systems in a target space of one dimension higher than the world volume of the extended object. Specifically, a membrane in three spatial dimensions and a string in two spatial dimensions, when gauge-fixed in a light-cone gauge, can be shown to devolve to a bosonic Chaplygin gas in two and one spatial dimensions, respectively . The fluid velocity potential arises from the single dynamical variable in the gauge-fixed Nambu-Goto theory, namely, the transverse direction variable for the membrane in space and the string on a plane. Although purely bosonic Chaplygin gas models in other dimensions can devolve from appropriate Nambu-Goto models for extended objects, for the supersymmetric case we need a superextended object, and these exist only in specific dimensionalities. In our case it is the light-cone parameterized supermembrane in (3+1)-dimensional space-time  and the superstring in (2+1)-dimensional space-time  that give rise to our planar and lineal supersymmetric fluid models.

One naturally wonders whether an arbitrary bosonic potential $`V(\rho )`$ has a supersymmetric partner in arbitrary dimensions, and this problem is under further investigation. One promising approach is to consider parameterizations of extended objects other than the light-cone one. It is known that in the purely bosonic case, other parameterizations of the Nambu-Goto actions lead to other fluid mechanical models, and this should carry over to a supersymmetric generalization.

Incidentally, the existence of Nambu-Goto antecedents of the fluid models that we have discussed allows one to understand some of their remarkable properties: complete integrability in the lineal case; existence of further symmetries (which we have not discussed here) and relation to other models (which devolve from the same extended system, but are parameterized differently from the light-cone method) .


text:
# Constraints on Galaxy Bias, Matter Density, and Primordial Non–Gausianity from the PSC𝑧 Galaxy Redshift Survey

## Abstract

We compute the bispectrum for the IRAS PSC$`z`$ catalog and find that the galaxy distribution displays the characteristic signature of gravity. Assuming Gaussian initial conditions, we obtain galaxy biasing parameters $`1/b_1=1.20_{0.19}^{+0.18}`$ and $`b_2/b_1^2=0.42\pm 0.19`$, with no sign of scale-dependent bias for $`k0.3`$ h/Mpc. These results impose stringent constraints on non-Gaussian initial conditions. For dimensional scaling models with $`\chi _N^2`$ statistics, we find $`N>49`$, which implies a constraint on primordial skewness $`B_3<0.35`$.

PACS numbers: 98.80.Es, 98.65.Dx, 98.80.Hw

Introduction.—What is the nature of the distribution of matter in the universe? Does the galaxy distribution follow the mass distribution on large scales? Our ability to constrain cosmological parameters from galaxy clustering is only as good as our understanding of bias, that is, the relation between the galaxy distribution and the underlying dark matter distribution. In the current structure formation paradigm, most of the matter in the universe is dark, interacting only through gravity, and cold. Small fluctuations, generated in the early universe, grow gravitationally once the universe becomes matter-dominated, leading to the formation of large-scale structure. Non-linear gravitational instability (GI) theory makes specific predictions for the statistical properties of the mass distribution, e.g., how non-Gaussian features arise from Gaussian initial conditions. The extent to which the galaxy distribution follows these predictions can be used to put constraints upon galaxy bias (and thus upon the physics of galaxy formation) and upon the degree of non-Gaussianity of the primordial fluctuations (which constrains the physics of the generation of fluctuations in the early universe).

In this Letter, we report and interpret measurements of the bispectrum for the IRAS PSC$`z`$ galaxy redshift survey . Details of the method and earlier results can be found in two previous papers. In the first , we developed a framework to obtain reliable constraints upon galaxy biasing and primordial non-Gaussianity that takes into account the effects of survey geometry and sampling. In the second , we computed the bispectrum of the galaxy distribution of earlier IRAS redshift catalogs. Due to its larger volume and higher sampling density, the PSC$`z`$ survey yields the best evidence supporting GI and the strongest constraints to date upon galaxy biasing and primordial non-Gaussianity.

The Bispectrum.—In linear perturbation theory (PT), the statistical properties of the primordial fluctuations, Gaussian or non-Gaussian, are preserved. If Gaussian, they can be fully characterized in Fourier space by their power spectrum $`P(k)`$,

$$\stackrel{~}{\delta }_m(𝒌_1)\stackrel{~}{\delta }_m(𝒌_2)=(2\pi )^3\delta _\mathrm{D}(𝒌_1+𝒌_2)P_m(k_1),$$
(1)
where $`\stackrel{~}{\delta }_m(𝒌)`$ is the Fourier transform of the density contrast $`\delta \rho /\rho `$. Assuming a linear and deterministic galaxy bias, $`\delta (𝒙)=b_1\delta _m(𝒙)`$, measurement of the galaxy power spectrum in redshift surveys in the linear regime gives

$$P(k,\mu )=(1+2\beta \mu ^2+\beta ^2\mu ^4)(b_1\sigma _8)^2P_1(k),$$
(2)
where $`\beta \mathrm{\Omega }_m^{0.6}/b_1`$, $`\mu `$ is the cosine of the angle between the wavector and the line of sight, $`\sigma _8`$ is the rms density fluctuation amplitude in spheres of radius $`8h^1\mathrm{Mpc}`$, and $`P_1(k)`$ is the linear mass power spectrum scaled to $`\sigma _8=1`$. Equation (2) illustrates the degeneracies between the parameters $`\mathrm{\Omega }_m`$, $`b_1`$, and $`\sigma _8`$: measurement of the quadrupole to monopole ratio of $`P(k,\mu )`$ via redshift distortions, for example, yields a measurement of $`\beta `$, whereas the overall amplitude of the power spectrum gives in addition an estimate of $`b_1\sigma _8`$. Equation (2) involves the small angle approximation, however for the parameter combinations measured here, the results will be unchanged even if the approximation is dropped.

Additional information is needed to break this degeneracy between $`\mathrm{\Omega }_m`$, $`b_1`$, and $`\sigma _8`$; for example, non-linear effects in pairwise velocities  and in density-velocity comparisons  can be used to constrain different combinations of $`\mathrm{\Omega }_m`$, $`b_1`$, and $`\sigma _8`$. We use here measurements of the bispectrum (see also ). The nonlinearities in the equations of motion of GI induce a characteristic pattern of three-point and higher order correlations . For Gaussian initial conditions, the induced bispectrum $`B_{123}B(k_1,k_2,k_3)`$,

$$\stackrel{~}{\delta }_m(𝒌_1)\stackrel{~}{\delta }_m(𝒌_2)\stackrel{~}{\delta }_m(𝒌_3)=(2\pi )^3\delta _\mathrm{D}(𝒌_1+𝒌_2+𝒌_3)B_{123},$$
(3)
scales as $`B(k)[P(k)]^2`$; it is thus useful to examine the reduced bispectrum amplitude $`Q`$,

$$Q\frac{B_{123}}{P_1P_2+P_1P_3+P_2P_3}.$$
(4)
To leading order in perturbation theory for Gaussian initial conditions, to an excellent approximation GI predicts that $`Q`$ is independent of time and thus of $`\sigma _8`$ and $`\mathrm{\Omega }_m`$; $`Q`$ is a function of triangle shape with a behavior that depends only on the spectral index, $`n_{\mathrm{eff}}(k)=d\mathrm{ln}P_1(k)/d\mathrm{ln}k`$.

We observe galaxies, not mass. At scales larger than the characteristic scale of galaxy formation, it is reasonable to assume that the galaxy density is given by a local transformation of the underlying mass density field; that is, for the smoothed density $`\delta =b_1\delta _m+\frac{1}{2}b_2\delta _m^2+\mathrm{}`$ locally, in which case the galaxy bispectrum amplitude ($`Q`$) is related to the matter amplitude ($`Q_m`$)  as

$$Q=\frac{Q_m}{b_1}+\frac{b_2}{b_1^2}.$$
(5)
This shows how the galaxy bispectrum can be used to break the degeneracies present in linear theory: since $`Q_m`$ is independent of $`\sigma _8`$ and $`\mathrm{\Omega }_m`$, measuring $`Q`$ for different triangles and comparing it to the predicted $`Q_m`$ based upon the measured spectral index gives separate values for the bias parameters $`b_1`$ and $`b_2`$ . In redshift space (where distances are measured by recession velocities using the Hubble law) there are small corrections to Eq. (5) that can be computed; for $`b_1=1`$, $`b_2=0.5`$, and $`\mathrm{\Omega }_m=0.3`$, (5) underestimates the exact result in the large-scale limit by $`\mathrm{\Delta }Q0.14`$, independent of configuration . Thus, it does not affect $`b_1`$, and given the observational uncertainties, it only minimally alters the inferred $`b_2`$.

To estimate the galaxy power spectrum and bispectrum, we follow Feldman, Kaiser, and Peacock  in using the optimal weighted transform of the difference between the data and a tailored synthetic catalog . In addition we construct mock catalogs using second-order Lagrangian PT (2LPT), which agrees with $`N`$-body simulations at the scales we consider . The speed of 2LPT allows us to construct a large number of mock catalogs which take into account the selection function, survey geometry, and redshift-space mapping. This is essential to estimate accurately the mean, errors, covariance, and the distribution of $`Q`$ for different triangles, required to compute the non-Gaussian likelihood function . The 2LPT mock catalog initial conditions are based on a $`\mathrm{\Lambda }`$CDM model with $`\mathrm{\Omega }_m=0.3`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$ ($`\mathrm{\Lambda }`$ stands for the cosmological constant); the linear power spectrum shape parameter $`\mathrm{\Gamma }=\mathrm{\Omega }_mh=0.21`$ is consistent with PSC$`z`$ power spectrum measurements , and the adopted normalization, $`\sigma _8=0.7`$, corresponds to $`\sigma _8^s=0.84`$ in redshift space, consistent with the observed normalization for IRAS galaxies .

Data and Analysis.—The IRAS PSC$`z`$ survey  is based upon the IRAS Point Source Catalog with additions to achieve the best possible uniformity over the sky. Out of the 15411 IRAS galaxies across 84% of the sky, we take the 13180 galaxies in the range $`20h^1\mathrm{Mpc}R500h^1\mathrm{Mpc}`$, with galactic latitude $`|b|10^{}`$, and IRAS 60 micron flux $`f_{60}>0.6\mathrm{Jy}`$. Our results appear graphically in Figures 1 and 2. The bispectrum is defined for closed triangles in Fourier space. We characterize a given triangle by its ordered sides $`k_1k_2k_3`$. In Fig. 1 we show $`Q`$ from PSC$`z`$ as a function of $`k_1`$ for triangles with two sides separated by angle $`\mathrm{cos}\theta =(\widehat{𝒌}_1\widehat{𝒌}_2)`$, for four ranges of $`\theta `$. Since the width of the survey window function is $`0.01h\mathrm{Mpc}^1`$, we confine our quantitative analysis to triangle sides $`k_30.05h\mathrm{Mpc}^1`$, for which deconvolution using the narrow window approximation is accurate . The median of $`Q`$ decreases with increasing $`\theta `$, as predicted by GI  (see Fig. 2).

Figure 2 shows $`Q`$ from PSC$`z`$ as a function of angle $`\theta `$ for triangles with $`0.2k_10.4h\mathrm{Mpc}^1`$ and with two sides of ratio $`k_2/k_1=0.4`$–0.6. The solid curve shows the prediction for $`Q`$ in redshift space, obtained from averaging many 2LPT mock catalogs as detailed above. Symbols show results for bands in $`k_1`$, as identified in the caption. The dependence of $`Q`$ on triangle shape predicted by GI is clearly seen in the data. We employ a likelihood analysis as in to quantify the constraints that this places on galaxy biasing and primordial non-Gaussianity. For Gaussian initial conditions, the dashed curve shows the 2LPT $`\mathrm{\Lambda }`$CDM predictions with the best-fit values $`1/b_1=1.20`$, $`b_2/b_1^2=0.42`$, as given in Table 1.

Figure 3 shows the likelihood contours and marginalized distributions for $`1/b_1`$ and $`b_2/b_1^2`$ for the PSC$`z`$ survey, assuming Gaussian initial conditions and including triangles with $`k<k_{\mathrm{max}}=0.3h\mathrm{Mpc}^1`$, where the upper limit is imposed by both nonlinearity and discreteness. We have varied the maximum wavenumber allowed in the analysis, $`k_{\mathrm{max}}=0.2`$, 0.25, and $`0.3h\mathrm{Mpc}^1`$, (see Table 1.) The maximum likelihood values are essentially independent of $`k_{\mathrm{max}}`$, though the error bars decrease as $`k_{\mathrm{max}}`$ is increased. There is no evidence that the bias parameters depend on $`k`$. These results for $`b_1`$ and $`b_2`$ are insensitive to the values of $`\sigma _8`$ and $`\mathrm{\Omega }_m`$ adopted in the mock catalogs , but they do depend upon the assumed value for $`\mathrm{\Gamma }`$, since it determines the predicted $`Q_m`$ .

If galaxy biasing is local in Lagrangian, rather than Eulerian space (imposed on the initial, rather than final conditions), then $`Q`$ in Eq.(5) has an additional term which depends upon configuration . We have repeated the likelihood analysis for such a model and found that the likelihood ratio for the Eulerian to Lagrangian maximum likelihood is $`_E/_L=1.6`$. This implies that the behavior of the bispectrum for PSC$`z`$ galaxies is better described by an Eulerian bias scheme.

The PSC$`z`$ bispectrum provides strong constraints upon non-Gaussian initial conditions. As an extension of the results in , we consider $`\chi _N^2`$ statistics as a general example of dimensional scaling models, where the linear PT $`n`$-point correlation function $`\xi _n\xi _2^{n/2}`$. For $`N=1`$, this corresponds to the predictions of some inflationary models with isocurvature perturbations ; as $`N\mathrm{}`$ the model becomes effectively Gaussian, and for a fixed power spectrum (taken to fit that of PSC$`z`$) the primordial bispectrum obeys $`Q^IN^{1/2}`$ . In addition, there are two other contributions that partially cancel that scale as $`N^1`$ . The amplitude and scaling of the PSC$`z`$ bispectrum constrains $`N`$ to be considerably larger than unity. Thus, we use $`Q(N)Q_G+(Q_{\chi ^2}Q_G)N^{1/2}`$, and similarly for the errors, where $`Q_G`$ and $`Q_{\chi ^2}`$ are obtained from mock catalogs for Gaussian and $`N=1`$ initial conditions, respectively. In addition, we assume that $`Q`$-eigenmodes and eigenvalues are well approximated by the Gaussian ones in the large $`N`$ regime. We construct a likelihood for $`N`$ by marginalizing over the bias; from this we obtain $`N>49(22)`$ at 68% (95%) CL. Since the primordial dimensionless skewness is $`B_3=2.46`$ for a $`\chi _1^2`$ field , we conclude that the PSC$`z`$ bispectrum constrains $`B_3<0.35(0.52)`$.

Discussion.—Our findings are consistent with previous studies from sparser and smaller IRAS surveys , but using the PSC$`z`$ catalog reduces the statistical and systematic errors and allows us to place the strongest constraints to date upon nonlinear bias and primordial non-Gaussianity. Our main results are the following:

(1) The dependence of the bispectrum upon configuration shape is the clearest direct evidence to date that non-linear mode couplings are as specified in GI.

(2) The linear bias parameter we find, $`1/b_1=1.20_{0.18}^{+0.19}`$, agrees well with $`b_1=0.84\pm 0.28`$  obtained by a joint analysis of the PSC$`z`$ power spectrum, cosmic microwave background (CMB) anisotropy, and cluster abundances. It is also consistent with that inferred for APM galaxies  using the shape of the two-point correlation function, $`b_{\mathrm{APM}}=1.11\pm 0.22`$ , taking into account the relative bias $`b_{\mathrm{APM}}/b_{\mathrm{PSCz}}=1.15`$ . It is in less good agreement but still consistent with $`b_{\mathrm{PSCz}}=1.10\pm 0.23`$ (95% CL) found from a concordance between PSC$`z`$ and recent CMB results .

(3) We obtain a nonlinear bias $`b_2/b_1^2=0.48_{0.18}^{+0.19}`$, which is not yet measured in any other way. A negative $`b_2`$ means that the number of IRAS galaxies does not rise as quickly as the mass density contrast; this is consistent with the observation that infrared-selected galaxies are increasingly under–represented in massive clusters.

(4) That both the scale and shape dependence of the bispectrum are consistent with GI acting on Gaussian initial conditions limits the possibility of primordial non-Gaussianity. In particular, our study of $`\chi _N^2`$ initial conditions constrains $`N>49`$ and the primordial skewness to be $`B_3<0.35`$.

(5) Our results for the bispectrum are consistent with the galaxy skewness $`S_3`$ measured for the same catalog  and are similarly insensitive to the flux cut: we find identical results for $`f_{60}>0.8\mathrm{Jy}`$. Further, the PSC$`z`$ data is incomplete beyond $`420h^1\mathrm{Mpc}`$ , however, since we look at $`k>0.05`$, this should not affect the bispectrum signal.

(6) When coupled with measurements of the power spectrum redshift distortions, which determine $`\beta =\mathrm{\Omega }_m^{0.6}/b_10.4\pm 0.12`$ for the PSC$`z`$ survey , our measurement of $`b_1`$ from the bispectrum allows one to break the degeneracy between linear bias and $`\mathrm{\Omega }_m`$: we find $`\mathrm{\Omega }_m=0.16\pm 0.1`$, indicating a low-density universe. We stress that, unlike other methods, this result is based only on the clustering properties of PSC$`z`$ galaxies assuming Gaussian initial conditions, independent to a large extent of external determinations of $`\sigma _8`$.

Due to its almost complete sky coverage and large volume, the PSC$`z`$ survey is the best survey available to study the bispectrum at large scales. This will soon change with the advent of larger redshift surveys such as 2dF and SDSS, which will determine the bispectrum even more precisely and thus test the GI framework, nonlinear galaxy bias, and primordial non-Gaussianity to unprecedented accuracy.

Research supported in part by the NSF grant AST-0070702 at Kansas, by the DOE and NASA grant NAG5-7092 at Fermilab, and by NASA NAG5-2835 at Florida. RS is supported by endowment funds from the IAS and thanks M. Zaldarriaga for useful discussions. We thank A. Hamilton and M. Tegmark for useful comments.