The O’Nan-Scott Theorem

I have decided that any mathematical blog entitled SymOmega should have an expository post about one of the most influential theorems of permutation group theory, that is, The O’Nan-Scott Theorem. Originally, this was a theorem about maximal subgroups of the symmetric group.  It appeared as an appendix to a paper of Leonard Scott in the proceedings of the Santa Cruz symposium on finite simple groups in 1979, with a footnote that Michael O’Nan had independently proved the same result. Apparently there are even earlier versions due to various people but it was the Classification of Finite Simple Groups (CFSG) which meant that it would become very useful.

In its simplest form the theorem states that a maximal subgroup of the symmetric group where , is one of the following:

1. , the stabiliser of a k-set (that is, intransitive),
2. with , the stabiliser of a partition into b parts of size a (that is, imprimitive), or
3. primitive (that is, preserves no nontrivial partition) and of one of the following types:

• ,

• with , the stabiliser of a product structure ,

• a group of diagonal type, or

• an almost simple group.

(These  types will be explained in further detail below).

It was soon recognised (perhaps first in a paper of Peter Cameron)  that the real power is in the ability to split the finite primitive groups into various types.  Problems concerning primitive groups can then be studied by solving them for each type.  This often sees questions about primitive groups reduced to questions about simple groups and then the force of the classification can be harnessed to get your result.  Furthermore, many results about transitive permutation groups can be reduced to the primitive case and so we actually have a tool for studying questions about transitive groups.

The division of primitive groups into various types is usually finer than given in the statement about maximal subgroups of as we are no longer concerned about maximality in but instead are more concerned about the types of actions. In Cameron’s original paper, the twisted wreath product case (again, more details later) which does not appear as a maximal subgroup of but is an important type of action with a distinctly different flavour to the maximal subgroup   it is contained in,  was left out and this was corrected in a subsequent paper of Aschbacher and Scott, and in work of Laci Kovacs. A complete self-contained proof is given in a paper by Martin Liebeck, Cheryl Praeger and Jan Saxl.

Since I am from Perth, I usually  follow the  division and labelling into 8 types due to Cheryl Praeger which appears here and here.  First we need to deal with a few preliminaries.

What staff shortage?

There was a story in The Australian newspaper last week warning that universities faced a “looming staff shortage” as thousands of academics approach retirement and that widespread dissatisfaction with high workloads and the corporate management culture would mean that there wouldn’t be enough new blood to replace them. (Here’s a link to the article.)

It sounds convincing enough, but – at least in mathematics – it just doesn’t seem to gel with what we actually see on a day to day basis, either at UWA or elsewhere. With a couple of exceptions, it seems that most Australian universities are still reducing staff in mathematics departments, and actively welcome retirements rather than worry about replacing them. Certainly our department has shrunk more or less monotonically for more than 20 years, and there are no signs that it has bottomed out.  And of course there are well known examples like Flinders, which was rather embarrassed when Terry Tao won the Fields Medal and the media descended on his alma mater only to discover that they had essentially shut down all higher-level maths.

Meanwhile, despite the constantly deteriorating conditions, there seems to be no shortage of really good applicants for the occasional positions that come up, especially in Pure Mathematics. I personally know several really first-rate young pure mathematicians currently on fixed-term research-only positions who are searching, with varying degrees of desperation, for any continuing position (where “continuing” means “not fixed term” – the word “tenure” in Australia no longer has any connotations of job security or permanency because anyone can be fired at any time simply on financial grounds) and several more who have simply given up.

Perhaps this is unique to mathematics and other disciplines really are finding a looming staff shortage? (But here again, obviously the University of Melbourne is not too concerned, given that they’re busily trying to get rid of more than 200 staff, though not all are academics.)

So what gives?

[Update (9 October): See Terry Tao’s recent post on the “Maths in Australia” blog about the new AMSI director writing to Victoria University, one of the universities that is proposing further cuts in maths]

What ought to be in any pure mathematics degree?

With the recent cut-backs in mathematics and statistics programmes around Australia, we are now being asked to rationalise our offerings and provide less choice for our undergraduates. So what are the essential threshold concepts that someone intending to major in pure mathematics ought to know? For example, “linear independence” is such a concept, but “group theory” is not a good answer as there are extraneous areas of group theory which are not essental (e.g., Grigorchuk groups). Nor is “linear algebra” a good answer as it is debatable whether everyone should learn what a tensor product is (but you are allowed to disagree with me on this one). So should every pure-maths graduate know…

(1) that every integer has a unique factorisation into primes?

(2) the epsilon-delta definition of a limit?

(3) the Prime Number Theorem?

(4) proof by induction?

(5) an axiomatic notion (e.g., vector space, group, ring)?

(6) finite Galois fields?

(7) a theorem by Euler?

(8) the basic ideas of cardinalities (e.g., rationals are countable)?

So please contribute so we can cut out courses!

AustMS conference

I am back after my trip to the annual meeting of the Australian Maths Society in Adelaide. There were 12 plenary speakers this year. Going to one of these general meetings always reveals how big a subject mathematics is and how little of it I know. For this reason I always prefer “big picture” plenaries over more detailed ones. A couple of personal  highlights were Terry Tao’s public lecture on `Structure and randomness in the prime numbers’,  Jacqui Ramagge’s talk on `Totally disconnected, locally compact groups’ which outlined the theory of the subject developed mainly by George Willis,  and Akshay Venkatesh’s talk on his work with Ellenberg and Westerland on `The Cohen-Lenstra heuristics over global fields’.

There were up to 12 parallel sessions on at any given time. I mainly attended the combinatorics session where there were many good talks and  I spoke on `3/2-transitive permutation groups’. I have uploaded the slides for my talk. I  also ventured to the Topological groups session  and enjoyed Daniel Horadam’s talk there on `Automorphism groups of trees’. There were many other talks I would have liked to have gone to but they clashed with other interesting talks or me speaking.

Overall the conference went very well and the organisers should be congraulated on the great job they did. The conference dinner was also very well done: the food and wine was great and there was even a band.

AustMS talk on chromatic roots

I gave my talk at the AustMS 2009 meeting yesterday, and have now uploaded the PDF slides of my talk which was called Chromatic Roots and Maxmaxflow.

I was lucky enough to be the “keynote” speaker at the special session on Combinatorics so I got a one-hour time slot, which is usually easier to deal with than a shorter one.

The talk itself was a more focussed variant of a talk I gave at the British Combinatorial Conference in July this year, and describes my recent work with Alan Sokal, which is essentially complete, but just needs wrestling into final publishable shape. Working with Alan is a tremendous privilege, but exploring every possible generalization, hypothsis-weakening and related application that his incredibly fertile brain  throws up is incredibly time-consuming for a mere mortal!

Anyway the gist of this work is that we want to find a parameter to replace maximum degree in the result that the moduli of chromatic roots are bounded by a function of maximum degree. The parameter maxmaxflow which is defined to be the maximum number of edge disjoint paths between any pair of vertices is a promising alternative, and this talk gives a very general overview of our proof that it works for series-parallel graphs.

Maths activities for school students

One of the things John and I do around here is run activities for groups of school students  who are visiting the university. Today we had such a visit from a group from Esperance.  The visits often include activities in other disciplines across campus, for example physics demonstrations or building bridges/gyroscopes/electric motors in engineering. This presents an interesting dilemma as to what the maths activity should be.  It needs to be very much hands on so that the students get to do something. John and I are also keen for it to be very different to the sort of maths done at school.

Currently, our main activity revolves around the game of Nim. We introduce the rules of the game, give a short demonstration and then call for challengers. We offer a chocolate bar to anyone who can beat us.  After a couple of games, we then give all the students some counters and get them to play the game amongst themselves so that they can try and work out a winning strategy and continue to try to beat us.  Towards the end of the activity we outline binary numbers, Nim addition and how to use it to win.  The activity goes down really well.  It draws  on their competitive instincts and some students get right into trying to beat us. It has worked with the whole range of high school ages and we once even ran the activity successfully  for a group of primary school students (minus the maths behind it though).

We are interested in learning about  other suitable activities.  It would be good to have a couple up our sleeves as there are sometimes students who attend more than one of these visits. John is looking at developing something involving Conway’s Rational Tangles. He has demonstrated it to a couple of groups of students now and has been very succesful but it is more of a demonstration than an activity. Ideally we should pair it with a couple of other things as we usually have 45-60 minutes. Please let us know of other activities that work well which could be done with or separately to these.

Lose the beamer navigation symbols!!

We’re all getting ready here for next week’s Australian Math Society conference in Adelaide, so I’ve been watching a few practice talks. Watching these, along with a few other recent talks,  reminded me of a pet peeve.

Nowadays, even in mathematics conferences, most talks are computer presentations, and most of these are prepared using Till Tantau’s beamer package for LaTeX.

Although beamer is amazingly good – or perhaps because beamer is amazingly good – its sheer ubiquity means that so many talks “look the same”.

And one way in which they look the same is that although I have never seen anyone use them in a talk, almost everyone seems to keep the default navigation symbols at the bottom corner of every page, where they often overlap the content and generally clutter the page.

But it is so easy to turn them off – just add

\setbeamertemplate{navigation symbols}{}

before the beginning of the document and away they go!

Akshay Venkatesh

Today I had a meeting at our Institute of Advanced Studies to discuss the  programme for Akshay Venkatesh‘s  visits here as a  Professor-at-Large for 2010 and 2011. This will involve a visit each year and the tentative schedule is that over the course of his two visists he will give a public lecture, a masterclass for postgraduate students and  teach parts of some honours courses.

Akshay did his undergrad here at UWA before going off to the US for his postgrad. He is now a Professor at Stanford and is an invited speaker at next year’s International Congress of Mathematics. His first visit  as a Professor-at-Large will be directly after the congress. He was also here today for the meeting and we were able to reminisce about sharing an office in the period between our honours year and going off to separate parts of the world for our PhD’s.

Maths talks on the web

I have just come across the Newton Institute’s Web seminars. It looks a great resource of various talks given at the Institute including those given as part of their programmes and workshops. They seem to have  quite an extensive recording mechanism as there appears to be several cameras involved. The files are a bit big but I can see myself wasting hours watching them as long as my australian broadband can cope. The site includes a talk by Gordon.

Edge-primitive graphs

I have just finished reading the proofs for my paper `On finite edge-primitive and edge-quasiprimitive graphs’ with Cai Heng Li which has just been accepted in JCTB. This paper has been a long time in the making as Li and I started the work in 2002! Usually when I submit a paper to a journal I put a preprint up on my research web page but I should really start uploading them also to the arxiv so I have just done so and it is now available there.

A graph is called edge-primitive if its automorphism group acts primitively on the set of edges.  Many famous graphs such as the Heawood graph, Tutte-Coxeter graph, Hoffman-Singleton graph and Higman-Sims graph are edge-primitive.  The paper begins a systematic study of edge-primitive and edge-quasiprimitive graphs by analysing the possible actions on vertices and edges.