Counting Polynomials for Channel Assignments, Hypergraph Colouring and Lattice Point Enumeration

Dominic Welsh University of Oxford

22 March 1999

Abstract

I shall present the results of some recent work with Geoffrey Whittle on a problem which originated in trying to extend classical theory of the Tutte polynomial of a graph to wider classes of structures. This we do by focusing on an equivalent version of the Tutte polynomial — what we call the bad colouring polynomial of a graph, and denote by B(G; λ, s). It is defined by

B(G; λ, s) = ∑_{k=0}^{|E|} b_{k}(G, λ)s^{k}

where b_{k}(G, λ) denotes the number of ways of colouring G with λ-colours so that exactly k edges are bad, that is have their end points the same colour. Equivalently, B(G; λ, s) is recognisable as a mildly distorted version of the partition function Z of the standard Q-state Potts model on G. The correspondence being obtained by the substitution λ → Q, s to inverse temperature.

Instead of the usual delete/contract recursion of the Tutte polynomial, the bad colouring polynomials b_{k}(G; λ) satisfy for all k ≥ 1, the recursion

b_{k}(G; λ) = b_{k}(G′_{e}; λ) − b_{k}(G′′_{e}; λ) + b_{k−1}(G′′_{e}, λ).

Here G′_{e}, G′′_{e} have their usual meaning of G delete (respectively contract) e. We realised that this relation, which we call the 3-term recurrence is satisfied by several other naturally occurring counting functions. We develop such a theory for the very general concept of a configuration Q. This is just a pair (E, f) with E a finite set and f : 2^{E} → ℤ satisfying

(i) f(∅) = 0,

(ii) f(A) ≤ f(B) whenever A ⊆ B.

Much of the standard theory goes through and applications include:

a) Counting the number of lattice points belonging to exactly j members of an arrangement of subspaces in AG(n, q).

b) Extending the theory of the Tutte polynomial from graphs to general hypergraphs.

c) Developing further the theory of the classical critical problem developed by Crapo and Rota 1970.

At the same time as we were working on these purely abstract problems we were also considering the highly applicable problem of assigning radio channel frequencies. This is a problem of huge commercial significance, which has received a great deal of interest over the last few years. One of the nicer applications of the theory that we have developed is to a counting problem in this area.

Reference

[1. ] Dominic Welsh and Geoffrey Whittle, Arrangements, Channel Assignments and Associated Polynomials, Advances in Applied Mathematics, 1999 (to appear).