Combinatorial aspects of an exact sequence that is related to a graph

M. Hofmeister Siemens AG, Munich Corporate Research & Development

Abstract The five problems of counting component colorings, vertex colorings, arc colorings, cocycles, and switching equivalence classes of a graph with respect to a finite field up to isomorphism are related by an exact sequence that stems from a coboundary operator. This cohomology is presented, and counting formulas are given for each of the five problems.

1 Introduction

Let G be an undirected simple graph with vertex set V = V (G), edge set E = E(G), and automorphism group Γ. Two objects related to G ( e.g. vertices, edges, components, vertex colorings,... ) are called isomorphic, if there is an automorphism of G mapping the one onto the other.

For some prime power q, let IF_{q} be the finite field of this order. Consider the following problems, which are related by the common use of the field IF_{q}.

Problem 1 Color the components of G with q colors. What is the number of such colorings up to isomorphism?

Problem 2 Count the nonisomorphic vertex colorings with q colors.

Problem 3 Let A = A(G) be the set of ( directed ) arcs of the corresponding symmetric digraph of G. An alternating coloring of G is an arc coloring with color set IF_{q}, such that inverse arcs have inverse colors, with respect to addition in IF_{q}. Count the alternating colorings of G up to isomorphism.

Problem 4 A cocycle of G is an alternating coloring of G such that, whenever (i, j) ∈ A, i ∈ V_{x}, j ∈ V_{y}, it follows that the color of (i, j) is x − y for a vertex partition (V_{u})_{u∈IF_{q}} in ( possibly empty ) pairwise disjoint sets. Enumerate the nonisomorphic cocycles of G.

Problem 5 Two alternating colorings of G are called switching equivalent, if they differ only by a cocycle of G. What is the number of nonisomorphic switching equivalence classes?

There is a nice cohomological approach relating these five problems. Our purpose is to present this cohomology and solutions of the problems. But let us first continue with some remarks. Problems 1 and 2 can be easily solved by Pólya’s theorem. Problem 3 reduces to the problem of coloring the edges of G with q colors up to isomorphism if the field characteristic of IF_{q} ( denoted by χ(IF_{q}) ) equals two; in this case, the enumeration can be done by Pólya’s theorem again. Problem 4 is solved in [5] in full generality. The last problem was solved in [7] for complete graphs and q = 2, and later for arbitrary graphs and q = 2 in [3] and [8] independently. In this paper we will present a counting formula for this problem in the general case of arbitrary graphs and finite fields; its proof can be found in [6].

2 Cohomology

All objects considered in Problems 1 - 5 have one property in common: they form vector spaces over IF_{q}. A vertex coloring of G with q colors can be understood as a function f : V → IF_{q}; let C^{0}(G; IF_{q}) be the vector space of such functions, with pointwise addition and scalar multiplication. In a similar way, an alternating coloring of G can be described by a function F : A → IF_{q} such that F (i, j) = −F (j, i) for each arc (i, j) ∈ A; let C^{1}(G; IF_{q}) be the vector space of such functions, with pointwise addition and scalar multiplication again. Next we define the vector space homomorphism

δ : C^{0}(G; IF_{q}) → C^{1}(G; IF_{q})  (1)

by setting

δ(f)(i, j) = f(i) − f(j)  ((i, j) ∈ A).  (2)

Let H^{0}(G; IF_{q}) = ke(δ), the 0-cohomology space of G, and let H^{1}(G; IF_{q}) = C^{1}(G; IF_{q})/im(δ), the 1-cohomology space of G. Let δ^{0} : H^{0}(G; IF_{q}) → C^{0}(G; IF_{q}) and δ^{1} : C^{1}(G; IF_{q}) → H^{1}(G; IF_{q}) be the canonical monomorphism and epimorphism, respectively. Then we have an exact sequence

δ^{0}  δ  δ^{1}
0 ⟶ H^{0}(G; IF_{q}) ⟶ C^{0}(G; IF_{q}) ⟶ C^{1}(G; IF_{q}) ⟶ H^{1}(G; IF_{q}) ⟶ 0.  (3)

Since H^{0}(G; IF_{q}) consists of those functions of C^{0}(G; IF_{q}) which are constant on the components of G, the space H^{0}(G; IF_{q}) is the space of component colorings of G with q colors. The set of cocycles of G corresponds to im(δ), while the set of switching equivalence classes is given by H^{1}(G; IF_{q}).

The following dimension formulas can be easily obtained from elementary counting arguments and exactness of Sequence 3.

Proposition 1 Let m, n, k be the number of edges, vertices, and components of G. Then

1. dim(H^{0}(G; IF_{q})) = k;

2. dim(C^{0}(G; IF_{q})) = n; 3. dim(C^{1}(G; IF_{q})) = m;

4. dim(H^{1}(G; IF_{q})) = m − n + k;

5. dim(im(δ)) = n − k.

3 Automorphisms

The automorphism group Γ of G, considered as a permutation group of the vertices of G, acts as a permutation group on edges, arcs, and components of G via γ[i, j] = [γ(i), γ(j)], γ(i, j) = (γ(i), γ(j)), and γ(H) = H̃ iff γ(i) is a vertex of H̃ for some vertex i of H, for each edge [i, j], arc (i, j), and component H of G. The cycle type of γ ∈ Γ, considered as a permutation of components, vertices, and edges of G, is denoted by (ω_{1}(γ), …, ω_{k}(γ)), (ν_{1}(γ), …, ν_{n}(γ)), and (ϵ_{1}(γ), …, ϵ_{m}(γ)), respectively. Their corresponding sums are denoted by ω(γ), ν(γ), and ϵ(γ).

The group Γ acts not only on vertices and edges of G, but also on the spaces C^{0}(G; IF_{q}) and C^{1}(G; IF_{q}) via

\begin{matrix}γ(f) = f ∘ γ^{−1} for f ∈ C^{0}(G; IF_{q}), \\ γ(F) = F ∘ γ^{−1} for F ∈ C^{1}(G; IF_{q}). \end{matrix}  (4)

Proposition 2 For every γ ∈ Γ, γ ∘ δ = δ ∘ γ.

It is Proposition 2 from which we conclude that Γ acts on H^{0}(G; IF_{q}) and im(δ) in an obvious way, and on H^{1}(G; IF_{q}) via

γ(F + im(δ)) = γ(F) + im(δ).  (5)

In the sense of Equations 4, every γ ∈ Γ establishes vector space automorphisms of the four spaces of Sequence 3 and of im(δ). Our considerations may be summarized by the observation that the diagram

δ^{0}  δ  δ^{1} 0 ⟶ H^{0}(G; IF_{q}) ⟶ C^{0}(G; IF_{q}) ⟶ C^{1}(G; IF_{q}) ⟶ H^{1}(G; IF_{q}) ⟶ 0
γ ↓  γ ↓  γ ↓  γ ↓  (6)
0 ⟶ H^{0}(G; IF_{q}) ⟶ C^{0}(G; IF_{q}) ⟶ C^{1}(G; IF_{q}) ⟶ H^{1}(G; IF_{q}) ⟶ 0
δ^{0}  δ  δ^{1}

is commutative.

4 Enumeration

The Problems 1-5 can be restated in the following form: Count the orbits of the actions of Γ on the spaces H^{0}(G; IF_{q}), C^{0}(G; IF_{q}), C^{1}(G; IF_{q}), im(δ), and H^{1}(G; IF_{q}). By Burnside’s lemma ( which is in fact due to Cauchy-Frobenius ), these problems reduce to the problems of counting the component colorings, vertex colorings, alternating colorings, cocycles, and switching equivalence classes that are fixed under γ, for every γ ∈ Γ.

We define homomorphisms α_{γ}^{0} : C^{0}(G; IF_{q}) → C^{0}(G; IF_{q}) and α_{γ}^{1} : C^{1}(G; IF_{q}) → C^{1}(G; IF_{q}) by setting

\begin{matrix}α_{γ}^{0}(f) = f − γ(f), \\ α_{γ}^{1}(F) = F − γ(F), \end{matrix}  (7)

for f ∈ C^{0}(G; IF_{q}) and F ∈ C^{1}(G; IF_{q}). Set β_{γ}^{0} = α_{γ}^{0}|H^{0}(G; IF_{q}), and let β_{γ}^{1} : H^{1}(G; IF_{q}) → H^{1}(G; IF_{q}) be defined by β_{γ}^{1}(F + im(δ)) = α_{γ}^{1}(F) + im(δ). In order to solve the Problems 1-5, it suffices to determine the sizes of ke(β_{γ}^{0}), ke(α_{γ}^{0}), ke(α_{γ}^{1}), ke(α_{γ}^{1}|im(δ)), and ke(β_{γ}^{1}). But in the cases of nonisomorphic component colorings and vertex colorings we can use Pólya’s theorem directly.

Theorem 1 The number of nonisomorphic component colorings of G with q colors is

\frac{1}{|Γ|} ∑_{γ∈Γ} q^{ω(γ)}.  (8)

Theorem 2 The number of nonisomorphic vertex colorings of G with q colors is

\frac{1}{|Γ|} ∑_{γ∈Γ} q^{ν(γ)}.  (9)

Let γ ∈ Γ, and let σ_{ν} be a vertex cycle of γ. The cycle σ_{ν} is called diagonal, if its size is even, say |σ_{ν}| = 2t, and [i, γ^{t}(i)] ∈ E for some i ∈ σ_{ν}. The corresponding edge cycle and arc cycle as well as their edges and arcs are called diagonal, too. Now set

ρ(γ) = \{ \begin{matrix}number of diagonal vertex cycles of γ , & if χ(IF_{q}) ≠ 2, \\ 0  , & if χ(IF_{q}) = 2. \end{matrix}  (10)

Theorem 3 The number of nonisomorphic alternating colorings of G with q colors is

\frac{1}{|Γ|} ∑_{γ∈Γ} q^{ϵ(γ)−ρ(γ)}.  (11)

Now we turn attention on the cocycles of G. Let σ_{ω} be a component cycle of γ. A vertex cycle σ_{ν} of γ is associated to σ_{ω}, if σ_{ν} permutes vertices of components in σ_{ω}. Let κ(γ) be the number of component cycles σ_{ω} of γ that have an associated vertex cycle σ_{ν} such that

\frac{|σ_{ν}|}{|σ_{ω}|} ≢ 0 (mod χ(IF_{q})).  (12)

Note that \frac{|σ_{ν}|}{|σ_{ω}|} indicates how many vertices of σ_{ν} are contained in a component of σ_{ω}. Recall that k is the number of components of G.

Theorem 4 The number of nonisomorphic cocycles of G over IF_{q} is

\frac{1}{|Γ|q^{k}} ∑_{γ∈Γ} q^{ν(γ)−κ(γ)+ω(γ)}.  (13)

As an application of Theorem 4, let G = K_{n} be the complete graph with n vertices. Then we have k = 1 and Γ = S_{n}, the symmetric group on the n vertices. For every γ ∈ S_{n} we have ω(γ) = 1, hence |σ_{ω}| = 1 for the only component cycle of γ. We conclude that

κ(γ) = \{ \begin{matrix}0 & if |σ_{ν}| ≡ 0 (mod p) for every vertex cycle σ_{ν} of γ, \\ 1 & otherwise . \end{matrix}

Now, by Theorem 4, the number of non-equivalent cocycles of K_{n} over IF_{q} is

\frac{1}{n!} ∑ q^{ν(γ)} + \frac{1}{q · n!} ∑ q^{ν(γ)},  (14)

where the first sum extends over all γ ∈ S_{n} such that |σ_{ν}| ≡ 0 (mod p) for every vertex cycle σ_{ν} of γ, and the second sum extends over the remaining permutations in S_{n}.

The cycle index of S_{n} [2] is the polynomial

Z(S_{n}; s) = \frac{1}{n!} ∑_{γ∈S_{n}} s_{1}^{ν_{1}(γ)} … s_{n}^{ν_{n}(γ)} ,

where s = (s_{1}, s_{2}, s_{3}, …). Set 1 = (1, 1, 1, …) and for r ∈ IN define 1[r] = (x_{1}, x_{2}, x_{3}, …) by setting

x_{i} = \{ \begin{matrix}1 & if r is a divisor of i , \\ 0 & otherwise . \end{matrix}

Then it follows from Expression 14 by a short calculation that the number of nonequivalent cocycles of K_{n} over IF_{q} is

\frac{1}{q}(Z(S_{n}; q · 1) + (q − 1)Z(S_{n}; q · 1[p])) ,

where, as usual, the number p is the field characteristic of IF_{q}. From this formula we obtained Table 1. The cycle indices of small order symmetric groups are tabulated in [2].

Now we will present a counting formula for the number of nonisomorphic switching equivalence classes of the graph G. We remarked already, that the problem reduces, by Burnside’s lemma, to the computation of the size of ke(β_{γ}^{1}), since this space is the set of switching equivalence classes fixed by the automorphism γ ∈ Γ.

\begin{matrix}q\n & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 2 & 2 & 3 & 3 & 4 & 4 & 5 \\ 3 & 2 & 4 & 5 & 7 & 10 & 12 & 15 \\ 4 & 4 & 5 & 11 & 14 & 24 & 30 & 45 \\ 5 & 3 & 7 & 14 & 26 & 42 & 66 & 99 \\ 7 & 4 & 12 & 30 & 66 & 132 & 246 & 429 \\ 8 & 8 & 15 & 50 & 99 & 232 & 429 & 835 \\ 9 & 5 & 21 & 55 & 143 & 339 & 715 & 1430 \\ 11 & 6 & 26 & 91 & 273 & 728 & 1768 & 3978 \\ 13 & 7 & 30 & 140 & 476 & 1428 & 3876 & 9690 \\ 16 & 16 & 51 & 276 & 969 & 3504 & 10659 & 30954 \\ 17 & 9 & 57 & 285 & 1197 & 4389 & 14296 & 43263 \\ 19 & 10 & 70 & 385 & 1771 & 7084 & 25300 & 82225 \\ 23 & 12 & 100 & 650 & 3510 & 16380 & 67860 & 254475 \\ 25 & 13 & 117 & 819 & 4755 & 23751 & 105183 & 420732 \end{matrix} Table 1

Consider the fiber product of the homomorphisms δ and α_{γ}^{1}, i.e. the space C_{γ}(G; IF_{q}) consisting of all pairs (f, F) such that δ(f) = α_{γ}^{1}(F), together with the canonical projections μ_{γ}^{0} : C_{γ}(G; IF_{q}) → C^{0}(G; IF_{q}) and μ_{γ}^{1} : C_{γ}(G; IF_{q}) → C^{1}(G; IF_{q}). Set C_{γ}^{0}(G; IF_{q}) = im(μ_{γ}^{0}) and C_{γ}^{1}(G; IF_{q}) = im(μ_{γ}^{1}). Then we have im(δ^{1}|C_{γ}^{1}(G; IF_{q})) = ke(β_{γ}^{1}). It is clear that we can obtain the size of ke(β_{γ}^{1}) from dim(C_{γ}^{0}(G; IF_{q})).

For an automorphism γ of G, let G_{γ} be the cycle graph of G with respect to γ, i.e. the simple graph with the vertex cycles of γ as vertices; two different vertices σ_{ν}, τ_{ν} of G_{γ} are adjacent in G_{γ} iff there are i ∈ σ_{ν}, j ∈ τ_{ν} such that [i, j] ∈ E(G).

We define an evaluation on vertex cycles of γ by setting Ω(σ_{ν}) = s if |σ_{ν}| = p^{s}u, where s is chosen so that p is not a divisor from u. Let V_{s} be the set of vertex cycles of γ that satisfy Ω(σ_{ν}) = s. Then G_{γ} < V_{s} > denotes the subgraph of G_{γ} induced by V_{s}. A component of G_{γ} < V_{s} > is called minimal in G_{γ} if it does not contain a vertex that is adjacent in G_{γ} to a vertex σ_{ν} with Ω(σ_{ν}) < s. Let X_{γ} be the subgraph consisting of the minimal components of all graphs G_{γ} < V_{s} > in G_{γ} if p ≠ 2, respectively the subgraph consisting of such components that do not contain a vertex that is a diagonal vertex cycle of γ if p = 2. Let ξ(γ) be the number of components of X_{γ}.

Recall that the number of vertex cycles of γ is denoted by ν(γ).

Theorem 5 The number of nonisomorphic switching equivalence classes of G is

\frac{1}{|Γ|} ∑_{γ∈Γ} q^{ϵ(γ)−ν(γ)+ξ(γ)−ρ(γ)}.  (15)

In order to illustrate the last theorem, consider again the complete graph G = K_{n} with n vertices, and remember the notations about its automorphism group given above.

Let γ ∈ S_{n}, and let (ν_{1}, …, ν_{n}) be the cycle type of γ. Then ν(γ) = ∑_{i=1}^{n} ν_{i}. From the cycle index of the pair group S_{n}^{(2)} ( see [2] ) we obtain ϵ(γ); the cycle indices of pair groups are tabulated in [2] for n ≤ 10.

\begin{matrix}q\n & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 1 & 2 & 3 & 7 & 16 & 54 \\ 3 & 1 & 2 & 4 & 14 & 120 & 3222 \\ 4 & 1 & 4 & 11 & 100 & 2200 & 242064 \\ 5 & 1 & 3 & 10 & 155 & 14030 & 6099115 \\ 7 & 1 & 4 & 21 & 1036 & 395283 & 943185908 \\ 8 & 1 & 8 & 50 & 3088 & 1557536 & 7022450816 \end{matrix} Table 2

Every vertex cycle of γ of even length is diagonal, hence

ξ(γ) = \{ \begin{matrix}0 , & if every vertex cycle of γ is of even length and p = 2, \\ 1 , & otherwise. \end{matrix}  (16)

Recall that p is the field characteristic of IF_{q}. Furthermore,

ρ(γ) = \{ \begin{matrix}Number of vertex cycles of γ of even length , & if p ≠ 2, \\ 0  , & otherwise. \end{matrix}  (17)

Using these facts, we obtained Table 2 presenting the numbers of nonisomorphic switching equivalence classes of K_{n} for some small values of n and q.

References

[1] J.L. Gross, T.W. Tucker, Topological Graph Theory, Wiley Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons (1987).

[2] F. Harary, E.M. Palmer, Graphical Enumeration, Academic Press, New York and London (1973).

[3] M. Hofmeister, Counting double covers of graphs, J. Graph Theory 12 (1988), 437-444.

[4] M. Hofmeister, Isomorphisms and automorphisms of graph coverings, Discrete Math. 98 (1991), 175-183.

[5] M. Hofmeister, Non-equivalent cocycles of graphs over finite fields, submitted.

[6] M. Hofmeister, On an exact sequence related to a graph, submitted.

[7] C.L. Mallows, N.J.A. Sloane, Two-graphs, switching classes, and Euler graphs are equal in number, SIAM J. Appl. Math. 28 (1975), 876-880.

[8] A.L. Wells, Even signings, signed switching classes, and (1, −1)-matrices, J. Comb. Theory Ser. B 36 (1984), 194-212.