Duursma zeta function of a graph

I’m going to start off with two big caveats:

This is not Duursma‘s definition, it’s mine.
I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.

So that’s your warning – you may be wasting your time reading this!

The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.

Duursma zeta function of a code

Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.

Let $C$ be an $[n,k,d]_q$ code, ie a linear code over $GF(q)$ of length $n$ , dimension $k$ , and minimum distance $d$ . In general, if $C$ is an $[n,k,d]_q$ -code then we use $[n,k^\perp,d^\perp]_q$ for the parameters of the dual code, $C^\perp$ . It is a consequence of Singleton’s bound that $n+2-d-d^\perp\geq$ , with equality when $C$ is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function $\zeta=\zeta_C$ :

$\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},$
where $P(T)=P_C(T)$ is a polynomial of degree $n+2-d-d^\perp$ , called the zeta polynomial of $C$ . We next sketch the definition of the zeta polynomial.

If $C^\perp$ denotes the dual code of $C$ , with parameters $[n,n-k,d^\perp]$ then the MacWilliams identity relates the weight enumerator $A_{C^\perp}$ of $C^\perp$ to the weight enumerator $A_{C}$ of $C$ :

$A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).$
A polynomial $P(T)=P_C(T)$ for which

$\frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ .$
is a (Duursma) zeta polynomial of $C$ .

Theorem (Duursma): If $C$ be an $[n,k,d]_q$ code with $d\geq 2$ and $d^\perp\geq 2$ then the Duursma zeta polynomial $P=P_C$ exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let $\Gamma=(V,E)$ be a graph having $|V(\Gamma)|$ vertices and $|E(\Gamma)|$ edges. We define the zeta function of $\Gamma$ via the Duursma zeta function of the binary linear code defined by the cycle space of $\Gamma$ .

Theorem (see [DKR], [HB], [JV]): The binary code $B=B_\Gamma$ generated by the rows of the incidence matrix of $\Gamma$ is the cocycle space of $\Gamma$ over $GF(2)$ , and the dual code $B^\perp$ is the cycle space $Z=Z_\Gamma$ of $\Gamma$ :

$B_\Gamma^\perp = Z_\Gamma.$
Moreover,
(a) the length of $B_\Gamma$ is $|E|$ , dimension of $B_\Gamma$ is $|V|-1$ , and the minimum distance of $B_\Gamma$ is the edge-connectivity of $\Gamma$ ,
(b) length of $Z_\Gamma$ is $|E|$ , dimension of $Z_\Gamma$ is $|E|-|V|+1$ , and the minimum distance of $Z_\Gamma$ is the girth of $\Gamma$ .

Call $Z_\Gamma$ the cycle code and $B_\Gamma$ the cocycle code.

Finally, we can introduce the (Duursma) zeta function $\Gamma$ :

$\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},$
where $P=P_\Gamma=P_{Z_\Gamma}$ is the Duursma polynomial of $\Gamma$ .

Example: Using SageMath, when $\Gamma = W_5$ , the wheel graph on 5 vertices, we have

$P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.$
All its zeros are of absolute value $1/\sqrt{2}$ .

References

[Du] I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109–136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.

[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.

[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Yet Another Mathblog

Duursma zeta function of a graph

Leave a Reply Cancel reply

Yet Another Mathblog

Share this:

Like this:

Related

Leave a Reply Cancel reply