Regular polytopes, 1

One of the topics I am thinking about with Dimitri Leemans at present concerns regular polytopes. He and his co-authors Maria Elisa Fernandes and Mark Mixer have produced some nice results and a tantalising problem about these objects. I will give a brief introduction here; hopefully later I will have some more to report on.

A polytope is a higher-dimensional generalisation of a polygon in 2 dimensions or a polyhedron in 3 dimensions. Rather than stretch your geometric intuition, I will describe polytopes combinatorially. Keep the cube in mind as an example. Here is the cube; I have selected a particular vertex v, edge e and face f. (Ignore the primed vertices for the moment.)

A cube

The faces (of whatever dimension) are partially ordered by geometric incidence. (In the cube, a vertex lies on an edge, an edge on a face, or a vertex on a face.) We “complete” the cube by a minimal and maximal element, corresponding to the empty set and the entire polytope.

The polytope, as partially ordered set, has the following properties:

  1. Every maximal chain has the same length. (In the case of the cube, a maximal chain has the form (empty set, vertex, edge, face, cube).) So we can talk about the dimension of a face: the empty set has dimension −1, a vertex dimension 0, an edge dimension 1, and so on.
  2. A connectedness condition: we can move from any face to any other by a sequence of steps in which consecutive faces are incident; we can further assume that every face in the sequence except the first and last has dimension i or j, where i and j are two given dimensions.
  3. If f and g are faces of dimensions i and i+2 respectively, then there are exactly two faces of dimension i+1 incident with both f and g. (In our picture of the cube, v and v’ are the faces incident with the empty set and e; e and e’ are incident with v and f; and f and f’ are incident with e and with the whole polytope.)

An automorphism of a polytope is a permutation of the faces preserving the partial order (and hence preserving the dimensions of faces). The collection of all automorphisms is closed under composition and so forms a group, the automorphism group of the polytope. The automorphism group of the cube is, as you would expect, the group S4×C2 of order 48.

It follows from the three conditions above that the identity is the only automorphism fixing a maximal chain. (In the case of the cube, suppose that an automorphism fixes v, e and f. Then it must fix v’, the only other vertex incident with e; similarly it must fix e’ and f’. Using the connectedness, we can work from any maximal chain to any other, and find that everything is fixed.)

So the number of automorphisms does not exceed (and, indeed, is a divisor of) the number of maximal chains. The most symmetric polytopes are thus the ones in which the number of automorphisms is equal to the number of maximal chains, and so the group of automorphisms acts transitively on the maximal chains. These are the regular polytopes.

Suppose that P is a regular polytope. Then there is a unique automorphism of P mapping any maximal chain to any other. We fix a maximal chain C = (f−1,…fd). Now, for any i with 0 ≤ d−1, there is a unique maximal chain Ci which agrees with C in every dimension except i, and so a unique automorphism ρi which maps C to Ci. Then ρi also maps Ci back to C, and so ρi2 = 1, where 1 denotes the identity automorphism.

For example, in the cube, ρ0 reflects the cube in the plane of symmetry bisecting the edge e; ρ1 reflects the cube in the plane of symmetry through v bisecting the face f; and ρ2 reflects the cube in the plane of symmetry through e and bisecting the angle between the faces f and f’.

A connectedness argument shows that, using these reflections in a suitable sequence, we can map C to any maximal chain. So the group G generated by the automorphisms ρi acts transitively on the maximal chains, and so must be equal to the automorphism group of the polytope.

So the automorphism group is generated by d involutions (elements of order 2).

These involutions have two more important properties:

  • If |i−j| ≥ 2, then ρi and ρj commute, so their product has order 2. (For example, in the cube, ρ0 and ρ2 are reflections in perpendicular planes.)
  • For any subset S of {0,…d−1}, let GS denote the subgroup of G generated by the elements ρi with iS. Then the intersection of GS and GT is equal to GST. This is called the intersection property.

A group generated by involutions with this property is called a string C-group. (“String” because we can imagine the involutions ρ0,…ρd−1 arranged along a string, so that non-adjacent involutions commute; the convention for Coxeter graphs is that involutions are joined by an edge if and only if they do not commute. The “C” stands for “Coxeter”.)

Conversely, any string C-group can be shown to be the automorphism group of a regular polytope.

This material is discussed in a paper by Daniel Pellicer, “CPR graphs and regular polytopes”, in the European Journal of Combinatorics 29 (2008), 59–71.

In the next part, I hope to discuss how we represent and recognise string C-groups, and how this contributes to the theory of regular polytopes.


Posted in exposition | Tagged , , , | Leave a comment

Hood fellowships

On Monday, we went to a celebration of 10 years of the Hood Foundation, in University House, a lovely building which had been a synagogue and then a bank and was now offices for part of the university administration (with a central area for functions like this). A young man played Bach cello suites from the balcony (where women used to sit when it was a synagogue), but unfortunately was completely inaudible over the rising level of conversation.

The most interesting part of the evening was an inspirational talk from John Hood. He said, in essence, that support for curiosity-driven research is vital for all our futures, and that New Zealand is very poor at supporting it compared to countries of similar size and wealth. What could we do? Only two things. First, try to persuade politicians of the importance of research. Second, encourage philanthropy. A large number of people are friends of the university (in some sense), and they can be encouraged to put their hands into their pockets.

I feel a little uneasy about all this, and I am not quite sure why. American universities have seen their alumni as a resource for many years now, but this has been slower coming to Britain (and, I suppose, New Zealand too). I don’t like relying on charity for support, though that is what I am doing at the moment, and having a very productive time of it. (Today, a paper submitted, a paper accepted and sent to the journal production department, progress on two further projects, and a very nice colloquium talk connecting C*-algebras, graphs, and dynamical systems.) Will the donors feel that I am using their money well? Should I be even thinking about this while I am so busy with the research?

Posted in mathematics and ... | Leave a comment

A symmetric design

Quite a long time ago, Arunas Rudvalis discovered a symmetric 2-(14080,1444,148) design: a set of 14080 points, with 14080 subsets of size 1444 called blocks, with the property that any point lies in 1444 blocks, any two points in 148 blocks, and any two blocks meet in 148 points. A few years ago, when I visited Harriet Pollatsek in Mt Holyoke, I met up with Arunas, and he suggested that we delve deeper into the structure of this design, which we did, and published a paper on a remarkable geometry it conceals.

At roughly the same time, I worked with Cheryl Praeger on designs with flag-transitive but point-imprimitive automorphism groups. These are fairly rare, and always have a beautiful structure involving number-theoretic or group-theoretic coincidences. Symmetric designs are even rarer. But we were led to suspect the existence of a symmetric 2-(1408,336,80) design. (Why one with one-tenth the number of points of the Rudvalis design? I have no idea!)

This never got published. The reason was that we (well, mainly Cheryl) developed a very general construction method, extending an earlier idea by Sharad Sane. The ingredients are three designs (one symmetric, one resolvable, and one group-divisible) with parameters related in a certain way, together with some bijections with appropriate properties. Our construction of our new design (and indeed, some known designs with subgroups of their full automorphism groups which are flag-transitive but block-imprimitive) were purely group-theoretic, and to a casual glance bore no resemblance to our general methods. Indeed, it can be quite hard to say exactly what designs and bijections should be put into the general method in order to produce these designs.

I will describe here the construction of the symmetric 2-(1408,336,80) design, because I have a small apology to make.

The group 3.M22 has a 6-dimensional representation over the field GF(4), giving rise to a semi-direct product G = 212:(3.M22). (Matrices generating 3.M22 can be obtained from the on-line Atlas of Finite Group Representations, and downloaded into a GAP program.) Restricting to the subgroup 3.M21, the 6-dimensional module has a 3-dimensional submodule, and so we obtain a subgroup H = 26:(3.M21) of G. So we can represent G as a permutation group of degree 22×64=1408 on the cosets of H. (Computationally, constructing this permutation representation is by far the most time-consuming part of the exercise.)

Now G is imprimitive, with 22 blocks of size 64; the group permuting the blocks is the 3-transitive M22. The stabiliser of a point has an orbit of length 336, which meets every block except the one containing the stabilised point in 16 points. The 1408 images of this point under G are the blocks of the required design.

My apology is for claiming, in various places, that the automorphism group of this design is the group used in the construction. In fact it is twice as large (though still flag-transitive and point-imprimitive). The outer automorphism of M22 acts as a field automorphism over GF(4), so is not visible in the linear action on the 6-dimensional module; but it does preserve the design. So the full group has structure 212:((3.M22):2).

It is no coincidence that I am thinking about this while Cheryl and I are in the same town, as you will not be surprised to learn if you have ever worked with Cheryl!

Posted in doing mathematics, exposition | Tagged , , , | 2 Comments

Across New Zealand

Yesterday, Cheryl Praeger arrived in Auckland on an overnight flight from the ICM in Korea. She is here for a meeting on Science advice to Governments, involving international scientific organisations (including the IMU) as well as government scientific advisers from a number of countries.

Because she arrived so early, her hotel room was not yet ready, and so Rosemary and I suggested that she come to our room to leave her belongings. Cheryl was keen to come when we suggested doing the Coast-to-Coast Walk – indeed I can think of few better ways to cope with a change of time zones.

There are few countries the size of New Zealand that can be walked across in a few hours; indeed, in most of New Zealand this would be out of the question. But Auckland is on a very narrow neck of land, and a 16km walk takes you from Viaduct Harbour on Weitamata Harbour, on the Pacific Ocean, to Onehunga Lagoon on Manukau Harbour, on the Tasman Sea. When I was in Auckland on the Forder lecture tour, I walked across and back before lunch.

On Maungawhau

The path takes in the summits of two of Auckland’s largest extinct volcanoes, Maungawhau (Mt Eden) and Maungakiekie (One-Tree Hill). It was a day of breathtaking clarity, warm in the sun though the air was cold; we went much slower than on my previous trip, stopping to look at things and potter round interesting sites.

At the end, the new electric train service took us back from Onehunga station to Britomart Travel Centre in under half an hour.

The most remarkable incident of the walk occurred in Cornwall Park, below Maungakiekie. We had had an excellent lunch in the Aspire Café in Manukau Road, but decided to defer coffee to the restaurant in Cornwall Park. But the restaurant seemed to be closed. So we went in to the tourist information office next door, to ask whether there was anywhere else we could get coffee.

There was one person there, Philippa Price, whose job title is Cornwall Park Information Centre Manager, but the only person she was managing was herself. On such a beautiful day, the park was crowded with tourists, and she had to deal with all who came to the information centre: one to register a dog with the Cornwall Park Dogs scheme, others just asking for directions, and so on. So she would have been perfectly entitled to say “No, the restaurant is closed for refurbishment, I’m afraid”.

What she actually said was “I’ll make you some”. Between other jobs, she brewed up a pot, sat us down at a table in one of the many rooms in the Information Centre (illustrated with stunning photographs of the park), and stopped to chat when other business allowed while we drank it. And at the end, she wouldn’t charge us anything for it!

At Cornwall Park Information Centre

I had on my Prague MCW T-shirt, and the word “Combinatorcs” seemed to ring a bell; she was sure she had seen me before. We established that it was probably when I talked about infinity on the BBC Horizon programme. Talking about other media appearances, I mentioned that I had been on the Kim Hill show when I was here on the Forder tour. She is a great fan of Kim Hill, and indeed of the radio in general, her window on the world, and before we left she had found the podcast of the interview.

It proved, if nothing else, that I don’t handle fame well. My two companions are probably more famous than I am, and I felt a little embarrassed about being in the limelight.

A final note on geology. There are about fifty extinct volcanoes in the Auckland volcanic field, a World Heritage Site for its combination of natural and cultural features. (Different authorities quote slightly different numbers.) It is near-certain that there will be another eruption one day; the Auckland City Council website estimates that an Auckland resident has about an 8% chance of experiencing one in his or her lifetime. Almost the only other things that experts agree on is that the next eruption will not be one of the existing volcanoes; it is completely unpredictable where and when it will be, and it is likely to cause very severe disruption and loss of life.


Posted in geography | Tagged , , , , , , | 2 Comments



Rosemary and I are in Auckland on a seven week research visit, supported by Hood fellowships from the University.

Already I am working on several projects, on polytopes, automorphic loops, symmetric designs, optimal neighbour designs, and median graphs. I hope to make progress on at least some of these things, and will report on this (and maybe a bit on my surroundings) later.

When we arrived, Auckland was a city of rain and fog, with views of mist and mystery from our 21st floor hotel room. Only yesterday did the sun come out and was I able to take the picture at the top of this post (from the corridor opposite my office).

Auckland harbour

Posted in geography, mathematics | Tagged , | Leave a comment

How to make awesome comics

WordPress claim the right to put advertisements on my blog, because I am too mean to pay them not to. But I think I have the right to put advertisements up myself.

Neill’s second book, How to make awesome comics, is now out. You can find details, and links to how to get your hands on a copy, on his blog.

How to make awesome comics

As the author says,

Buy it for every child you know, and also for any you don’t, and also for yourself.

I completely agree!

Posted in Uncategorized | Leave a comment

Google Scholar citations

This is too good not to report!

I looked at my Google Scholar page today. One of the items had an asterisk by it, so I decided to explore. It helpfully explained that this citation may include more than one item. On exploring further, I discovered that as well as

Designs, graphs, codes, and their links
PJ Cameron, JH Van Lint – 1992
Cited by 385

there was also

Codes, and their Links
PJ Cameron, JH Van Lint, G Designs – 1991
Cited by 92

But they don’t list “G Designs” among my co-authors. Should this researcher have Erdős number 2?? And why the different year?

Posted in the Web | Tagged | 4 Comments