Combinatorial representations

It is nice when several things that I care about come together. That is the story I have to tell here.

Some history

In April 2008, I visited New Zealand as the Forder Lecturer, a collaborative venture of the London Mathematical Society (who do the selection) and the New Zealand Mathematical Society (who look after the lecturer during the trip). I went to all the university towns in New Zealand (they lie on an approximately straight line), and had a wonderful time, which you can read about here.

Afterwards, I tried to find out about the future of the scheme: I recorded my attempts here. Eventually I discovered that, not only had the scheme not been wound up, but that a reciprocal scheme, the Aitken lectureship, had been established. The first Aitken lecturer will be Geoff Whittle, who was my host in Wellington on my Forder tour. He will be lecturing at Queen Mary twice, on 14 and 17 October (details here), and at other places around the country.

I have mentioned Geoff on this blog before: he was a philosopher before becoming a mathematician, and his current work on matroid representability may throw some light on Kant’s notion of “synthetic a priori truths”.

But the purpose of this post is to go on from there. Maximilien Gadouleau, Søren Riis and I are putting the finishing touches on a paper entitled “Combinatorial representations”, which bears the same relation to matroid representations as orthogonal partitions do to affine planes over fields.

Orthogonal Latin squares revisited

By way of introduction, I want to give a proof of a theorem which I mentioned in the post on orthogonal partitions:

Given any positive integer r, there exist r mutually orthogonal Latin squares of order n for all sufficiently large n (that is, larger than some function of r).

The proof uses Wilson’s theorem on pairwise balanced designs, which I discussed here.

We make a slightly stronger requirement for our Latin squares: they should all be idempotent, meaning that the diagonal element in row i and column i of each square is i.

Now we claim that the set of n for which r mutually orthogonal idempotent Latin squares exist is PBD-closed: that is, if we have a PBD(K) on n points, and such squares exist for each line size of the PBD, then squares of order n exist. To see this, choose r idempotent MOLS of order k, for each kK. Now suppose that n is in the PBD-closure of K; so there exists a PBD on the set {1,…,n} with block sizes from K, and each block indexes the rows, columns and symbols of r idempotent MOLS.

Now define r idempotent MOLS of order n as follows. Take i,j from {1,…,n}. If i=j, then the (i,j) entry of each square is i. Otherwise, a unique block of the PBD contains i and j; in the tth square, put the corresponding entry of the tth square corresponding to this block. It is easily checked that this construction does what was required of it.

By Wilson’s theorem, r idempotent MOLS exist for all sufficiently large n for which α(K) divides n−1 and β(K) divides n(n−1). So we are done if we can show that α(K)=1 and β(K)=2. But this follows because all sufficiently large prime powers belong to K. (If F is a field of order greater than r, then the squares Mt, for any choice of r distinct elements t of F different from 0 and 1, are idempotent MOLS, where Mt has (i,j) entry ti+(1-t)j.) If α(K)>1, then every sufficiently large prime power is congruent to 1 (mod α(K)), contradicting Dirichlet’s Theorem. The argument for β(K) is similar.

Combinatorial representations

The paper is twenty pages long, so this is just a taster. Since I am writing this post during an Isaac Newton Institute programme on statistics, I will point out some links with experimental design.

Let B be a family of r-element subsets of {1,…,n}. Keep in mind two standard examples: B is the family of bases of a matroid of rank r; or r=2 and B is the set of edges of a graph.

A combinatorial representation of B over an alphabet A is a collection of functions fi : ArA for i=1,…,n such that, for any r coordinates i1,…,ir, the map

(a1,…,ar) → (fi1(a1,…,ar),…,fir(a1,…,ar)),

from Ar to itself, is a bijection if and only if {i1,…,ir} is in B.

(If you know anything about network coding, you will have some idea about what lies behind this definition.)

Now we can make the following observations:

  • In the definition, the actual values of the functions fi are not really significant, only the partition of Ar into |A| parts given by the inverse images of elements of A. (In statistics, such a partition would be referred to as a factor.)
  • In fact, the domain Ar can be replaced by any set of the same cardinality, since the fuctions corresponding to an element of B give it the required Cartesian power structure.
  • A linear representation of a matroid is a combinatorial representation. (Take the functions fi to be the coordinate functions on the vector space.)
  • Conversely, a family of sets which has a representation by linear functions is necessarily the family of bases of a representable matroid.
  • Any family of r-sets has a representation by matrix linear functions.
  • A combinatorial representation of the complete graph Kn over an alphabet of size s is the same as a family of n−2 mutually orthogonal Latin squares of order s.
  • A graph (i.e. family of 2-sets) has a combinatorial representation over all sufficiently large alphabets.

The last result is proved using Wilson’s theorem on pairwise balanced designs; indeed, it uses the same ideas as the proof above of existence of MOLS. It suggests a couple of open questions:

  • How large is “sufficiently large”? (Our bounds are lousy, but there is no shame in that, since even in the case of complete graphs the bounds are lousy, despite a lot of attention over the last half-century or so.)
  • Is the conclusion “representable over all sufficiently large alphabets” valid for all r? (Our proof shows representability over alphabets of infinitely many sizes; but there is no “higher analogue” of Wilson’s theorem to fill in the gaps.)

One can begin developing generalisations of matroid properties in the abstract. For example,

  • an element i is a loop if it is contained in no set in B;
  • Two non-loop elements j and k are parallel if we can substitute one for the other in any set without affecting membership in B;
  • A set is independent if it is contained in an element of B.

These properties of the set family are independent of representation. However, given a representation, we can define more refined versions of them:

  • The element i is a relative loop if the corresponding factor (partition of Ar) does not have all its parts of the same size. (A statistician says a factor is uniform if all parts have the same size. Thus, discarding relative loops means we only need consider uniform factors.)
  • two non-loop elements j and k are relatively parallel if the corresponding partitions of Ar are equal. (A statistician would say that the factors j and k are aliased.)
  • a set of size s is relatively independent if the infimum of the corresponding factors is a partition of Ar into |A|s sets each of size |A|r-s.

The relative concepts clearly imply the absolute ones. In the case of matroid representations (but not in general), these implications reverse.

We do much more: here are some examples.

  • The intersection of two representable matroids is combinatorially represented by 2-row matrix functions, but the converse is false. This representability property defines an interesting collection of set families which deserves further investigation.
  • It is possible to define rank functions (submodular but not integral) for arbitrary families, but the family and its representation does not determine the rank function uniquely.

And so on.

Advertisements

About Peter Cameron

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

One Response to Combinatorial representations

  1. The paper is at http://arxiv.org/abs/1109.1216, if you want to read it.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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