Addressing and decomposing

A talk by Sebastian Cioaba yesterday reminded me of a nice piece of mathematics by Ron Graham and Henry Pollak. This was explained to me by Jack van Lint, a master expositor, and when I think about this (and indeed several other things he explained to me over many years) I hear it in Jack’s voice. He is much missed.

An addressing scheme with word length k in a connected graph G is a labelling of the vertices of G with words of length k over the alphabet {0,1,*} so that the Hamming distance between labels is equal to the graph distance between the vertices. The Hamming distance here counts the number of coordinates where the first word has 0 and the second has 1 or vice versa; the symbol * is regarded as standing for either 0 or 1 and does not contribute to the distance.

The idea is that, if a packet of information is at node v and wants to reach node w, it can compute how far it has to go; if it can also look at the neighbours of v, it can choose one with shorter distance and move there. So optimal routing can be achieved locally.

So we have the question: Given a graph, what is the minimum word length of an addressing scheme?

Questions like this are usually hard, and answers even in special cases are a bit messy. But Graham and Pollak pointed out that there is a simple answer, namely n−1, for the complete graph on n vertices, with a beautiful proof.

First we observe that Kn has an addressing scheme with word length k if and only if its edges can be partitioned into k bicliques, where a biclique is a complete bipartite graph (not necessarily using all the vertices). For given an addressing scheme, for each edge {v,w} there is a unique position i such that the entries of the labels of v and w in the ith position are 0 and 1. So the ith biclique in the decomposition consists of vertices with 0 and 1 in the ith position. The construction reverses in the obvious way.

So why cannot we partition Kn into fewer than n−1 bicliques?

The adjacency matrix of a graph is the symmetric 0-1 matrix having entries 1 corresponding to edges and 0 on the diagonal and for non-edges. Being symmetric, it corresponds to a quadratic form, whose rank and signature can be calculated from the eigenvalues of the matrix. For the complete graph Kn, the quadratic form is non-singular, with signature (1,n−1); that is, it is positive definite on a 1-dimensional subspace and negative definite on a complementary n−1-dimensional subspace.

For a biclique, it is easy to show that the quadratic form has rank 2 and signature (1,1). Now if we decompose the edges of the complete graph into bicliques, we can write the quadratic form for the complete graph as the sum of the forms for the bicliques. But a negative definite space of dimension n−1 cannot be written as the sum of fewer than n−1 subspaces of dimension 1. So we cannot have fewer than n−1 bicliques in the decomposition.

We can find a decomposition with n−1 bicliques (indeed, stars), by taking all edges through vertex 1, then all edges through vertex 2 but not 1, and so on, until the single edge from n−1 to n.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s