Automorphism groups of hypergraphs

I am getting old and forgetful, but I don’t think I said anything here about this problem yet. If I did, apologies for the repetition – but there is something new to report!

In April, Laci Babai and I finally polished a paper which we started in 1990, and sent it off to a journal. Perhaps the headline theorem of the paper asserts:

Except for the alternating groups and finitely many others, every primitive permutation group is the full automorphism group of a uniform hypergraph.

A famous theorem of Frucht states that every (abstract) group is the full automorphism group of a graph. However, it is not true that every permutation group is the automorphism group of a graph (acting on the vertex set of the graph); for example, the only graphs preserved by a doubly transitive group are the complete and null graphs, whose full automorphism groups are the symmetric group. Our theorem describes a way of making good this lack. (A uniform hypergraph is like a graph, except that its “edges” have some fixed cardinality k which is not necessarily 2.)

A permutation group G of degree n is set-transtive if any two subsets of the domain of the same cardinality lie in the same orbit of G. Thus, if G is set-transitive, then any G-invariant hypergraph consists of all or none of the k-subsets, for all k, and its full automorphism group is the symmetric group. Thus, set-transitive groups other than symmetric groups cannot be automorphism groups of hypergraphs. These groups include the alternating groups and just four others. This problem itself has an interesting history. It was posed in the first edition of von Neumann and Morgenstern’s Theory of Games and Economic Behaviour, and in the second edition they report that it was solved by C. Chevalley. But as far as I know, Chevalley’s solution was never published, and the solution is usually credited to Beaumont and Petersen. The four groups are: AGL(1,5), degree 5, order 20; PGL(2,5), degree 6, order 120; PGL(2,8), degree 9, order 504; and PΓL(2,8), degree 9, order 1512.

Laci Babai and I were asked this question by Misha Klin at a graph theory conference in Japan in 1990, and succeeded in solving it. We showed, further, that the automorphism group of the hypergraph could be taken to be edge-transitive, even edge-regular, in general (that is, the stabiliser of an edge is the identity), and that the cardinality of the edges could be taken to be n3/4+o(1). I was in favour of publishing the result, but Laci held out for an improvement of the last fact to n1/2+o(1). This was eventually achieved (largely by his efforts), but by then the theorem had sunk down the pile.

One of the antecedents of this theorem was one I proved with Peter Neumann and Jan Saxl in 1984: apart from the alternating groups and finitely many others, a primitive permutation group has a regular orbit on the power set of its domain. My theorem with Laci shows that in general we can take such an orbit to be the edge set of the required hypergraphs. Now in 1997, Ákos Seress published a paper in which he found all the exceptions in the Cameron–Neumann–Saxl theorem. (There are exactly 43 exceptions, the largest degree being 32.) After his untimely recent death, Laci and I decided that our paper would be a suitable tribute to him.

The new thing to report is that Pablo Spiga has now found all the exceptions in the Babai–Cameron theorem. There are 15 of them, with degrees ranging between 5 and 10, and they include (as they must) the four exceptional set-transitive groups.

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

Metrics

HEFCE had a consultation on metrics. I found out about it too late to send in a submission.

But you may want to read what two people whose opinions I respect, David Colquhoun and David Spiegelhalter, have to say.

Posted in Uncategorized | Tagged , , , | 1 Comment

Busy times, 10: in Waterloo

After a week in London, off to Waterloo for Chris Godsil’s 65th birthday conference.

The week at home was no holiday: among other things I managed to

  • read and examine Christopher Harden’s PhD thesis (a nice study of fixed point polynomials of permutation groups);
  • write a talk for the Waterloo conference, and most of a talk for the
    Portuguese Mathematical Society summer meeting, from scratch;
  • make my annual foray to Oxford Street for clothes shopping (this didn’t get done last year, I was too busy, and having to divide my clothes between two places meant things were getting rather desperate);
  • go on an expedition to the dinosaurs in the Natural History Museum with my children and grandchildren.

A couple of nice speculations from Christopher Harden’s thesis (I don’t think he would call them conjectures unless he were feeling extremely optimistic; but he worked many examples and these speculations appear to hold). The fixed point polynomial of a permutation group is the generating function for the number of fixed points of elements of the group; that is, the coefficient of xm is the number of group elements with m fixed points.

  • The number of real roots of the fixed point polynomial of a transitive permutation group is bounded above by an absolute constant.
  • The roots of fixed point polynomials for arbitrary permutation groups are dense in the complex plane (not true for transitive groups, he found a zero-free region).

Then an early start on Sunday morning in order to catch a 10:40 flight from
Gatwick to Toronto.

I was delighted to be asked to speak, although I have no formal connection with Chris; much to people’s surprise, we don’t even have a joint paper. (Plenty of time yet! As far as the photography session before the conference banquet was concerned, what I share with Chris is being aged 65+ and being Australian/New Zealander.) But we have enough common interests that I felt I had things to say about graph endomorphisms and synchronization that would be interesting to him and his students and postdocs; I hope that proved to be the case.

With Chris Godsil

The conference was in the quantum nano centre, which seems to be practical as well as theoretical: is this the kit needed to build a quantum computer?

Building a quantum computer

It was a wonderful occasion, a very happy conference, which is a tribute to the esteem in which Chris is held by colleagues and present and former students. I first met Chris in 1980 (if I recall correctly): I was visiting Sydney, and he and Brendan McKay invited me down to Melbourne to work together for a few days. So it seems that I had known him for longer than most people at the meeting (Brendan, Cheryl Praeger and Wilfried Imrich excepted).

The front wall of the lecture room under the projector screen was one huge whiteboard – but the pens were not good enough to risk a board talk. The very left of the board was reserved for information; the first item concerned “collaboration space”, a room in another building where people could go to work together. I suggested that the term might be interpreted as “collaboration graph with extra structure”, e.g. with a simplex pasted on for every set of authors who have written a paper together (or should we require that to form a simplex it would have to be the case that every subset of those authors should have a paper together? I think not, since this requirement is not enforced for the graph.)

A lot of good talks too, some of which I will try to describe briefly.

  • Brendan McKay talked about his result on counting k-regular graphs with 1-factorisation. This is new, but Brendan and Chris did the bipartite case (aka counting Latin rectangles) long ago, and some of Chris’ tricks are useful here too.
  • Gordon Royle gave a summary of results about roots of chromatic polynomials. Since the Newton Institute programme in 2008, much of this wasn’t new to me, but the pictures really add something to the results.
  • There were several talks on perfect state transfer in quantum random walks on graphs. This seems to be a relatively rare phenomenon, each new example being something to take note of.
  • On a related theme, Chris himself talked about perfect mixing in quantum random walks. This is in some sense the reverse. Instead of wanting the wave function concentrated at a single vertex at some time, you want the probabilities evenly spread over all vertices. This is almost as rare. The only cycles known to have the property are those of lengths 3 and 4. It is known that there are no other even cycles, but the proof of this apparently simple fact requires tools as deep and devious as the Gel’fond–Schneider theorem on the transcendence of ab for algebraic numbers a and b (if the latter is irrational) and an analytic theorem of Haagerup. As he said, new tools needed! Akihiro Munemasa followed up with a talk about finding some examples (aka complex Hadamard matrices in 3-class association schemes). He also explained the array of antipodean animals on the front of the conference programme.
  • A couple of authors including David Roberson and Simone Severini talked about graph parameters lying between the clique number and the chromatic number (and so potentially useful in the synchronization project).
  • Although I had heard part of it before, I really liked Bojan Mohar’s talk about median eigenvalues of graphs (especially bipartite graphs). He took us right from Hückel’s molecular orbital theory (which, using an approximate version of Schrödinger’s equation, reduces analysis of aromatic hydrocarbons to a problem on eigenvalues of graphs) to recent results on the “median gap”. An interesting speculation was whether there could be a carbon molecule with the configuration of the Heawood graph (a kind of super-buckyball). Apparently such a molecule would have metal-like properties.
  • Marston Conder talked about “Extreme graph symmetries”, which sounds like a new sport for the daredevil mathematician.
  • Cheryl Prager told us how much of her joint work with Chris had involved asking questions about doubly transitive groups which could not be answered just by having a list of the groups available – these included distance-transitive graphs, imprimitive rank 3 groups, and neighbour-transitive codes in the Johnson schemes. I certainly agree that there are many more problems hiding here, as in some of my work with João Araújo.

My slides are in the usual place.

Herons

For the excursion, we went to Elora, where the Grand River flows through a spectacular gorge. Ian Wanless and I went for a walk along the gorge, and came back to look at a map in the tourist information (which suggested some much less interesting walks). Then we had lunch in a pub, coffee in another, and a beer in a third, until it was time to go.

Posted in events | Tagged , , , , , , , | 2 Comments

A five-finger exercise

This morning at the Godsil 65 conference, Cheryl Praeger was wearing a T-shirt she was a bit ashamed of. It had been produced by the Australian Mathematics Trust to commemorate Niels Abel’s anniversary, and featured a quintic equation (he was the mathematician who first showed conclusively that the quintic is not soluble by radicals). Unfortunately the quintic they had chosen has an integer root!

So here is my suggestion for a problem which should be easy if you have done any Galois theory. The other thing Abel is remembered for is abelian groups, so why not an irreducible quintic with abelian Galois group?

Exercise: Find a simple example of such a quintic.

Posted in Uncategorized | Tagged , , | 4 Comments

Almost highly transitive

I want to discuss a concept I have known about for quite a long time, but never found any real use for. Suggestions welcome!

Highly transitive groups

A permutation group is n-transitive if it has a single orbit on the set of n-tuples of distinct elements from its domain; it is highly transitive if it is n-transitive for all natural numbers n. (This concept, of course, applies only to infinite permutation groups.)

Apart from the symmetric group, and the finitary symmetric group, there are very many examples; many additional properties can also be required.

Almost highly transitive groups

The context is measure theory: we have a probability space X (a measure space of total measure 1). As usual, we say that something happens “almost everywhere” if it is true on a set of measure 1 (that is, everywhere except for a null set).

We say that a group G of measure-preserving transformations of X is almost transitive if it has an orbit (necessarily unique) of measure 1. More generally, G is almost n-transitive if it has an orbit of measure 1 on Xn (the set of n-tuples of elements of X, with the product measure); and G is almost highly transitive if it is almost n-transitive for all natural numbers n.

First example: graphs

There is a natural measure on the set of all graphs on a given countable vertex set V, described by the phrase “choose edges independently with probability 1/2″. More formally, we give measure 1/2n(n−1)/2 to the set of graphs which induce a given finite graph on a given n-element subset of V, and extend to the Borel sets (or the Lebesgue-measurable sets) in the standard way. The symmetric group on the set V acts as a group of order-preserving transformations of this space.

The Erdős–Rényi theorem (see here), asserting that a specific graph R (the “random graph” or “Rado graph”) occurs – up to isomorphism – with probability 1, shows that Sym(V) is almost transitive: isomorphisms are induced by elements of the symmetric group.

Now choose n graphs independently at random from this probability distribution. There are 2n possibilities for the structure of a pair of vertices, since they may be an edge or a non-edge in each of the n chosen graphs. The Erdős–Rényi argument, almost unchanged, says that a unique structure arises with probability 1.

Thus the action os Sym(V) on the space of graphs is almost n-transitive for all n, that is, almost highly transitive.

Orders

Now consider the same group Sym(V) for a countable set V, acting on the set of total orders of V.

How do we choose a total order at random? One way is to enumerate the points of V, as v1, v2, …, and order them in stages. Suppose that, after n stages, the first n points have been ordered. Then they give n+1 “intervals”: before the smallest, between the smallest and the second smallest, …, after the largest; assign the (n+1)st point randomly to one of these intervals, all intervals equally likely.

A calculation shows that this measure can also be described by saying that, given any n points, all n! orderings are equally likely. (There is something to prove since the n points may not be the first in the enumeration.) This description shows that Sym(V) does indeed act as a group of measure-preserving transformations.

Perhaps not surprisingly, a random order is isomorphic to the order of the rational numbers with probability 1. By Cantor’s theorem, this is the unique dense order without endpoints on a countable set, so it suffices to show that the random order is dense and without endpoints with probability 1. By the usual argument invoking the fact that a countable union of null sets is null, it suffices for density to prove that given two points y and z, conditional on y < z, the probability that no point lies between y and z is zero.

But we can compute this probability. Starting at stage n (assuming that by this stage we know that y is smaller than z and no point lies between), the probability that no subsequent point is put into this gap is

(1-1/(n+1))(1-1/(n+2))… = 0

(the infinite product diverges).

The proof that there is no least or greatest element is similar.

So we have established that Sym(V) is almost transitive on the set of orders.

The proof that it is almost n-transitive involves a small subtlety, which held me up for a while. The object we should get if we choose n orders independently is the unique countable homogeneous universal n-order (described here). But the calculation similar to the one I did above is much more difficult.

The trick is as follows. I describe the case n = 2 (biorders) here; the general case is similar.

Another way to describe the countable dense order without endpoints is as follows. Sample countably many points from the uniform distribution on the open unit interval. The denseness and absence of endpoints are easily shown by simple arguments involving geometric probability.

Now we see that choosing two such orders is equivalent to sampling countably many points from the open unit square. Once again the defining property of the universal homogeneous biorder is easily verified.

So, indeed, Sym(V) is almost highly transitive on the set of orders on V.

Triangle-free graphs

There is a nice triangle-free graph (countable, universal, homogeneous), namely Henson’s graph. I struggled for years to find a similarly nice measure which gives the isomorphism class of Henson’s graph measure 1; the difficulty arises because triangle-free graphs have a very strong tendency to be bipartite (the Erdős–Kleitman–Rothschild theorem). The problem was solved by Petrov and Vershik, as I described here.

So Sym(V) acts as measure-preserving transformations of the space of all graphs on the vertex set V, with the Petrov–Vershik measure, and the action is almost transitive; the unique orbit of measure 1 is the isomorphism class of Henson’s graph.

Problem: Is this action almost highly transitive?

Footnote: Baire category

If G acts by isometries on a complete metric space, there is an analogous notion of “almost transitive”: G is almost transitive if it has an orbit which is residual (contains a countable intersection of open dense sets). Then we can make a similar definition of “almost highly transitive”.

As usual in this game, the Baire category notion is much better explored than the probabilistic notion. In particular, many closed permutation groups (such as the symmetric group, and the automorphism group of the random graph) have the property that their actions on themselves by conjugation is almost highly transitive: that is, there is a generic element (whose conjugacy class is residual), and indeed, for any n, a generic n-tuple of elements. These facts play an important role in the proof of the strong index property for these groups.

Posted in Uncategorized | Tagged , , , , , , , | 1 Comment

Busy times, 9: Beyond the limit in St Petersburg

Anatoly Vershik

Anatoly Vershik is a universal mathematician, with influential work in asymptotic combinatorics, groups and group actions, probability, mathematical physics, and many other areas.

This week, I was in St Petersburg for a conference with the wonderful title “Representations, Dynamics, Combinatorics: In the Limit and Beyond”, celebrating his eightieth birthday. The meeting was at the Euler International Mathematical Institute, commemorating a universal mathematician who spent much of his career in St Petersburg.

Leonhard Euler

In their talks, both Benjamin Weiss and Hillel Furstenberg quoted Psalm 90, which in the King James version reads

The days of our years are threescore years and ten; and if by reason of strength they be fourscore years, yet is their strength labour and sorrow; for it is soon cut off, and we fly away.

Both of them used something like “heroism” in place of “strength” here. It is heroic of Anatoly to be still as active in mathematical bridge-building as he is. He is a hero in another sense too. As someone who has always chosen his own path, he had a lot of trouble from bureaucrats during his life, even condemned to work in an Operations Research department for a time. But these stories are better told by someone else.

He is more than twelve years older than I am, but perhaps I am scattier. I was in the agency that processes Russian visa applications for an hour and three-quarters, at the end of which I know what the stupid pupils in the class feel like. I took the form to the desk three times; the first two times I was told no, this wasn’t right, I should go away and do it again. They had computers in the place which applicants could use to re-do their forms, but although the form asked for the name, address, and telephone of every educational institute you had been to, access to all educational institutes was blocked, so I had to be a bit creative. Eventually the form was done and submitted, and I was told to come back the following afternoon. I spent the intervening thirty hours worrying about all the reasons they might have for turning down my application, but in the end my passport was there with a visa in it.

There was far too much interesting stuff at the conference for me to mention all but a small selection.

  • Jarik Nešetřil gave a nice talk about the connections between Ramsey theory (specifically, the classification programme for Ramsey classes of structures) and homogeneous countable structures, and also his recent work with Patrice Ossona de Mendez on the connections between homomorphism counting and graph structure.
  • Tatiana Smirnova-Nagnibeda and Slava Grigorchuk talked about Vershik’s notion of “totally non-free actions”. These are measure-preserving actions of a group on a probability space in which almost all pairs of points have distinct stabilisers (if I have it right). In trying to find an example to think about to fix my ideas, I realised that the action of the full symmetric group of countable degree on the space of graphs on the countable vertex set has a stronger property, which I have known about for some time, and which I will describe here sometime soon, I hope.
  • Sergey Fomin talked about the fact that forbidding subtraction in arithmetic computations can make the number of operations required exponentially greater, even when the function can be calculated. Unsurprisingly, cluster algebras made a brief appearance,
  • Andrei Okounkov told a beautiful story about some formulae which arise in connection with box-packing in two and three dimensions. The former is equivalent to counting partitions, and according to Hardy and Ramanujan the number is the exponential of a constant times the square root of n; he explained the square root of n as the average boundary of a Young diagram with n boxes, and the constant as twice the square root of ζ(2), where ζ is the Riemann zeta-function; the celebrated ζ(3) occurs in the three-dimensional case. Then he threw out the mystifying remark that anyone meeting this for the first time wants to generalise to higher dimensions, but this is not possible because 2×(2+3) = 10, where the first 2 is the dimension of the complex numbers over the reals, and 10 is the dimension of string theory. I got distracted by this, and observed that 2×(22+32) = 26, which was the dimension of string theory in the early, fermionic versions; then 2×(23+33) = 70, whose significance is reflected in the fact that the sum of the first 24 squares is 70 squared, giving an embedding of the Leech lattice into the 26-dimensional spacetime; then 2×(24+34) = 194, a number whose significance in this game I don’t know – it is not the dimension of E7.5 (which is 190).
  • I mentioned Igor Frenkel’s talk on categorification in the preceding post. A very impressive cocktail of things from apparently different parts of mathematics.
  • Dmitry Shirokov gave a talk scheduled to be given by Victor Maslov on the foundations of classical thermodynamics, where they have no van der Waals forces but explain the phase transitions by clustering instead.
  • Yury Neretin talked about the diagonal action of the product of three copies of the finitary symmetric group, showing phenomena which don’t occur in the finite case: a parametrisation of the double cosets by diagrams, which give a combinatorial description of a topologically defined multiplication. I haven’t really got to grips with this yet.

You can find slides of my talk in the usual place.

St Petersburg

On Monday there was a party, at which various people gave eulogies about the birthday boy, and his daughter cut an amazing birthday cake. On Tuesday, he very generously took the foreign guests to a pie shop, a café where the speciality was pies (meat, cabbage, berry, and various other things), where we spent a congenial couple of hours. On Wednesday a leisurely boat trip in bright sunshine took us to the extraordinary conference banquet: walking home with Greg Cherlin through the white night was quite an experience. On Thursday there was a chamber music concert, featuring music by St Petersburg composers of the early eighteenth century, including Madonis (I didn’t catch the names of the others). Friday was the excursion, to Menshikov’s Grand Palace at Oranienbaum and then Peter the Great’s naval base at Kronstadt.

Kronstadt

On Saturday I was able to give my talk and attend all but the last talk of the conference, and still be back home in London well before the Underground closed for the night.

Posted in events, exposition, mathematics | Tagged , , , , | 5 Comments

Categorification, step 1

Today at the St Petersburg meeting, Igor Frenkel talked about categorification. He explained that there are five levels (maybe more!) and one has to take certain steps between them; he illustrated with an example, where level 0 was Jacobi’s Triple Product Identity and level 5 was four-dimensional quantum Yang–Mills.

He did say,

Forget about categorification if you don’t want to hear this word,

and it is certainly not an attractive word.

But I, like a stubborn mule, found myself unable to cross the Pons Asinorum from Level 0 to Level 1, since the landscape along the way was too attractive. I have some questions about this, which I will describe briefly here. I may try to write this out at greater length sometime.

Numbers and vector spaces

Step 1, in essence, consists in replacing numbers (non-negative integers) with vector spaces over a field, which is usually taken to be the field of complex numbers (but undoubtedly different things will happen over other fields). The number n is replaced by an n-dimensional vector space over C.

Addition and multiplication of numbers is replaced by direct sum and tensor product of vector space; the dimensions do indeed behave correctly.

An equation like ab+c = 0 is replaced by a short exact sequence

{0} → A → B → C → {0};

this means that the image of each map is equal to the kernel of the next. Again the dimensions behave correctly. But we see already that the process is not purely mechanical, since the reverse of the short exact sequence (which could be realised by maps of the dual spaces) may not be the thing that naturally occurs.

For example, Euler’s polyhedral formula (written in the form 1−V+EF+1 = 0) can be realised in this way: first orient the edges and faces of the polyhedron; now replace V,E,F by vector spaces of functions from vertices, edges and faces to C; and then use “coboundary maps” to make the sequence. (For example, from V to E, we replace a function f on vertices by a function df on edges, where df(v,w) = f(w)−f(v).) Now the proof of Euler’s formula becomes the proof of exactness of this sequence.

Formal power series

A formal power series ∑anxn has to be treated a bit differently. We cannot substitute a natural number for x, since all but the tamest such sequences have radius of convergence smaller than 1. But, as in combinatorial enumeration, we regard the powers of x as markers.

Thus, the interpretation of the series is a graded vector space ⊕An, where An is a vector space of dimension an.

Now direct sum or tensor product of graded vector spaces (with the usual conventions about grading, that is, the product of elements of degrees k and l has degree k+l), correspond to the sum or product of the formal power series.

Problem What if the graded vector space is actually a graded algebra?

In particular, the formal power series 1 and x corresponds to 1-dimensional vector spaces with degree 0 and 1 respectively.

Invariants

Let G be a finite permutation group on the set {1,…,n}. Then G has a natural action on a vector space V of dimension n, by permuting the vectors of a basis. An invariant of G is simply a vector fixed by G; such a vector must have coordinates which are constant on each G-orbit, and so the space of invariants of G (written VG) has dimension equal to the number of orbits of G. So we have taken the first step towards categorifying orbit-counting.

More generally, let W be a graded vector space. Then there is a natural action of G on the direct sum V = Wn of n copies of G. How do we “count” invariants here?

The answer lies in Pólya theory. Associated with G is a multivariate polynomial called the cycle index of G. This is the polynomial in indeterminates s1,…sn constructed as follows: for each element g of the group, having ci cycles of length i for each i, we form a monomial by raising si to the power ci, multiplying all these together; then sum these monomials over all group elements, and divide by the order of the group. This is denoted by Z(G).

Suppose that we have a collection of “figures”, each with a non-negative integer “weight”, so that there are only finitely many (say ai) figures of weight i for each i. The figures can be represented by a figure-counting series A(x) = ∑aixi. Now a “function” is a map from the set {1,…n} to the set of figures (essentially it puts a figure at every point of this set). G permutes the functions by moving their arguments. We are interested in counting the orbits of G on functions of given total weight (the sum of the weights of their values). If bi is the number of orbits, then the function-counting series is B(x) = ∑bixi.

Now Pólya’s Theorem asserts that B(x) is obtained from Z(G) by substituting A(xi) for si, for each i.

Now (I think), if we replace the figure-counting series by a graded vector space W, and let G act on the direct sum V of n copies of V, then the function-counting series corresponds to the space of invariants of G in V.

Of course, permutation actions are a special case of linear actions.

Problem. What happens for linear actions? Do we replace Pólya’s theorem by Molien’s?

Oligomorphic groups

A permutation group G on an infinite set is called oligomorphic if it has only finitely many (say an) orbits on the set of all n-element subsets of the permutation domain.

The definition of cycle index breaks down completely for oligomorphic permutation groups. However, one can define a modified cycle index for an oligomorphic group; this is obtained by taking orbit representatives for the orbits of G on the finite subsets of its domain, for each orbit representative take the cycle index of the finite group induced on this set by its setwise stabiliser in G, and then summing. It is easy to see that we obtain a formal power series in the infinitely many indeterminates s1,s2,….

A finite permutation group is a special case of an oligomorphic group; according to the Shift Theorem, its modified cycle index can be obtained from its ordinary cycle index by replacing si by si+1, for each i.

Many substitution results hold. For example, the power series ∑anxn is obtained from the modified cycle index by substituting xi for si, for each i. There are also rules for direct and wreath products.

There is at least the possibility of turning all this into graded vector spaces. Let Vi be the vector space of all functions from the set of G-orbits on i-sets to C, and V the graded vector space having these spaces as their homogeneous components. Then the vector space V “represents” the orbit-counting power series.

The vector space V has a natural algebra structure, which I won’t describe here. In fact, though results about the rate of growth of the numbers an tend to be proved by combinatorial methods (chiefly by Dugald Macpherson), I have had a small amount of success in proving smoothness results using algebraic methods, based on the fact that the multiplication in the algebra gives a map from VmVn to Vm+n.

Problem What are the vector space operations corresponding to direct and wreath product of oligomorphic groups?

Problem Is there a linear group analogue of oligomorphic permutation groups, for which a similar theory can be developed?

I think that is enough problems to be going on with!

Posted in exposition, open problems | Tagged , , , , , | 2 Comments