Enumeration of walks on lattices. I

Aleksandrs Mihailovs Department of Mathematics University of Pennsylvania Philadelphia, PA 19104-6395 mihailov@math.upenn.edu http://www.math.upenn.edu/∼mihailov/

March 25, 1998

Abstract

This work develops a methodical approach to counting of walks on cartesian products, biproducts, symmetric and exterior powers and bipowers, Schur operations, coverings and semicoverings of weighted graphs. For weight and root lattices of semisimple Lie algebras, this approach allows us to compute various combinatorial and representation-theoretical constants, in particular, the number of plane symplectic wave graphs with given number of vertices.

1 Introduction

If it is not specified, a graph here means the graph in the most general sense, i. e. it can contain multiple edges, loops and some edges can be directed. The only restriction is that all graphs considered here, are locally finite, i. e. have a finite degree of each vertex. We denote E(G) and V (G) the sets of edges and vertices of the graph G, as usual. Then

E(G) = E_{d}(G) ⨿ E_{u}(G),  (1.1)

where E_{d}(G) and E_{u}(G) are the sets of the directed or undirected edges, correspondingly. All loops are supposed to be directed. Adjacency matrix A(G) is the V (G) × V (G) matrix such that A(G)_{uv} is the number of edges (both directed and undirected) from u to v.

A graph morphism α : G_{1} → G_{2} is a pair of maps

α_{V} : V (G_{1}) → V (G_{2}), α_{E} : E(G_{1}) → E(G_{2})  (1.2)

such that for any edge e ∈ E(G_{1}) from u to v the edge α(e) ∈ E(G_{2}) is an edge from α(u) to α(v) of the same type, directed or undirected, as e. Graphs and their morphisms form a category.

A weighted graph is a graph G with the weight function w : E(G) → Z, where Z is a ring of weights. Z can be any commutative ring and we suppose that this ring is fixed during this article. Weight matrix W (G) of a weighted graph G is the V (G) × V (G) Z-matrix such that

W (G)_{uv} = ∑_{\begin{matrix}e from \\ u to v \end{matrix}} w(e).  (1.3)

A weighted graph morphism α : G_{1} → G_{2} is a graph morphism from G_{1} to G_{2} such that w(α(e)) = w(e) for any edge e ∈ E(G_{1}). Weighted graphs and their morphisms form a category.

If Z is an ordered ring, i. e. its underlying set is ordered such that a > 0, b > 0 implies a + b > 0 and ab > 0 and if w(e) > 0 for all edges e ∈ E(G), then we’ll say that G is a positive weighted graph. Positive weighted graphs and their morphisms form a category as well.

We can consider each graph G as a positive weighted graph with Z = ℤ and w ≡ 1. In that case A(G) = W (G).

We’ll call a weighted graph reduced iff it is a graph without multiple edges, such that its weight function is nonzero for all its edges. Reduced graphs and their morphisms form a category, too.

Cartesian product of (weighted) graphs G_{1} × G_{2} is a graph with

V (G_{1} × G_{2}) = V (G_{1}) × V (G_{2}), E(G_{1} × G_{2}) = (V (G_{1}) × E(G_{2})) ⨿ (E(G_{1}) × V (G_{2})) (1.4)

supposing that for edge e ∈ E(G_{2}) from u to v, the edge (v_{1}, e) is an edge from (v_{1}, u) to (v_{1}, v) of the same type, directed or undirected, as e and w(v_{1}, e) = w(e) and analogously for the edges of another type.

Example 1.1. Let G = P_{2}:

[figure: 0; 1; 2]

Then P_{2} × P_{2} looks as follows:

[figure]

Biproduct of (weighted) graphs G_{1} ×_{2} G_{2} is a graph with

V (G_{1} ×_{2} G_{2}) = V (G_{1}) × V (G_{2}), E(G_{1} ×_{2} G_{2}) ≃ (E(G_{1}) × E(G_{2})) ⨿ (E_{u}(G_{1}) × E_{u}(G_{2})) (1.5)

supposing that for edges e_{1} ∈ G_{1} from u_{1} to v_{1} and e_{2} ∈ G_{2} from u_{2} to v_{2}, at least one of which is directed, the edge (e_{1}, e_{2}) is a directed edge from (u_{1}, v_{1}) to (u_{2}, v_{2}), and w(e_{1}, e_{2}) = w(e_{1})w(e_{2}); actually if one of those edges was undirected, considering it as an edge from u to v, or from v to u, we got two undirected edges in the biproduct; for both undirected edges we got two undirected edges: from (u_{1}, v_{1}) to (u_{2}, v_{2}) and from (u_{1}, v_{2}) to (u_{2}, v_{1}), both of the same weight w(e_{1})w(e_{2}).

Below, in Example 3.11 you could find a pictures of P_{2} ×_{2} P_{2}.

For unweighted either directed or undirected graphs biproduct G = G_{1} ×_{2} G_{2} together with the canonical projections

\begin{matrix}Pr_{1} : G → G_{1}, V (G) ∋ (v_{1}, v_{2}) ↦ v_{1} ∈ G_{1}, \\ Pr_{2} : G → G_{2}, V (G) ∋ (v_{1}, v_{2}) ↦ v_{2} ∈ G_{2}, \end{matrix}  (1.6)

projecting an edge from (u_{1}, v_{1}) to (u_{2}, v_{2}) onto the edges from u_{1} to u_{2} and from v_{1} to v_{2}, correspondingly, is a product in the category-theoretical sense.

2 Cartesian products

Definition 2.1. Denote c_{n}(G, u → v) the count of walks of length n starting in the vertex u and ending in the vertex v of the graph G. Set

c_{0}(G, u → v) = δ_{uv}.  (2.1)

Also denote

c(G, u → v) = ∑_{n=0}^{∞} \frac{c_{n}(G, u → v)}{n!}t^{n}  (2.2)

the exponential generating function.

Theorem 2.2. For a Cartesian product G_{1} × G_{2},

c(G_{1} × G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = c(G_{1}, u_{1} → v_{1}) c(G_{2}, u_{2} → v_{2}).  (2.3)

Proof. By the definition of Cartesian product, for each edge ((a_{1}, a_{2}), (b_{1}, b_{2})) of G_{1} × G_{2}, we have either a_{1} = b_{1} and (a_{2}, b_{2}) is an edge of G_{2}, or (a_{1}, b_{1}) is an edge of G_{1} and a_{2} = b_{2}. Choose a walk of length n on the Cartesian product. If k of its edges are of the second kind, then the other n − k edges are of the first kind. In this case k edges of type (a_{1}, b_{1}) form a walk of length k on G_{1} and n − k edges of type (a_{2}, b_{2}) form a walk of length n − k on G_{2}. From the other side, for each pair of walks of length k on G_{1} and of length n − k on G_{2}, we can construct a walk on G_{1} × G_{2} by \binom{n}{k} ways, moving on k arbitrarily chosen steps between 1 and n along the corresponding edge of the second kind and on the other n − k steps—along the corresponding edge of the first kind. Hence

c_{n}(G_{1} × G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = ∑_{j=0}^{n} \binom{n}{j}c_{j}(G_{1}, u_{1} → v_{1})c_{n−j}(G_{2}, u_{2} → v_{2}).  (2.4)

But it means the same as (2.3).

Definition 2.3. Denote C(G) the V (G) × V (G) matrix with

C(G)_{uv} = c(G, u → v).  (2.5)

Corollary 2.4. For a Cartesian product G_{1} × G_{2},

C(G_{1} × G_{2}) = C(G_{1}) ⊗ C(G_{2}).  (2.6)

Proof. It immediately follows from Theorem 2.2 and the definition of a tensor product.

Lemma 2.5. C(G) = e^{A(G)t}.

Proof. By the definition of an exponent,

e^{A(G)t} = ∑_{n=0}^{∞} \frac{(A(G))^{n}}{n!} t^{n}.  (2.7)

So, we have to check that

((A(G))^{n})_{uv} = c_{n}(G, u → v).  (2.8)

But

((A(G))^{n})_{uv} = ∑ A(G)_{u_{1}v_{1}} … A(G)_{u_{n}v_{n}},  (2.9)

where (u_{1}, v_{1}), …, (u_{n}, v_{n}) is a walk between u and v. Each summand in (2.9) equals 1, that proves (2.8).

Formulas (2.8–2.9) suggest following

Definition 2.6. For a weighted graph G, denote

c_{n}(G, u → v) = ∑ w(u_{1}, v_{1}) … w(u_{n}, v_{n})  (2.10)

where (u_{1}, v_{1}), …, (u_{n}, v_{n}) is a walk between u and v and w(u, v) is the weight of the edge (u, v). Let Z{t} be Z-algebra of exponential series

∑_{n=0}^{∞} z_{n} \frac{t^{n}}{n!} , z_{n} ∈ Z.  (2.11)

Denote c(G, u → v) ∈ Z{t} and C(G) by (2.2) and (2.5) as well.

Lemma 2.7. For a weighted graph G,

C(G) = e^{W (G)t}.  (2.12)

Proof. See the proof of Lemma 2.5.

Lemma 2.8. For a Cartesian product of graphs G_{1} × G_{2},

A(G_{1} × G_{2}) = A(G_{1}) ⊗ I_{V (G_{2})} + I_{V (G_{1})} ⊗ A(G_{2}),  (2.13)

where I is an identity matrix.

Proof. G_{1} × G_{2} has two kinds of edges, see the proof of Theorem 2.2. Each kind conforms to the corresponding summand in (2.13).

Definition 2.9. For matrices W_{1} and W_{2}, denote

W_{1} ⊎ W_{2} = W_{1} ⊗ I + I ⊗ W_{2},  (2.14)

where I is an identity matrix of the size of W_{2} first time and of the size of W_{1} second time.

Lemma 2.10. For a Cartesian product of weighted graphs G_{1} × G_{2},

W (G_{1} × G_{2}) = W (G_{1}) ⊎ W (G_{2}).  (2.15)

Proof. The same as for Lemma 2.8. Theorem 2.11. For a Cartesian product of weighted graphs G_{1} × G_{2},

c(G_{1} × G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = c(G_{1}, u_{1} → v_{1}) c(G_{2}, u_{2} → v_{2}).  (2.16)

Proof. The same as for Theorem 2.2. Corollary 2.12. For a Cartesian product of weighted graphs G_{1} × G_{2},

C(G_{1} × G_{2}) = C(G_{1}) ⊗ C(G_{2}).  (2.17)

Proof. It immediately follows from Theorem 2.11 and the definition of a tensor product. Corollary 2.13. For any locally finite, i. e. with a finite number of nonzero elements in each row and each column, matrices W_{1} and W_{2},

e^{(W_{1}⊎W_{2})t} = e^{W_{1}t} ⊗ e^{W_{2}t}.  (2.18)

Proof. It follows from Lemmas 2.7 and 2.10 and Corollary 2.12.

3 Biproducts

Definition 3.1. Denote \overrightarrow{G} the directed (weighted) graph obtained from a (weighted) graph G by preserving all its vertices and directed edges (with their weights), and by the replacement of each of its undirected edges by a pair of opposite directed edges (of the same weight) between the same vertices. Lemma 3.2. A(\overrightarrow{G}) = A(G) and W (\overrightarrow{G}) = W (G).

Proof. It follows immediately from the definitions of the matrices A(G) and W (G). Corollary 3.3. C(\overrightarrow{G}) = C(G).

Proof. It follows from Lemmas 2.5, 2.7 and 3.2.

Lemma 3.4. \overrightarrow{G_{1} ×_{2} G_{2}} ≃ \overrightarrow{G_{1}} ×_{2} \overrightarrow{G_{2}}.

Proof. Again it follows immediately from the definitions.

Definition 3.5. Denote ∘ the coefficient-wise product in Z{t}:

(∑_{n=0}^{∞} x_{n} \frac{t^{n}}{n!} ) ∘ (∑_{n=0}^{∞} y_{n} \frac{t^{n}}{n!} ) = ∑_{n=0}^{∞} x_{n}y_{n} \frac{t^{n}}{n!} .  (3.1)

Theorem 3.6. For a biproduct G_{1} ×_{2} G_{2} of (weighted) graphs,

c(G_{1} ×_{2} G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = c(G_{1}, u_{1} → v_{1}) ∘ c(G_{2}, u_{2} → v_{2}),  (3.2)
c_{n}(G_{1} ×_{2} G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = c_{n}(G_{1}, u_{1} → v_{1}) c_{n}(G_{2}, u_{2} → v_{2}).  (3.3)

Proof. By Corollary 3.3 and Lemma 3.4, we can suppose that the graphs G_{1} and G_{2} are directed. Consider the canonical projections Pr_{1} and Pr_{2} defined in (1.6). They project each walk on G_{1} ×_{2} G_{2} onto two walks of the same length on G_{1} and G_{2}. Conversely, each pair of walks of equal lengths on G_{1} and G_{2} produce a walk on G_{1} ×_{2} G_{2} of the same length, where we choose the product of the first edges on the first step, the second edges on the second step and so on. Thus, we have a bijection between the corresponding sets of walks on G_{1} ×_{2} G_{2} and pairs of walks of the same length on G_{1} and G_{2}. That proves (3.3) and (3.2) follows from (3.3) for all n. The weight of a walk on G_{1} ×_{2} G_{2} equals the product of the weights of the corresponding walks on G_{1} and G_{2} as well.

Definition 3.7. We’ll call a graph G bipartite if the set of its vertices is divided on two nonintersecting parts

V (G) = V_{0}(G) ⨿ V_{1}(G)  (3.4)

such that there are no edges between vertices lying in the same part, i. e. each edge of G has an end in V_{0}(G) and another one—in V_{1}(G). In particular, bipartite graphs can’t contain loops.

Definition 3.8. Let G_{1} and G_{2} be bipartite graphs. We’ll say that a vertice (v_{1}, v_{2}) of their biproduct G_{1} ×_{2} G_{2}, is even, if either

v_{1} ∈ V_{0}(G_{1}), v_{2} ∈ V_{0}(G_{2}), or v_{1} ∈ V_{1}(G_{1}), v_{2} ∈ V_{1}(G_{2}),  (3.5)

and odd otherwise, i. e. if either

v_{1} ∈ V_{0}(G_{1}), v_{2} ∈ V_{1}(G_{2}), or v_{1} ∈ V_{1}(G_{1}), v_{2} ∈ V_{0}(G_{2}).  (3.6)

Lemma 3.9. Each edge of a biproduct of bipartite graphs connects the vertices of the same parity, i. e. its ends are either both even, or both odd.

Proof. For an edge connecting the vertices (u_{1}, u_{2}) and (v_{1}, v_{2}) of G_{1} ×_{2} G_{2}, if

u_{1} ∈ V_{a}(G_{1}), u_{2} ∈ V_{b}(G_{2}),  (3.7)

then

v_{1} ∈ V_{1−a}(G_{1}), v_{2} ∈ V_{1−b}(G_{2}),  (3.8)

and

a + b ≡ (1 − a) + (1 − b) mod 2,  (3.9)

that means that the vertices (u_{1}, u_{2}) and (v_{1}, v_{2}) are both even or odd simultaneously.

Definition 3.10. For a bipartite (weighted) graphs G_{1} and G_{2} denote G_{1} ×_{0} G_{2} and G_{1} ×_{1} G_{2} the complete (weighted) subgraphs of the biproduct G_{1} ×_{2} G_{2}, spanned by the even or odd vertices, correspondingly. We’ll call these graphs an even and an odd product of G_{1} and G_{2}, correspondingly.

Example 3.11. Let G = P_{2} with V_{0}(P_{2}) = {0, 2}, V_{1}(P_{2}) = {1}:

[figure: 0; 1; 2]

Then G ×_{0} G and G ×_{1} G look as follows:

[figure: P_{2} ×_{0} P_{2}; P_{1} ×_{1} P_{2}]

Corollary 3.12. For a bipartite (weighted) graphs G_{1} and G_{2},

c(G_{1} ×_{0} G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = c(G_{1}, u_{1} → v_{1}) ∘ c(G_{2}, u_{2} → v_{2}),  (3.10)
c(G_{1} ×_{1} G_{2}, (u_{1}, u_{2}) → (v_{1}, v_{2})) = c(G_{1}, u_{1} → v_{1}) ∘ c(G_{2}, u_{2} → v_{2}).  (3.11)

Proof. It is a corollary of Theorem 3.6 and Lemma 3.9.

4 Homogeneous graphs

Definition 4.1. A pair of (weighted) graph G and a group of its automorphisms Γ ⊆ Aut G forms a homogeneous (weighted) graph if for each two vertices u, v of G there is an automorphism g ∈ Γ such that g(u) = v. If Γ is an Abelian group, we’ll say that G is an Abelian (weighted) graph and Γ is its translation group.

Lemma 4.2. Let (u, u_{1}), …, (u, u_{d}) be the list of all the edges starting from a vertex u of a (weighted) homogeneous graph (G, Γ) ( and w_{1}, …, w_{d} be their weights). Then for any vertex v of G and for any g ∈ Γ such that v = g(u), the list of all the edges starting from v is (v, g(u_{1})), …, (v, g(u_{d})) ( and they have the same weights w_{1}, …, w_{d}).

Proof. Because g is an automorphism.

Definition 4.3. Let Γ be a group, H its subgroup and g_{1}, …, g_{d} elements of Γ. Denote (Γ, H, (w_{1})g_{1}, …, (w_{d})g_{d}) a (weighted) graph with the set of vertices Γ/H, edges of which, starting in gH are (gH, gg_{1}H), …, (gH, gg_{d}H) (with weights w_{1}, …, w_{d}, correspondingly) for any gH ∈ Γ/H.

Theorem 4.4. The pair ((Γ, H, (w_{1})g_{1}, …, (w_{d})g_{d}), Γ/H_{Γ}) where

H_{Γ} = ⋂_{g∈Γ} gHg^{−1}  (4.1)

is a homogeneous (weighted) graph for any admissible data. Each (weighted) homogeneous graph (G, Γ), edges of which (of weights w_{1}, …, w_{d}), starting in its vertex u, are (u, u_{1}), …, (u, u_{d}), is isomorphic to a graph (Γ, H, (w_{1})g_{1}, …, (w_{d})g_{d}) with H_{Γ} = 0 where H ⊆ Γ is the stabilizer of a vertex u and u_{1} = g_{1}(u), …, u_{d} = g_{d}(u).

Proof. Elements of H_{Γ} act trivially on Γ/H and if xgH = gH, then x ∈ gHg^{−1}. It means that x ∈ H_{Γ} iff x acts trivially on Γ/H. By definition (4.1), H_{Γ} is a normal subgroup of Γ, so Γ/H_{Γ} ⊆ Aut(Γ, H, …) and it acts transitively on Γ/H, because Γ acts transitively. Everything remaining except the triviality of H_{Γ} follows from Lemma 4.2. H_{Γ} ⊆ Γ ⊆ Aut G must be trivial, because only the neutral element of Aut G acts trivially on G.

Theorem 4.5. Let (G, Γ) be a connected homogeneous (weighted) graph and (u, g_{1}(u)), …, (u, g_{d}(u)) be a list of all its edges, starting in a vertex u. Then (G, Γ_{0}) is a homogeneous (weighted) graph as well, where Γ_{0} is the subgroup of Γ, generated by g_{1}, …, g_{d}.

Proof. By Lemma 4.2, each edge, starting from Γ_{0}u has the form (g(u), gg_{i}(u)) with g ∈ Γ_{0}, hence it ends in Γ_{0}u as well, because gg_{i} ∈ Γ_{0}. Analogously, the edges ending in Γ_{0}u, has the form (g(u), gg_{i}(u)) with gg_{i} ∈ Γ_{0} and they start in Γ_{0}u as well, because g = (gg_{i})g_{i}^{−1} ∈ Γ_{0}. It means that Γ_{0}u contains the connected component of u, i. e.

Γ_{0}u = G.  (4.2)

Theorem 4.6. Each Abelian (weighted) graph with the translation group Γ is isomorphic to a graph (Γ, 0, (w_{1})g_{1}, …, (w_{d})g_{d}). If G is connected, then elements g_{1}, …, g_{d} generate Γ.

Proof. We already know from Theorem 4.4 that a graph is isomorphic to a (Γ, H, (w_{1})g_{1}, …, (w_{d})g_{d}) with H_{Γ} = 0. For an Abelian Γ we have H_{Γ} = H, hence H = 0. It means that for each vertex v of G, there is a unique element g ∈ G such that v = gu. Now, from (4.2), Γ = Γ_{0}.

Corollary 4.7. The translation group of a connected Abelian (weighted) graph is finite generated, i. e. isomorphic to ℤ^{r} ⊕(ℤ/q_{1}ℤ)⊕⋯⊕(ℤ/q_{k}ℤ) where q_{1}, …, q_{k} are some powers of prime numbers.

Proof. It follows immediately from Theorem 4.6.

Lemma 4.8. For any vertices u, v of a (weighted) homogeneous graph G and an automorphism g of G,

c_{n}(G, u → v) = c_{n}(G, g(u) → g(v))  (4.3)
c(G, u → v) = c(G, g(u) → g(v)).  (4.4)

Proof. Applying g to both vertices of each edge of a walk from u to v, we get a walk from g(u) to g(v). Applying g^{−1} to both vertices of each edge of a walk from g(u) to g(v), we get a walk from u to v. Since these operations are inverse, we get a bijection between the corresponding sets.

Definition 4.9. For an automorphisms g ∈ Γ of a (weighted) homogeneous graph G = (Γ, H, …) denote

c_{n}(G, g) = c_{n}(G, H → gH)  (4.5)
c(G, g) = c(G, H → gH).  (4.6)

Lemma 4.10. For any vertices g_{0}H, g_{1}H of a (weighted) homogeneous graph G = (Γ, H, …),

c_{n}(G, g_{0}H → g_{1}H) = c_{n}(G, g_{0}^{−1}g_{1}),  (4.7)
c(G, g_{0}H → g_{1}H) = c(G, g_{0}^{−1}g_{1}).  (4.8)

Proof. It follows from Lemma 4.8 with u = H, v = g_{0}^{−1}g_{1}H and g = g_{0}.

Theorem 4.11. Cartesian product of homogeneous (weighted) graphs is a homogeneous (weighted) graph, and for graphs defined in Definition 4.3,

c(G_{1} × G_{2}, (g_{1}, g_{2})) = c(G_{1}, g_{1}) c(G_{2}, g_{2}).  (4.9)

Proof. Cartesian product of automorphisps is an automorphism and we can use Theorems 2.2 and 2.11.

Definition 4.12. Let Z be the ring of weights and Γ be a group. Denote Z(Γ){t} the Z{t}-algebra of exponential series

∑_{n=0}^{∞} z_{n} \frac{t^{n}}{n!} , z_{n} ∈ Z(Γ),  (4.10)

with coefficients in the group algebra

Z(Γ) = Z ⊗ ℤ(Γ).  (4.11)

Theorem 4.13. For G = (Γ, 0, (w_{1})g_{1}, …, (w_{d})g_{d}), the matrix C(G) is the matrix of right multiplication on e^{((w_{1})g_{1}+···+(w_{d})g_{d})t} in the topological basis (g)_{g∈Γ} of the Z{t}-algebra Z(Γ){t}.

Proof. By Lemma 4.2, the adjacency (weight) matrix A(G) (or W (G) correspondingly) is the matrix M of right multiplication on ((w_{1})g_{1} + ⋯ + (w_{d})g_{d}) in the given basis, i. e. for g ∈ Γ,

gM = ∑_{h∈Γ} M_{gh}h.  (4.12)

Now, Theorem 4.13 follows from Lemmas 2.5 and 2.7.

Corollary 4.14. For G = (Γ, 0, (w_{1})g_{1}, …, (w_{d})g_{d}),

((w_{1})g_{1} + ⋯ + (w_{d})g_{d})^{n} = ∑_{g∈Γ} c_{n}(G, g)g,  (4.13)
e^{((w_{1})g_{1}+···+(w_{d})g_{d})t} = ∑_{g∈Γ} c(G, g)g.  (4.14)

Proof. (4.14) follows from Theorem 4.13 and (4.12) for M = C(G) and neutral g in (4.12). Considering coefficients at t^{n}, we get (4.13).

5 Composite walks

Definition 5.1. Let k ≥ 2. For vertices v_{0}, v_{1}, …, v_{k} of a (weighted) graph G denote c_{n}(G, v_{0} → v_{1} → ⋯ → v_{k}) the number of walks (the sum (2.10) along walks) from v_{0} coming successively through v_{1}, …, v_{k−1} to v_{k}. Denote

c(G, v_{0} → v_{1} → ⋯ → v_{k}) = ∑_{n=0}^{∞} \frac{c_{n}(G, v_{0} → v_{1} → ⋯ → v_{k})}{n!}t^{n}.  (5.1)

Lemma 5.2. For vertices v_{0}, v_{1}, …, v_{k} of a (weighted) homogeneous graph G and an automorphism g of G,

c_{n}(G, v_{0} → v_{1} → ⋯ → v_{k}) = c_{n}(G, g(v_{0}) → g(v_{1}) → ⋯ → g(v_{k})),  (5.2)
c(G, v_{0} → v_{1} → ⋯ → v_{k}) = c(G, g(v_{0}) → g(v_{1}) → ⋯ → g(v_{k})).  (5.3)

Proof. Applying g to both vertices of each edge of a walk from v_{0} coming successively through v_{1}, …, v_{k−1} to v_{k}, we get a walk from g(v_{0}) coming succesively through g(v_{1}), …, g(v_{k−1}) to g(v_{k}). Applying g^{−1} to both vertices of each edge of a walk from g(v_{0}) to g(v_{k}), we get a walk from v_{0} to v_{k}. Since these operations are inverse, we get a bijection between the corresponding sets.

Definition 5.3. For elements g_{1}, …, g_{k} ∈ Γ of a (weighted) homogeneous graph G = (Γ, H, …) denote

c_{n}(G, g_{1}, …, g_{k}) = c_{n}(G, H → g_{1}H → g_{1}g_{2}H → ⋯ → g_{1} … g_{k}H),  (5.4)
c(G, g_{1}, …, g_{k}) = c(G, H → g_{1}H → g_{1}g_{2}H → ⋯ → g_{1} … g_{k}H).  (5.5)

Lemma 5.4. For vertices g_{0}H, g_{1}H, …, g_{k}H of a (weighted) homogeneous graph G = (Γ, H, …)

c_{n}(G, g_{0}H → g_{1}H → ⋯ → g_{k}H) = c_{n}(G, g_{0}^{−1}g_{1}, g_{1}^{−1}g_{2}, …, g_{k−1}^{−1}g_{k}),  (5.6)
c(G, g_{0}H → g_{1}H → ⋯ → g_{k}H) = c(G, g_{0}^{−1}g_{1}, g_{1}^{−1}g_{2}, …, g_{k−1}^{−1}g_{k}).  (5.7)

Proof. It follows from Lemma 5.2 with v_{i} = g_{0}^{−1}g_{i}H and g = g_{0}.

Theorem 5.5. Let G = (Γ, H, …) and F be a fundamental domain of the actions of some subgroup of Stab H = {α ∈ Aut G : α(H) = H} on V (G) = Γ/H. Then

c(G, g_{1}, …, g_{k}) = c(G, |g_{1}|, …, |g_{k}|),  (5.8)

where |g| denotes an element of Γ such that |g|H ∈ F and |g|H = α_{g}(gH) for an automorphism α_{g} from the given subgroup of Stab H.

Proof. For each g ∈ Γ, fix α_{g} satisfying the condition above. For each walk from H coming successively through g_{1}H, …, g_{1} … g_{k−1}H to g_{1} … g_{k}H we can construct a walk from H coming successively through |g_{1}|, …, |g_{1}| … |g_{k−1}|H to |g_{1}| … |g_{k}|H. Walking from H to |g_{1}|H, first we go along the image under α_{g_{1}} of the initial part of the given walk to the first meeting of g_{1}H. Note that we’ll meet |g_{1}|H only at the end of this part of a walk, because α_{g_{1}} is an automorphism. Then we successively transform the part of the given walk from g_{1} … g_{i−1} to the first (new) meeting of g_{1} … g_{i}H into its image under |g_{1}| … |g_{i−1}|α_{g_{i}}. Again we’ll meet |g_{1}| … |g_{i}| only at the end, because we use an automorphism. Conversely, for each walk from H to |g_{1}| … |g_{k}|H coming succesively through |g_{1}|, …, |g_{1}| … |g_{k−1}|H we can construct a walk of the given type by inverse automorphisms of the corresponding parts. So, we have a bijection between the considered sets of walks.

Theorem 5.6. If in the conditions of Theorem 5.5 for any f_{1}, f_{2} ∈ F each walk from H to f_{1}f_{2}H comes through f_{1}H, then

c(G, g_{1}, …, g_{k}) = c(G, |g_{1}| … |g_{k}|)  (5.9)

Proof. For any f ∈ F, each walk from fH to ff_{1}f_{2}H comes through ff_{1}H, because multiplication on f is an automorphism of G. It means that each walk from H to |g_{1}| … |g_{k}|H comes succesively through g_{1}H, …, g_{1} … g_{k−1}H. Therefore

c(G, |g_{1}|, …, |g_{k}|) = c(G, |g_{1}| … |g_{k}|).  (5.10)

Using Theorem 5.5, we get (5.9).

6 Coverings and semicoverings

Definition 6.1. We’ll say that a (weighted) graph morphism π : G_{1} → G_{2} is a covering, iff it is a surjective local isomorphism, i. e. for each vertex v ∈ G_{2} there is a vertex u ∈ G_{1} such that

v = π(u),  (6.1)

and each vertex u ∈ G_{1} satisfying (6.1) has the same count ( and weights) of both incoming and outcoming edges starting or ending in u as the edges starting and ending in v.

Theorem 6.2. Let π : G_{1} → G_{2} be a covering and π(u_{1}) = u, π(v_{1}) = v for some vertices of G_{1} and G_{2}. Then

c(G_{2}, u → v) = ∑_{v_{j}∈π^{−1}(v)} c(G_{1}, u_{1} → v_{j}) = ∑_{u_{i}∈π^{−1}(u)} c(G_{1}, u_{i} → v_{1}).  (6.2)

Proof. π can’t paste together edges starting or ending in the same vertex of G_{1}, because it is a local isomorphism. It means that distinct walks on G_{1} projects under π in distinct walks on G_{2}. Conversely, for each walk from u to v on G_{2}, choosing for the first edge some edge of G_{1} starting in u_{1} and projecting onto the given edge and then step by step choosing for each sequential edge of the walk on G_{2} some edge of G_{1} starting in the end of the edge of G_{1} constructed on the previous step and projecting in the considered edge, we get a walk on G_{1} from u_{1} to some vertex v_{i} projecting onto v. Therefore, we have a bijection between the set of walks on G_{2} from u to v and the set of walks on G_{1} from u_{1} to vertices from π^{−1}(v) and the first equality in (6.2) is proven. The equality between the first and the last items of (6.2) can be proven analogously, or it follows from the proven first equality by changing the directions of all edges.

Definition 6.3. For a graph G, denote |G| the undirected graph with the same vertices as G, obtained from G by saving all its undirected edges and a replacement of all directed edges by undirected ones having the same vertices. Also, for a graph morphism α : G_{1} → G_{2} we denote |α| : |G_{1}| → |G_{2}| a morphism that is the same as α on vertices and undirected edges of G_{1} and transfers an edge of |G_{1}| obtained by a replacement of a directed edge e of G_{1} to the edge of |G_{2}| obtained by a replacement of the directed edge α(e).

Lemma 6.4. |.| is a functor from the category of graphs to the category of undirected graphs.

Proof. It is clear.

Lemma 6.5. The morphism |α| is a covering iff α is a covering.

Proof. One can easily check that both conditions, of a surjectivity and of being a local isomorphism, are true or not simultaneously for α and |α|.

Definition 6.6. We’ll call a graph G connected iff |G| is connected.

Theorem 6.7. Let G_{1} be a connected graph and π : G_{1} → G_{2} be a covering. Then G_{2} is connected as well and either the sets π^{−1}(v) are infinite for each vertex v ∈ G_{2}, or all of them are finite and contain an equal number of elements.

Proof. Morphism π is surjective and the image of a morphism of a connected graph is connected, so G_{2} is connected. By Lemma 6.5, we can suppose that the graphs G_{1} and G_{2} are undirected, or replace them by |G_{1}| and |G_{2}| otherwise. Now, if the set π^{−1}u is finite and contains m_{u} > 0 elements for some u ∈ G_{2}, then for any v ∈ G_{2} we obtain from Theorem 6.2 that

∑_{u_{i}∈π^{−1}(u)} ∑_{v_{j}∈π^{−1}(v)} c(G_{1}, u_{i} → v_{j}) = m_{u} c(G_{2}, u → v).  (6.3)

All coefficients of the series in (6.3) are nonnegative if we consider regular walks, not weighted, therefore we can change the order of summation:

∑_{u_{i}∈π^{−1}(u)} ∑_{v_{j}∈π^{−1}(v)} c(G_{1}, u_{i} → v_{j}) = ∑_{v_{j}∈π^{−1}(v)} ∑_{u_{i}∈π^{−1}(u)} c(G_{1}, u_{i} → v_{j}) = m_{v} c(G_{2}, u → v), (6.4)

where m_{v} denotes the number of elements of π^{−1}(v), that must be finite to ensure the converges of the series, because

c(G_{2}, u → v) ≠ 0  (6.5)

since G_{2} is connected. Compare (6.3) and (6.4), we get

m_{u} = m_{v}.  (6.6)

Corollary 6.8. Let π : G_{1} → G_{2} be a covering. Then for each connected component G of G_{1}, the subgraph π(G) ⊆ G_{2} is a connected component of G_{2} and either the sets π^{−1}(v) ∩ G are infinite for each vertex v ∈ π(G), or all of them are finite and contain an equal number of elements.

Proof. For each edge of G_{2} starting or ending in a vertex v ∈ π(G), we can find an edge of G projecting onto it, because π is a local isomorphism. It means that π(G) is a connected component of G_{2}. The other follows from Theorem 6.7.

Definition 6.9. We’ll say that a covering π : G_{1} → G_{2} is infinite-sheeted if for each vertex v ∈ G_{2} the set π^{−1}(v) is infinite, or j-sheeted if for each vertex v ∈ G_{2} the set π^{−1}(v) contains exactly j elements.

Lemma 6.10. Let Γ be a group and H ⊆ H_{1} ⊆ G be their subgroups. Then the morphism

\begin{matrix}π : (Γ, H, (w_{1})g_{1}, …, (w_{d})g_{d}) & → (Γ, H_{1}, (w_{1})g_{1}, …, (w_{d})g_{d}), \\ gH ↦ gH_{1}, (gH, gg_{k}H) & ↦ (gH_{1}, gg_{k}H_{1}) \end{matrix}  (6.7)

is an (H_{1} : H)-sheeted covering.

Proof. First we have to check that (6.7) defines a (weighted) graph morphism. In fact, gH = fH iff f = gh for some h ∈ H ⊆ H_{1}, hence gH_{1} = fH_{1} as well. Thus, π is a (weighted) graph morphism and it is a local isomorphism and surjective by its construction, so it is a covering. Cosets projected onto gH_{1} are ghH with h ∈ H_{1}. There are exactly (H_{1} : H) cosets of that type.

Corollary 6.11. Let G_{1} = (Γ, H, (w_{1})g_{1}, …, (w_{d})g_{d}), G_{2} = (Γ, H_{1}, (w_{1})g_{1}, …, (w_{d})g_{d}), with H ⊆ H_{1} and π : G_{1} → G_{2} be a covering, defined in (6.7). Then

c(G_{2}, g) = ∑_{hH∈H_{1}/H} c(G_{1}, gh),  (6.8)

and, in particular, if H = {1}, then

c(G_{2}, g) = ∑_{h∈H_{1}} c(G_{1}, gh).  (6.9)

Proof. After noticing that

π^{−1}(gH_{1}) = {ghH : hH ∈ H_{1}/H},  (6.10)

it follows from Lemma 6.10 and Theorem 6.2.

Definition 6.12. Let G_{1} and G_{2} be weighted graphs. We’ll say that a map π : V (G_{1}) → V (G_{2}) is a left semicovering, iff it is surjective and for any vertices u, v ∈ V (G_{2}), u_{1} ∈ V (G_{1}) such that u = π(u_{1}), we have

W (G_{2})_{uv} = ∑_{v_{j}∈π^{−1}(v)} W (G_{1})_{u_{1}v_{j}}.  (6.11)

We’ll say that a map π : V (G_{1}) → V (G_{2}) is a right semicovering, iff it is surjective and for any vertices u, v ∈ V (G_{2}), v_{1} ∈ V (G_{1}) such that v = π(v_{1}), we have

W (G_{2})_{uv} = ∑_{u_{i}∈π^{−1}(u)} W (G_{1})_{u_{i}v_{1}}.  (6.12)

We’ll call a map π : V (G_{1}) → V (G_{2}) a weak covering, iff it is both left and right semicovering.

Definition 6.13. Let G_{1} and G_{2} be graphs. We’ll say that a map π : V (G_{1}) → V (G_{2}) is a left semicovering, a right semicovering, or a weak covering if it is a left semicovering, a right semicovering, or a weak covering, correspondingly, of weighted graphs obtained from G_{1} and G_{2} by choosing Z = ℤ and w ≡ 1.

Note that left and right semicoverings as well as a weak covering, are not (weighted) graph morphisms.

Lemma 6.14. For a covering π : G_{1} → G_{2}, its vertex map π_{V} : V (G_{1}) → V (G_{2}) is a weak covering.

Proof. π_{V} is surjective, because π is surjective. Let u, v ∈ V (G_{2}) and u_{1}, v_{1} ∈ V (G_{1}) be vertices such that

π_{V} (u_{1}) = u, π_{V} (v_{1}) = v.  (6.13)

For each edge e from u to v there is exactly one edge e_{1} from u_{1} such that e = π_{E}(e_{1}) and it has the same weight as e, because π is a local isomorphism. For each edge e_{1} from u to a vertex v_{i} ∈ π^{−1}(v), the edge π(e_{1}) is an edge from u to v. Hence, we have the same count of edges from u to v and from u to π^{−1}(v) and they have the same weights. (6.11) follows from that. We can check (6.12) analogously, or it follows from (6.11) by changing the directions of all edges.

Theorem 6.15. Let G_{1} and G_{2} be (weighted) graphs and let π : V (G_{1}) → V (G_{2}) be a map and π(u_{1}) = u, π(v_{1}) = v for some vertices of G_{1} and G_{2}. If π is a left semicovering, then

c(G_{2}, u → v) = ∑_{v_{j}∈π^{−1}(v)} c(G_{1}, u_{1} → v_{j}).  (6.14)

If π is a right semicovering, then

c(G_{2}, u → v) = ∑_{u_{i}∈π^{−1}(u)} c(G_{1}, u_{i} → v_{1}).  (6.15)

If π is a weak covering, then both (6.14) and (6.15) are true.

Proof. Let graphs be weighted and π be a left semicovering. We’ll prove that

c_{n}(G_{2}, u → v) = ∑_{v_{j}∈π^{−1}(v)} c_{n}(G_{1}, u_{1} → v_{j})  (6.16)

is true for all n, by induction on n. For n = 0, if u ≠ v, then u_{1} ≠ v_{j} for all v_{j} ∈ π^{−1}(v) and both sides of (6.16) are 0; and if u = v,then u_{1} ∈ π^{−1}(v) and both sides of (6.16) are equal to 1. For n = 1, (6.16) is equivalent to (6.11), because

c_{1}(G, u → v) = W (G)_{uv}  (6.17)

for any G, u and v. Now let (6.16) be true for some n ≥ 1 for all the correct data. By Definition 2.6,

c_{n+1}(G, u → v) = ∑_{x∈V (G)} c_{n}(G, u → x)c_{1}(G, x → v).  (6.18)

for any G, u, v and n ≥ 0. For G = G_{2}, substituting (6.16) into the right hand side of (6.18), we get

c_{n+1}(G_{2}, u → v) = ∑_{x∈V (G_{2})} ∑_{x_{i}∈π^{−1}(x)} c_{n}(G_{1}, u_{1} → x_{i}) ∑_{v_{j}∈π^{−1}(v)} c_{1}(G_{1}, x_{i} → v_{j}) =

∑_{x_{i}∈V (G_{1})} c_{n}(G_{1}, u_{1} → x_{i}) ∑_{v_{j}∈π^{−1}(v)} c_{1}(G_{1}, x_{i} → v_{j}) =  (6.19)

∑_{v_{j}∈π^{−1}(v)} ∑_{x_{i}∈V (G_{1})} c_{n}(G_{1}, u_{1} → x_{i})c_{1}(G_{1}, x_{i} → v_{j}) = ∑_{v_{j}∈π^{−1}(v)} c_{n+1}(G_{1}, u_{1} → v_{j}).

By induction, (6.16) is true for all n, that is equivalent to (6.14). If π is a right semicovering, we can prove (6.15) analogously, or it follows from (6.14) by changing the directions of all edges. If π is a weak covering, it is both left and right covering, so both (6.14) and (6.15) are true. By Definition 6.13, we can consider weight function w ≡ 1 ∈ ℤ for nonweighted graphs.

Lemma 6.16. If G_{1} is a positive weighted graph, G_{1} and G_{2} are both either directed or undirected graphs and π : V (G_{1}) → V (G_{2}) is either a left semicovering, or a right semicovering, or a weak covering, then there is such map π_{E} : E(G_{1}) → E(G_{2}) that the pair (π, π_{E}) is a graph morphism from G_{1} to G_{2}.

Proof. Let u = π(u_{1}) and v = π(v_{1}). For each edge e_{1} ∈ E(G_{1}) from u_{1} to v_{1} we have

W_{uv} = W_{u_{1}v_{1}} + ⋯ = w(e_{1}) + ⋯ > 0.  (6.20)

It means that there is an edge e from u to v and we can put π_{E}(e_{1}) = e.

Note that we constructed only a graph morphism, not a weighted graph morphism. It is possible that the weighted graph morphism continuing a semicovering, or a weak covering, doesn’t exist.

Lemma 6.17. The map π : V (|G_{1}|) → V (|G_{2}|) is a left semicovering, a right semicovering, or a weak covering, iff it is a left semicovering, a right semicovering, or a weak covering, correspondingly, considered as a map π : V (G_{1}) → V (G_{2}).

Proof. Weight matrix elements are the same for G and |G| and Definition 6.12 depends only on the matrix elements.

Corollary 6.18. If G_{1} is a connected positive weighted graph and π : V (G_{1}) → G_{2} is either a left semicovering, or a right semicovering, or a weak covering, then G_{2} is a connected weighted graph.

Proof. By Lemma 6.17, we can replace G_{1} and G_{2} by undirected graphs |G_{1}| and |G_{2}|. By Lemma 6.16, the map π can be continued to a graph morphism from |G_{1}| to |G_{2}|. Now, π is surjective and the image of a connected graph under a graph morphism is connected.

Corollary 6.19. If G_{1} is a positive weighted graph, G_{2} is a reduced weighted graph and π : V (G_{1}) → V (G_{2}) is either a left semicovering, or a right semicovering, or a weak covering, then G_{2} is a positive weighted graph.

Proof. If G_{2} is reduced, then the weights of its edges coincide with the corresponding matrix elements of its weight matrix and by Definition 6.12 they are sums of positive elements, hence positive.

Corollary 6.20. If G_{1} is a positive weighted graph, G_{2} is a reduced weighted graph and π : V (G_{1}) → V (G_{2}) is a weak covering, then for each connected component G of G_{1}, the complete subgraph with the set of vertices π(V (G)) ⊆ V (G_{2}) is a connected component of G_{2}.

Proof. Let u_{1} ∈ G and u = π(u_{1}). For each edge from u, we can find an edge from u_{1} projecting onto it, because π is a left semicovering and the corresponding matrix element of the weight matrix of G_{2} is nonzero. End of the edge starting in u_{1}, lies in G, because G is a connected component. Hence, the projection of this end lies in π(G). Analogously for edges ending in u we can prove that they start in π(G), using that π is a right semicovering.

Theorem 6.21. Let G_{1} be a connected positive weighted graph and π : V (G_{1}) → V (G_{2}) be a weak covering. Then G_{2} is a connected weighted graph as well and either the sets π^{−1}(v) are infinite for each vertex v ∈ π(G), or all of them are finite and contain an equal number of elements.

Proof. The connectivity of G_{2} is already stated in Corollary 6.18. The other proof is the same as for Theorem 6.7, except that we consider weighted walks now and we need a new explanation why we can change the order of summation in (6.3). The point is that the sum have only a finite number of coefficients at t^{n} for each n. Also, instead of (6.5) we need

c(G_{2}, u → v) > 0  (6.21)

that is true because c(G_{2}, u → v) is a sum of positive summands.

Corollary 6.22. Let G_{1} be a positive weighted graph, and π : V (G_{1}) → V (G_{2}) be a weak covering. Then for each connected component G of G_{1} either the sets π^{−1}(v) ∩ G are infinite for each vertex v ∈ π(G), or all of them are finite and contain an equal number of elements.

Proof. The restriction π|_{G} : V (G) → π(G) is a weak covering from G to the complete subgraph of G_{2} with the set of vertices π(G) and we can use Theorem 6.21.

Definition 6.23. Denote K_{1}(m) = (0, 0, m · (0)) the graph with one vertex and one loop of weight m.

Theorem 6.24. c(K_{1}(m), 0) = e^{mt} .

Proof. The weight matrix of K_{1}(m) is (m) and we can use Lemma 2.7.

Corollary 6.25. If a weighted graph G_{1} is obtained from a weighted graph G by adding loops of weight m to all the vertices, then

c(G_{1}, u → v) = e^{mt}c(G, u → v)  (6.22)

for any their vertices u, v.

Proof. G_{1} is isomorphic to G × K_{1}^{m} and we can use Theorems 2.2 and 6.24.

Definition 6.26. We’ll call a weighted graph G left semiregular of weight m iff for each vertex u

∑_{v∈V (G)} W (G)_{uv} = m.  (6.23)

right semiregular of weight m iff for each vertex v

∑_{u∈V (G)} W (G)_{uv} = m,  (6.24)

and weak regular of weight m if it is both left semiregular of weight m and right semiregular of weight m.

Theorem 6.27. A weighted graph G is left semiregular of weight m, or right semiregular of weight m, or weak regular of weight m iff the constant map π : V (G) → V (K_{1}(m)) is a left semicovering, or a right semicovering, or a weak covering, correspondingly.

Proof. It is enough to compare Definitions 6.12 and 6.26.

Corollary 6.28. For a left semiregular graph G of degree m and a vertex u ∈ V (G),

∑_{v∈V (G)} c(G, u → v) = e^{mt},  (6.25)
∑_{v∈V (G)} c_{n}(G, u → v) = m^{n}.  (6.26)

For a right semiregular graph G of degree m and a vertex v ∈ V (G),

∑_{u∈V (G)} c(G, u → v) = e^{mt},  (6.27)
∑_{u∈V (G)} c_{n}(G, u → v) = m^{n}.  (6.28)

For a weak regular graph G of degree m all the formulas (6.25 − 6.28) are true for any vertices u, v ∈ V (G).

Proof. It is an immediate corollary of Theorems 6.15, 6.24 and 6.27.

7 Symmetric powers and bipowers

Definition 7.1. For a (weighted) graph G with linearly ordered set of vertices V (G), denote S^{n}(G) a directed (weighted) graph with the set of vertices

V (S^{n}G) = S^{n}V (G) = {(v_{1}, …, v_{n}) ∈ V (G)^{n} | v_{1} ≤ ⋯ ≤ v_{n}}  (7.1)

and edges defined as follows. For i = 1, …, n denote Pr_{i} : V (S^{n}G) → V (S^{n−1}G) the projection obtained by the erasing of the vertices v_{i} standing on the i-th place of the sequence (7.1). The directed edges from A to B correspond to pairs (i ∈ {1, …, n}, e ∈ E(G)) such that there is j such that P r_{i}(A) = P r_{j}(B) and e is an edge from v_{i}(A) to v_{j}(B) where v_{i} denotes the vertex of G standing on the i-th place of the sequence (7.1); in which case, for weighted graphs, the corresponding edge from A to B has the same weight as e.

Lemma 7.2. For a (weighted) graph G with linearly ordered set of vertices, mapping

V (G^{n}) → V (S^{n}G), (v_{1}, …, v_{n}) ↦ (v_{1}, …, v_{n})^{σ}  (7.2)

where the permutation σ rearranges (v_{1}, …, v_{n}) in increasing order, is a left semicovering.

Proof. It follows directly from Definitions 7.1 and 6.12.

Theorem 7.3. For a (weighted) graph G with linearly ordered set of vertices,

c(S^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = per(c(G, u_{i} → v_{j}))_{1≤i,j≤n},  (7.3)

i. e. the permanent of the matrix with pointed out elements.

Proof. It follows from Lemma 7.2 and Theorems 6.15 and 2.2, that

c(S^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = ∑_{σ∈S_{n}} c(G^{n}, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})^{σ})  (7.4)
= ∑_{σ∈S_{n}} c(G, u_{1} → v_{σ^{−1}(1)}) … c(G, u_{n} → v_{σ^{−1}(n)}) = per(c(G, u_{i} → v_{j}))_{1≤i,j≤n}.  (7.5)

Definition 7.4. For a (weighted) directed graph G with linearly ordered set of vertices V (G), denote S_{2}^{n}(G) a directed (weighted) graph with the set of vertices

V (S_{2}^{n}G) = S^{n}V (G) = {(v_{1}, …, v_{n}) ∈ V (G)^{n} | v_{1} ≤ ⋯ ≤ v_{n}}  (7.6)

and edges defined as follows. The directed edges from A to B correspond to the pairs (σ ∈ S_{n}, (e_{1}, …, e_{n}) ∈ (E(G))^{n}) such that for i from 1 to n, e_{i} is an edge from v_{i}(A) to v_{σ(j)}(B) where v_{i} denotes the vertex of G standing on the i-th place of the sequence (7.6), in which case, for weighted graphs, the corresponding edge from A to B has the weight e_{1} … e_{n}.

Lemma 7.5. For a (weighted) directed graph G with linearly ordered set of vertices, mapping

V (\underbrace{G ×_{2} ⋯ ×_{2} G}_{n times}) → V (S_{2}^{n}G), (v_{1}, …, v_{n}) ↦ (v_{1}, …, v_{n})^{σ}  (7.7)

where the permutation σ rearranges (v_{1}, …, v_{n}) in increasing order, is a left semicovering.

Proof. It follows directly from Definitions 7.4 and 6.12.

Theorem 7.6. For a (weighted) directed graph G with linearly ordered set of vertices,

c(S_{2}^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = per^{∘}(c(G, u_{i} → v_{j}))_{1≤i,j≤n},  (7.8)

i. e. the permanent of the matrix with pointed out elements multiplying coefficient-wise according to Definition 3.5.

Proof. It follows from Lemma 7.5 and Theorems 6.15 and 3.6, the same as in the proof of Theorem 7.6.

Corollary 7.7. For a (weighted) directed graph G with linearly ordered set of vertices,

c_{k}(S_{2}^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = per(c_{k}(G, u_{i} → v_{j}))_{1≤i,j≤n},  (7.9)

i. e. the permanent of the matrix with pointed out elements.

Proof. It follows directly from Theorem 7.6 and Definition 3.5.

Definition 7.8. For a bipartite graph G, we’ll say that a vertex (v_{1}, …, v_{n}) ∈ V (S_{2}^{n}G) is even if the sum of parities (0, 1) of v_{1}, …, v_{n} is even. If the vertex is not even, we’ll say that it is odd.

Lemma 7.9. Let G be a bipartite directed graph. For even n, each edge of S_{2}^{n}G connects vertices of the same parity, i. e. either both even, or both odd. For odd n, each edge of S_{2}^{n}G connects vertices of alternate parities, i. e. one of them must be even and another odd.

Proof. For an edge from (u_{1}, …, u_{n}) to (v_{1}, …, v_{n}), the sum of parities of all the u_{i} and v_{i} equals n, therefore it is even for even n and odd for odd n.

Definition 7.10. For a bipartite directed graph G and even n denote S_{0}^{n}G and S_{1}^{n}G the complete subgraphs of S_{2}^{n}G, spanned by all the even vertices, or the odd, respectively.

Corollary 7.11. For even n, we can use the formulas (7.8) and (7.9) for S_{0}^{n}G and S_{1}^{n}G instead of S_{2}^{n}G, as well.

Proof. It follows from Theorem 7.6, Corollary 7.7 and Lemma 7.9.

8 Schur operations and bioperations

We’ll fix here for each Young diagram of a partition λ, a standard tableau T of shape λ filling first the first row, then the second and so on.

Definition 8.1. For a (weighted) graph G with linearly ordered set of vertices V (G) and for a partition λ denote S^{λ}(G) a directed (weighted) graph vertices of which are tableaux of shape λ with elements from V (G) increasing in each column and not decreasing in each row, and edges defined as follows. For a triple consisting of a vertex u ∈ V (S^{λ}G), box i of the Young diagram of shape λ and an edge e from the vertex u_{i} ∈ V (G) located on the i-th place of the Young diagram, to a vertex v ∈ V (G), denote (u, i, e) the tableau obtained by substituting v instead of u_{i} in the i-th box of u. It is not a tableau with increasing columns and non-decreasing rows, in general. Let

Y_{T} (u, i, e) = ∑_{x∈V (S^{λ}G)} γ_{x}Y_{T} (x)  (8.1)

where Y_{T} is the Young symmetrizer corresponding to the standard tableau T fixed in the beginning of this section. γ_{x} ∈ ℤ are some integer coefficients. We suppose that for each such triple (u, i, v) and for each non-zero coefficient γ_{x} in (8.1) we have an edge from u to x of weight γ_{x}w(e) where w(e) is the weight of e.

Theorem 8.2. For a (weighted) graph G with linearly ordered set of vertices and for a partition λ,

c(S^{λ}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = imm_{λ}(c(G, u_{i} → v_{j}))_{1≤i,j≤n},  (8.2)

i. e. the immanent of the matrix with pointed out elements, where

imm_{λ}(a_{ij})_{1≤i,j≤n} = ∑_{σ∈S_{n}} χ_{λ}a_{1σ(1)} … a_{nσ(n)}  (8.3)

and χ_{λ} denotes the character of symmetric group S_{n} corresponding to the partition λ.

Proof. It follows from the commutativity of the diagram

Mat_{V (G)}(r) ⟶^{exp} Mat_{V (G)}(r{{t}})
S^{λ}↓ ↓^{S_{∗}^{λ}}
Mat_{V (S^{λ}G)}(r) ⟶^{exp} Mat_{V (S^{λ}G)}(r{{t}})

(8.4)

for our ring of weights r, where exp : W (G) ↦ C(G) = e^{W (G)t}, S^{λ}(W (G)) = W (S^{λ}G) and S_{∗}^{λ} is defined according to the right hand side of (8.2). The commutativity of this diagram for r follows from the commutativity of this diagram for r = ℤ which follows from the commutativity of this diagram for r = ℝ in which case it follows from the well-known correspondence between the representations of Lie groups and algebras. Also, S^{λ}, S_{∗}^{λ} and exp can be defined as univeral functors for appropriate categories. Combining the universal properties, we obtain a unique universal diagonal functor for (8.4).

Note that Theorem 7.3 is a particular case of Theorem 8.2 for λ = n.

Definition 8.3. For a (weighted) graph G with linearly ordered set of vertices V (G) and for a partition λ denote S_{2}^{λ}(G) a directed (weighted) graph vertices of which are tableaux of shape λ with elements from V (G) increasing in each column and not decreasing in each row, and edges defined as follows. For a pair consisting of a vertex u ∈ V (S^{λ}G) and tableau e of shape λ filled by the edges of G such that for each box i the edge e_{i} is an edge from the vertex u_{i} ∈ V (G) located in the i-th box of u to a vertex v_{i} ∈ V (G), denote (e) the tableau obtained by substituting v_{i} instead of u_{i} in the i-th box of u. It is not a tableau with increasing columns and non-decreasing rows, in general. Let

Y_{T} (e) = ∑_{x∈V (S^{λ}G)} γ_{x}Y_{T} (x)  (8.5)

where Y_{T} is the Young symmetrizer corresponding to the standard tableau T fixed in the beginning of this section. γ_{x} ∈ ℤ are some integer coefficients. We suppose that for each an edge tableau (e) and for each non-zero coefficient γ_{x} in (8.1) we have an edge from u to x of weight γ_{x}w(e_{1}) … w(e_{n}) where w(e_{i}) is the weight of e_{i}.

Theorem 8.4. For a (weighted) graph G with linearly ordered set of vertices and for a partition λ,

c(S_{2}^{λ}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = imm_{λ}^{∘}(c(G, u_{i} → v_{j}))_{1≤i,j≤n},  (8.6)

i. e. the immanent of the matrix with pointed out elements multiplying coefficient-wise according to Definition 3.5, i. e.

imm_{λ}^{∘}(a_{ij})_{1≤i,j≤n} = ∑_{σ∈S_{n}} χ_{λ}a_{1σ(1)} ∘ ⋯ ∘ a_{nσ(n)}  (8.7)

and χ_{λ} denotes the character of symmetric group S_{n} corresponding to the partition λ.

Proof. Analogously the proof of Theorem 8.2, it follows from the commutativity of the diagram

Mat_{V (G)}(r) ⟶^{exp} Mat_{V (G)}(r{{t}})
S_{2}^{λ}↓ ↓^{S_{∘}^{λ}}
Mat_{V (S_{2}^{λ}G)}(r) ⟶^{exp} Mat_{V (S_{2}^{λ}G)}(r{{t}})

(8.8)

for our ring of weights r, where exp : W (G) ↦ C(G) = e^{W (G)t}, S^{λ}(W (G)) = W (S^{λ}G) and S_{∘}^{λ} is defined according to the right hand side of (8.2). Again, S_{2}^{λ}, S_{∘}^{λ} and exp can be defined as univeral functors for appropriate categories. Combining the universal properties, we obtain a unique universal diagonal functor for (8.8).

Corollary 8.5. For a (weighted) graph G with linearly ordered set of vertices and for a partition λ,

c_{k}(S_{2}^{λ}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = imm_{λ}(c(G, u_{i} → v_{j}))_{1≤i,j≤n},  (8.9)

i. e. the immanent of the matrix with pointed out elements.

Proof. It follows directly from Theorem 8.4 and Definition 3.5.

Note that Theorem 7.3 and Corollary 7.3 are the particular cases of Theorem 8.4 and Corollary 8.5 for λ = n.

9 Exterior powers and bipowers

Definition 9.1. For a (weighted) graph G with linearly ordered set of vertices V (G), denote Λ^{n}(G) a directed (weighted) graph with the set of vertices

V (Λ^{n}G) = Λ^{n}V (G) = {(v_{1}, …, v_{n}) ∈ V (G)^{n} | v_{1} < ⋯ < v_{n}}  (9.1)

and edges defined as follows. For i = 1, …, n denote Pr_{i} : V (Λ^{n}G) → V (Λ^{n−1}G) the projection obtained by the erasing of the vertices v_{i} standing on the i-th place of the sequence (9.1). The directed edges from A to B correspond to pairs (i ∈ {1, …, n}, e ∈ E(G)) such that there is j such that P r_{i}(A) = P r_{j}(B) and e is an edge from v_{i}(A) to v_{j}(B) where v_{i} denotes the vertex of G standing on the i-th place of the sequence (9.1); in which case, for weighted graphs, the corresponding edge from A to B has the weight (−1)^{j−i}w(e) where w(e) is the weight of e.

Theorem 9.2. For a (weighted) graph G with linearly ordered set of vertices,

c(Λ^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = det(c(G, u_{i} → v_{j}))_{1≤i,j≤n}.  (9.2)

Proof. It is a particular case of Theorem 8.2 for λ = 1^{n}.

Definition 9.3. For a (weighted) directed graph G with linearly ordered set of vertices V (G), denote Λ_{2}^{n}(G) a directed (weighted) graph with the set of vertices

V (Λ_{2}^{n}G) = Λ^{n}V (G) = {(v_{1}, …, v_{n}) ∈ V (G)^{n} | v_{1} ≤ ⋯ ≤ v_{n}}  (9.3)

and edges defined as follows. The directed edges from A to B correspond to the pairs (σ ∈ S_{n}, (e_{1}, …, e_{n}) ∈ (E(G))^{n}) such that for i from 1 to n, e_{i} is an edge from v_{i}(A) to v_{σ(j)}(B) where v_{i} denotes the vertex of G standing on the i-th place of the sequence (9.3), in which case, for weighted graphs, the corresponding edge from A to B has the weight sgn(σ)e_{1} … e_{n}.

Theorem 9.4. For a (weighted) directed graph G with linearly ordered set of vertices,

c(Λ_{2}^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = det^{∘}(c(G, u_{i} → v_{j}))_{1≤i,j≤n},  (9.4)

i. e. the determinant of the matrix with pointed out elements multiplying coefficient-wise according to Definition 3.5.

Proof. It is a particular case of Theorem 8.4 for λ = 1^{n}.

Corollary 9.5. For a (weighted) directed graph G with linearly ordered set of vertices,

c_{k}(Λ_{2}^{n}G, (u_{1}, …, u_{n}) → (v_{1}, …, v_{n})) = det(c_{k}(G, u_{i} → v_{j}))_{1≤i,j≤n},  (9.5)

i. e. the determinant of the matrix with pointed out elements.

Proof. It follows directly from Theorem 9.4 and Definition 3.5.

Definition 9.6. For a bipartite graph G, we’ll say that a vertex (v_{1}, …, v_{n}) ∈ V (Λ_{2}^{n}G) is even if the sum of parities (0, 1) of v_{1}, …, v_{n} is even. If the vertex is not even, we’ll say that it is odd.

Lemma 9.7. Let G be a bipartite directed graph. For even n, each edge of Λ_{2}^{n}G connects vertices of the same parity, i. e. either both even, or both odd. For odd n, each edge of Λ_{2}^{n}G connects vertices of alternate parities, i. e. one of them must be even and another odd.

Proof. For an edge from (u_{1}, …, u_{n}) to (v_{1}, …, v_{n}), the sum of parities of all the u_{i} and v_{i} equals n, therefore it is even for even n and odd for odd n.

Definition 9.8. For a bipartite directed graph G and even n denote Λ_{0}^{n}G and Λ_{1}^{n}G the complete subgraphs of Λ_{2}^{n}G, spanned by all the even vertices, or the odd, respectively.

Corollary 9.9. For even n, we can use the formulas (9.4) and (9.5) for Λ_{0}^{n}G and Λ_{1}^{n}G instead of Λ_{2}^{n}G, as well.

Proof. It follows from Theorem 9.4, Corollary 9.5 and Lemma 9.7.

10 Linear graphs

Definition 10.1. Denote R = (ℤ, 0, 1, −1) the graph with the set of vertices ℤ and edges connecting n and n + 1 for every n:

[figure: −5; −4; −3; −2; −1; 0; 1; 2; 3; 4; 5]

Theorem 10.2.

c_{n}(R, m) = \begin{cases}\binom{n}{\frac{n−m}{2}} & if n − m is even, \\ 0 & otherwise. \end{cases}  (10.1)

Proof. Denoting q the element of the group algebra ℤ(ℤ), corresponding to 1 ∈ ℤ (inside parentheses), we get

ℤ(ℤ) = ℤ[q, q^{−1}],  (10.2)

where q^{m} corresponds to m. Then by (4.13),

(q + q^{−1})^{n} = ∑_{m∈ℤ} c_{n}(R, m)q^{m}.  (10.3)

and we know that

(q + q^{−1})^{n} = ∑_{i=0}^{n} \binom{n}{i}q^{n−2i},  (10.4)

so

c_{n}(R, m) = \binom{n}{i},  (10.5)

where m = n − 2i, i. e. i = (n − m)/2 .

Corollary 10.3. For m ≥ 0,

c(R, ±m) = \frac{t^{m}}{m!} _{0}F_{1}(; m + 1; t^{2}) = I_{m}(2t),  (10.6)

where _{0}F_{1} is the hypergeometric function, and I_{m} is the modified Bessel function of the first kind.

Proof. It follows immediately from Theorem 10.2 and the definitions of hypergeometric functions and Bessel functions.

Corollary 10.4.

e^{(q+q^{−1})t} = ∑_{m=−∞}^{∞} q^{m}I_{|m|}(2t).  (10.7)

Proof. It follows from (4.14) and Corollary 10.3.

Definition 10.5. Denote R(a, b) = (ℤ, 0, a · 1, b · (−1)) the graph R, considered as a directed graph having for every integer n the arcs (n, n + 1) of weight a and (n + 1, n) of weight b.

Theorem 10.6.

c_{n}(R(a, b), m) = \begin{cases}\binom{n}{\frac{n−m}{2}}a^{\frac{n+m}{2}} b^{\frac{n−m}{2}} & if n − m is even, \\ 0 & otherwise. \end{cases}  (10.8)

Proof. We can repeat the proof of Theorem 10.2 with corresponding modifications. Also, we get another proof, noticing that each walk of length n from 0 to m has the same weight a^{(n+m)/2}b^{(n−m)/2} and using Theorem 10.2.

Corollary 10.7. For m ≥ 0 and ab ≠ 0,

c(R(a, b), m) = \frac{a^{m}t^{m}}{m!} _{0}F_{1}(; m + 1; abt^{2}) = a^{m/2}b^{−m/2}I_{m}(2\sqrt{ab} t),  (10.9)
c(R(a, b), −m) = \frac{b^{m}t^{m}}{m!} _{0}F_{1}(; m + 1; abt^{2}) = a^{−m/2}b^{m/2}I_{m}(2\sqrt{ab} t).  (10.10)

For ab = 0

c(R(a, b), m) = \begin{cases}a^{m}t^{m}/m! & if b = 0, m ≥ 0, \\ b^{−m}t^{−m}/(−m)! & if a = 0, m ≤ 0, \\ 0 & otherwise. \end{cases}  (10.11)

Proof. It follows from Theorem 10.6 and definitions. Corollary 10.8. For ab ≠ 0,

e^{(aq+bq^{−1})t} = ∑_{m=−∞}^{∞}(\sqrt{a/b} q)^{m}I_{|m|}(2\sqrt{ab} t).  (10.12)

Proof. The same proof as for Corollary 10.4. Or we can change in (10.7) q to \sqrt{a/b} q and t to \sqrt{ab} t. Theorem 10.9.

c_{n}(R, m_{1}, …, m_{k}) = c_{n}(R, m) = \begin{cases}\binom{n}{\frac{n−m}{2}} & if n − m is even, \\ 0 & otherwise, \end{cases}  (10.13)

where m = |m_{1}| + ⋯ + |m_{k}|.

Proof. Consider the automorphism

− : R → R, m ↦ (−m).  (10.14)

Nonnegative integers form a fundamental domain with respect to it and our result follows from Theorems 10.2 and 5.6. Corollary 10.10.

c(R, m_{1}, …, m_{k}) = I_{m}(2t),  (10.15)

where m = |m_{1}| + ⋯ + |m_{k}|.

Proof. It follows from Theorem 10.9 and Corollary 10.3. Theorem 10.11.

c_{n}(R(a, b), m_{1}, …, m_{k}) = \begin{cases}\binom{n}{\frac{n−m}{2}}a^{(n+M)/2}b^{(n−M)/2} & if n − m is even, \\ 0 & otherwise, \end{cases}  (10.16)

where m = |m_{1}| + ⋯ + |m_{k}| and M = m_{1} + ⋯ + m_{k}.

Proof. In the proof of Theorem 10.6 we noticed that each walk from 0 to M has the same weight a^{(n+M)/2}b^{(n−M)/2}. Multiplying it on the number of walks stated in Theorem 10.9, we obtain (10.16).

Corollary 10.12. For ab ≠ 0,

c(R(a, b), m_{1}, …, m_{k}) = \frac{a^{(m+M)/2}b^{(m−M)/2}t^{m}}{m!} _{0}F_{1}(; m + 1; abt^{2}) = a^{M/2}b^{−M/2}I_{m}(2\sqrt{ab} t), (10.17)

where m = |m_{1}| + ⋯ + |m_{k}| and M = m_{1} + ⋯ + m_{k}. For ab = 0

c(R(a, b), m_{1}, …, m_{k}) = \begin{cases}a^{m}t^{m}/m! & if b = 0, m_{1} ≥ 0, …, m_{k} ≥ 0, \\ b^{m}t^{m}/m! & if a = 0, m_{1} ≤ 0, …, m_{k} ≤ 0, \\ 0 & otherwise. \end{cases}  (10.18)

Proof. It follows from Theorem 10.11 and definitions. Definition 10.13. Denote P the complete subgraph of R with all nonnegative vertices:

[figure: 0; 1; 2; 3; 4; 5]

Theorem 10.14.

c_{n}(P, k → l) = \begin{cases}\binom{n}{\frac{n+k−l}{2}} − \binom{n}{\frac{n−k−l}{2} − 1} & if n + k − l is even, \\ 0 & otherwise. \end{cases}  (10.19)

Proof. Let k, l ≥ 0. Each walk from k to l along the edges of R is a walk along the edges of P, except the walks coming through −1. It means that

c_{n}(P, k → l) = c_{n}(R, k → l) − c_{n}(R, k → (−1) → l) = c_{n}(R, l − k) − c_{n}(R, −1 − k, l + 1). (10.20)

Using Theorems 10.2 and 10.9, we get (10.19).

Corollary 10.15.

c(P, k → l) = I_{|l−k|}(2t) − I_{l+k+2}(2t).  (10.21)

Proof. It follows from (10.20) and Corollary 10.10. Corollary 10.16.

c(P, 0 → m) = \frac{t^{m}}{m!} _{0}F_{1}(; m + 2; t^{2}) = (m + 1)I_{m+1}(2t)/t.  (10.22)

Proof. It follows from Corollary 10.15 and recurrent relations between Bessel functions. Or from Theorem 10.14 and the equality

\binom{n}{\frac{n−m}{2}} − \binom{n}{\frac{n−m}{2} − 1} = \frac{m + 1}{n + 1}\binom{n + 1}{\frac{n−m}{2}}.  (10.23)

Corollary 10.17.

∑_{i=k}^{l}(n − 2i)\binom{n}{i} = n (\binom{n − 1}{l} − \binom{n − 1}{k − 1}) .  (10.24)

Proof. It follows from changing n + 1 to n in (10.23), changing (n − m)/2 to i and summation. Definition 10.18. Denote P (a, b) the complete weighted subgraph of R(a, b) with the same set of vertices as P. Theorem 10.19.

c_{n}(P (a, b), k → l) = \begin{cases}(\binom{n}{\frac{n+k−l}{2}} − \binom{n}{\frac{n−k−l}{2} − 1}) a^{(n−k+l)/2}b^{(n+k−l)/2} & if n + k − l is even, \\ 0 & otherwise. \end{cases}

(10.25)

Proof. Each walk from k to l has the same weight a^{(n−k+l)/2}b^{(n+k−l)/2}. Multiplying it on the number of walks stated in Theorem 10.14, we obtain (10.25). Corollary 10.20. For ab ≠ 0,

c(P (a, b), k → l) = (I_{|l−k|}(2\sqrt{ab} t) − I_{l+k+2}(2\sqrt{ab} t))a^{(l−k)/2}b^{(k−l)/2}.  (10.26)

For ab = 0,

c(P (a, b), k → l) = \begin{cases}a^{l−k}t^{l−k}/(l − k)! & if b = 0 and k ≤ l, \\ b^{k−l}t^{k−l}/(k − l)! & if a = 0 and k ≥ l, \\ 0 & otherwise. \end{cases}  (10.27)

Proof. It follows from the weighted variant of (10.20) and Corollary 10.10. Corollary 10.21. For ab ≠ 0,

c(P (a, b), 0 → m) = \frac{a^{m}t^{m}}{m!} _{0}F_{1}(; m + 2; abt^{2}) = (m + 1)a^{m/2}b^{−m/2}I_{m+1}(2\sqrt{ab} t)/t.  (10.28)

For ab = 0,

c(P (a, b), 0 → m) = \begin{cases}a^{m}t^{m}/m! & if b = 0, \\ 1 & if a = 0 and m = 0, \\ 0 & otherwise. \end{cases}  (10.29)

Proof. It follows from Corollaries 10.15, 10.16 and 10.20.

11 Products of linear graphs

Definition 11.1. Denote R^{2} = R × R the Cartesian square of R:

[figure]

Lemma 11.2. R^{2} ≃ R ×_{0} R ≃ R ×_{1} R.

Proof. To make this evident, it is enough to rotate the picture above at 45^{∘} counterclockwise. Theorem 11.3.

c_{n}(R^{2}, (m_{1}, m_{2})) = \begin{cases}\binom{n}{\frac{n−m_{1}−m_{2}}{2}}\binom{n}{\frac{n+m_{1}−m_{2}}{2}} & if n − m_{1} − m_{2} is even, \\ 0 & otherwise. \end{cases}  (11.1)

Proof. It follows from Lemma 11.2, Theorem 3.6 and Theorem 10.2. I’ll give a direct proof as well. Consider two projections:

\begin{matrix}Pr_{1} : R^{2} → R, (m_{1}, m_{2}) ↦ (m_{1} + m_{2}), \\ Pr_{2} : R^{2} → R, (m_{1}, m_{2}) ↦ (m_{2} − m_{1}). \end{matrix}  (11.2)

They project each R^{2}-walk from 0 to (m_{1}, m_{2}) to two R-walks from 0 to (m_{1} + m_{2}) and from 0 to (m_{2} − m_{1}), correspondingly. Note that for each vertex of R^{2}, both the projections have the same parity, because

m_{1} + m_{2} ≡ m_{2} − m_{1} mod 2.  (11.3)

Conversely, each pair of vertices u, v of R, having the same parity, uniquely determines the vertex (m_{1}, m_{2}) of R^{2}, such that

Pr_{1}(m_{1}, m_{2}) = u, Pr_{2}(m_{1}, m_{2}) = v.  (11.4)

In fact,

m_{1} = \frac{u − v}{2} , m_{2} = \frac{u + v}{2} .  (11.5)

For

u′ = u ± 1, v′ = v ± 1,  (11.6)

where the signs can be the same, or different, we have

m′_{1} = m_{1}, m′_{2} = m_{2} ± 1,  (11.7)

if the signs were the same, or

m′_{1} = m_{1} ± 1, m′_{2} = m_{2},  (11.8)

if the signs were different. It means that ((m_{1}, m_{2}), (m′_{1}, m′_{2})) is an edge of R^{2}. In other words, each pair of edges of R having the same parity, uniquely determines the edge of R^{2}, the first ( and second) projection of which coincides with the first (or second, correspondingly) edge of that pair. Therefore, each pair of R-walks, from 0 to (m_{1} + m_{2}) and from 0 to (m_{2} − m_{1}), uniquely determines a R^{2}-walk from 0 to (m_{1}, m_{2}). We constructed a bijection between the set of R^{2}-walks from 0 to (m_{1}, m_{2}) and the direct product of the sets of R-walks from 0 to (m_{1} + m_{2}) and R-walks from 0 to (m_{2} − m_{1}). Now, Theorem 10.2 gives us (11.1).

Corollary 11.4. For m_{1} ≥ 0, m_{2} ≥ 0,

c(R^{2}, (±m_{1}, ±m_{2})) = I_{m_{1}}(2t)I_{m_{2}}(2t) = ∑_{i=0}^{∞} \binom{m_{1} + m_{2} + 2i}{m_{1} + i}\frac{t^{m_{1}+m_{2}+2i}}{i! (m_{1} + m_{2} + i)!}.  (11.9)

Proof. The first equality follows from Theorem 4.11 and Corollary 10.3. The equality of the first and the third item of (11.9) follows from Theorem 11.3.

Corollary 11.5. For a ≥ 0, b ≥ 0,

∑_{i=0}^{k} \binom{2k + a + b}{i i + a k − i k − i + b} = \binom{2k + a + b}{k}\binom{2k + a + b}{k + a}.  (11.10)

Proof. After noticing that

\binom{2k + a + b}{i i + a k − i k − i + b} = \binom{2k + a + b}{2i + a}\binom{2i + a}{i}\binom{2k − 2i + b}{k − i},  (11.11)

it follows from (2.4), Theorems 10.2 and 11.3 for G_{1} = G_{2} = R and

u_{1} = v_{1} = 0, v_{1} = m_{1} = a, v_{2} = m_{2} = b, n = 2k + a + b, j = 2i + a.  (11.12)

There is also another bijective proof of (11.10), without walks. Notice, that the number in the right hand side of (11.10) is equal to the number of ways of choosing two subsets containing k and k + b elements, of the set containing 2k + a + b elements. We can choose these subsets, choosing first i elements that will be their intersection, then k − i the other elements of the first set and k + b − i the other elements of the second set. It gives us exactly the sum in the left hand side of (11.10).

Consider the graph R × P (the square lattice in the upper-half plane):

[figure]

Corollary 11.6. c(R × P, (k_{1}, k_{2}) → (l_{1}, l_{2})) = I_{|l_{1}−k_{1}|}(2t)(I_{|l_{2}−k_{2}|}(2t) − I_{l_{2}+k_{2}+2}(2t)).

Proof. It follows from Theorem 2.2 and Corollaries 10.3 and 10.15. Corollary 11.7. c_{n}(R × P, (k_{1}, k_{2}) → (l_{1}, l_{2})) =

\binom{n}{\frac{n−(l_{1}−k_{1})−|l_{2}−k_{2}|}{2}}\binom{n}{\frac{n+(l_{1}−k_{1})−|l_{2}−k_{2}|}{2}} − \binom{n}{\frac{n−(l_{1}−k_{1})−(l_{2}+k_{2}+2)}{2}}\binom{n}{\frac{n+(l_{1}−k_{1})−(l_{2}+k_{2}+2)}{2}}, (11.13)

if n − (l_{1} − k_{1}) − (l_{2} − k_{2}) is even and 0 otherwise.

Proof. It follows from Theorem 11.3 and Corollaries 11.4 and 11.6. Corollary 11.8. c(R × P, (k, 0) → (l, m)) = (m + 1)I_{|l−k|}(2t)I_{m+1}(2t)/t.

Proof. It follows from Theorem 2.2 and Corollaries 10.3 and 10.16. Corollary 11.9.

c_{n}(R × P, (k, 0) → (l, m)) = \frac{m + 1}{n + 1}\binom{n + 1}{\frac{n−(l−k)−m}{2}}\binom{n + 1}{\frac{n+(l−k)−m}{2}},  (11.14)

if n − l + k − m is even and 0 otherwise.

Proof. It follows from Theorem 11.3 and Corollaries 11.4 and 11.8. Corollary 11.10.

\binom{n}{i}\binom{n}{j} − \binom{n}{i − 1}\binom{n}{j − 1} = \frac{n − i − j + 1}{n + 1}\binom{n + 1}{i}\binom{n + 1}{j}.  (11.15)

Proof. Compare Corollaries 11.7 and 11.9. Corollary 11.11.

∑_{i=k}^{l}(n − m − 2i)\binom{n}{i}\binom{n}{m + i} = n (\binom{n − 1}{l}\binom{n − 1}{m + l} − \binom{n − 1}{k − 1}\binom{n − 1}{m + k − 1}) .  (11.16)

Proof. Changing n + 1 to n in (11.15), changing j to m + i and summing from i = k to l, we get (11.16).

Analogously, we can obtain a series of similar formulas for P × P and other products of linear graphs.

12 Enumeration of plane symplectic wave graphs

Recall the definition from [1].

A plane symplectic wave graph is a graph with the vertices 1, 2, …, m, each connected component of which is a path of length ≥ 1 (i. e. it can’t be a point), edges of which can be drawn in the plane considered as two half-planes, upper and lower, glued along ℝ, such that the first edge of each connected component, {i_{1}i_{2}}, is drawn on the upper half-plane; each edge {i_{j}i_{j+1}} consequent to the edge {i_{j−1}i_{j}} drawn on one of the half-planes, is drawn on another one; the last edge of the path, {i_{l}i_{l+1}}, supposed to be drawn on the upper half-plane; we suppose also that i_{1} < i_{2} < ⋯ < i_{l+1} and edges of our plane symplectic wave graph don’t intersect.

Theorem 12.1. There exist exactly

\frac{(2k)!(2k + 2)! · 6}{k!(k + 1)!(k + 2)!(k + 3)!}  (12.1)

plane symplectic wave graphs with 2k vertices.

Proof. It was shown in [1] that there is f̃_{2k}^{0}(2) plane symplectic wave graphs with 2k vertices, where f̃_{2k}^{0}(2) is the number of balanced symplectic lattice words in the alphabet \{1, 2, \overline{1}, \overline{2}\}. which is equal c_{2k}(Λ^{2}P, (0, 1) → (0, 1)). By Theorem 9.2,

c(Λ^{2}P, (0, 1) → (0, 1)) = |\begin{matrix}c(P, 0 → 0) & c(P, 0 → 1) \\ c(P, 1 → 0) & c(P, 1 → 1) \end{matrix}| .  (12.2)

Plugging the values of c(P, i → j) given by Corollaries 10.15 and 10.16 and using Corollary 11.4, we obtain formula (12.1).

Acnowledgements. I would like to thank Fan Chung Graham, Alexandre Kirillov and Herbert Wilf for useful discussions and my Gorgeous and Brilliant Wife, Bette, for her total support and love.

References

[1] Aleksandrs Mihailovs, Symplectic tensor invariants, wave graphs and S-tris (1998).

[2] Aleksandrs Mihailovs, Tensor invariants of SL(n), wave graphs and L-tris (1998).

[3] Aleksandrs Mihailovs, Diagrams of representations (1998).