Mathematical Structures

My last major job at Queen Mary University of London more than ten years ago was designing and presenting a new first-semester first-year module to be taken by all students on mathematics programmes or joint programmes involving mathematics. I discussed it in my LMS-Gresham lecture.

Now QMUL have dropped this module, so there is no problem with posting it here. It is on the “Lecture notes” page.

Mathematicians will know this stuff already, but if you know someone who is about to start a mathematics degree, that person may find this of some use.

Posted in exposition, teaching | Tagged , | 4 Comments

What is the University doing?

A new semester is about to start. An exciting time, since this semester I will be teaching a new module on Set Theory and Logic (jointly with Nik Ruskuc). The tentative enrolment in this module has clearly justified the need for such a course, which I was already aware of: a number of students have asked to do projects or independent study modules with me, and I have been pressing my colleagues for some time to have such a module on the books.

But the excitement is rather spoiled by bureaucracy.

Room bookings are now done centrally. So for my Monday lectures, I have to go to the other end of St Andrews, more than ten minutes’ walk from my office (but more to the point, students who have a lecture in the previous hour in the Mathematical Institute have to do the same, so inevitably we will start late and lose some lecture time.

Normally I would put course material, including lecture notes, problems and solutions, and much more such as additional references, links to PhD studentships, and open problems, on a module web page. But as I have reported earlier, the University no longer allows such things. We have to use Moodle. After brief acquaintance with Moodle, I deeply loathe it. It is impossible to structure it like a web page; all you can do is throw everything in, and how the students are supposed to find their way around is a mystery.

The third gripe is lecture recordings. Even though all students are attending face-to-face, the University requires us to record the lectures. Since Rosemary starts at 9am on Monday, we went to a training session, and then tried out the kit in the room where she will be lecturing. (We couldn’t try the kit in the tutorial room since our colleagues who taught last semester are in the middle of exam boards and one was going on in the tutorial room.) Anyway, first the computer monitor was not working; we called our local IT people who had to reboot the computer to fix the problem. This is not something you want to do at the start of a 9am lecture! Then when we got the thing on, we found that the microphones were not working. They claimed to be working, but the sound on the recording was completely inaudible. IT services were informed. We checked again as we left to come home, to find that a colleague from Chemistry who has been assigned that room was trying out the kit and finding exactly the same problem.

I should say that I have not been able to check the kit in the room where I am lecturing on Monday, since the desks and tables are all piled up around the walls. I hope it will be returned to a usable configuration by Monday!

And finally, we used Teams in the past but the University is putting on pressure for us to use Panopto. Much as I dislike Teams, at least it reported by email when it had finished uploading the recording, and invited you to check it out. Panopto, according to the trainer in the session today, puts the recording in “your Panopto folder”, but neither he nor another IT person I asked could tell us where this folder is or how you can get to it.

I don’t like being uncooperative, but if they can’t answer these questions or get the kit working properly I shall not be making recordings.

The University has been piling on this nonsense lately. I am thinking that retirement is becoming more and more attractive an option. I would lose some money, and the University would lose the ability to count my papers for the next REF. Maybe they consider that a fair swap?

Posted in teaching | Tagged , , | 5 Comments

Two things that should be related

Here are two things that look as if there should be a relation between them.

A graph duality

In my paper on graphs defined on groups, I invented an ad hoc duality relation between pairs of graphs.

The context is that, in a little break from his PhD work, Saul Freedman had looked at the intersection graph of a finite group G, the graph whose vertices are the non-trivial proper subgroups of G, two subgroups joined if the subgroups have non-trivial intersection. This graph was first studied by Csákány and Pollák in 1969; they showed that, for a non-simple group G, if the graph is connected, its diameter is at most&nbs[;4. For simple groups, Shen proved in 2010 that the graph is connected, and asked for a bound on its diameter. Herzog, Longobardi and Maj gave a bound of 64, reduced to 28 by Ma. Saul was able to show that the correct upper bound for simple groups is 5, and that this bound is attained only by the Baby Monster and possibly certain unitary groups.

I was thinking about graphs such as the enhanced power graph, commuting graph, and non-generating graph at the time, and when I wrote the survey I realised that there was a connection.

Let Γ1 and Γ2 be graphs with no isolated vertices. I say that these graphs are dual if there is a bipartite graph B with bipartition (V1),V2)) such that, for i = 1,2, two vertices in Vi) are joined in Γi if and only if they have a common neighbour in B.

Now it is straightforward to see that, if Γ1 and Γ2 are dual, then there is a natural bijection between their connected components, and corresponding components have diameters differing by at most 1.

Question: What other properties are shared by dual pairs of graphs?

The relevance of this is that, for a group which is not cyclic of prime order, the non-generating graph is dual to the subgroup intersection graph. (We make a bipartite graph whose vertices are the non-identity elements and non-trivial proper subgroups, with adjacency being membership. Then two non-identity elements fail to generate the group if and only if they lie in a proper subgroup; and two non-identity proper subgroups have non-trivial intersection if and only if some non-identity element lies in both.

So Saul’s result is almost equivalent to a result on the diameter of the non-generating graph of a simple group.

But there is more. We can replace the subgroup intersection graph by the (usually much smaller) maximal subgroup intersection graph, and the duality still applies. (The number of subgroups of a group can be greater than polynomial in the group order, but the number of maximal subgroups cannot. According to Wall’s conjecture, the number of maximal subgroups is strictly less than the group order. This is now known to be false, but it is known to be bounded by c|G|3/2, and the true exponent is thought to be much lower.)

It is easy to see that the maximal subgroup intersection graph is also dual to the non-generating graph. So similar comments also apply.

There are further results of this sort. For example, if G is minimal non-abelian, then the (maximal) subgroup intersection graph is dual to the commuting graph. And so on.

This looks like it should be a potential unifying principle for results about graphs defined on groups and related graphs.

The zero-divisor graph of a poset

The research discussion on graphs and groups, run by Ambat Vijayakumar and Aparna Lakshmanan in Kochi, produced a cornucopia of ideas, results, and papers. Tamizh Chelvam told us about the zero-divisor graph of a commutative ring with identity, and then Vinayak Joshi told us about the zero-divisor graph of a poset with zero. He proposes this as a unifying principle for various graphs defined on algebraic structures.

Let P be a poset which has a unique minimal element 0. A non-zero element a of P is a zero-divisor if there exists a non-zero element b in P such that the only element below both a and b is 0. The zero-divisor graph of P has as vertices the zero-divisors, two elements a and b adjacent if they have the above relation.

Now among several examples of such graphs, we have the following:

  • The annihilating ideal graph of a commutative ring with identity is defined as follows: vertices are those annihilating ideals (ideals with non-zero annihilator) I for which there exists an annihilating ideal J with IJ = 0; adjacency of I and J is defined by this relation.
  • Let G be a finite group. Define a relation R on G by the rule that x and y are in the relation if y is a power of x. This is a partial preorder, that is, a reflexive and transitive relation; so the set of equivalence classes of the equivalence relation S (in which two elements are equivalent if each is a power of the other) is partially ordered by R. Extending R by an arbitrary total order on each equivalence class, we obtain a partial order on G, whose comparability graph is the power graph of G. Now take the reverse of this partial order, and introduce a new least element 0 below everything else. Two elements a and b have the property that only 0 lies below both if and only if there is no cyclic subgroup containing a and b. So the zero-divisor graph is the complement of the enhanced power graph of G.
  • Angsuman Das studied component graphs of finite vector spaces with a given basis. These turn out to be the joins of zero-divisor graphs of a lattice derived from the vector space with complete graphs.
  • Any graph Γ can be considered as a simplicial complex, whose elements are the empty set and the vertices and edges of the graph. We can regard this complex as a poset, and take the zero-divisor graph of it. If we adjoin the edges of Γ to this graph, we obtain a graph whose chromatic number is the total chromatic number of Γ.

A concept which includes four such different graphs as special cases is obviously a good candidate for a unifying principle. Moreover, any general results that can be proved about zero-divisor graphs of posets will contain as corollaries results about the three types of graph above.

In particular, it often happens (for example, in the second and fourth examples above) that the graph is weakly perfect, that is, has clique number equ al to chromatic number. A good start would be to prove this for posets under som e additional condition which would have these results as special cases.

Question: Can we connect the above theories of dual graphs and zero-divisor graphs of posets?

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


Portugal is one of my favourite countries in the world.

In large part this is due to my colleague and friend João Araújo, who arranged for me to visit Portugal for the first time in 2008, and on all of my many visits since, has taken me on “crazy trips” over much of the country; as well as the popular tourist attractions, I have seen things that most tourists never get to.

Last year, Rosemary’s nephew and partner had a holiday in Porto and the Douro valley. They asked me for recommendations for things to see. Since we didn’t have time for much discussion over Christmas, I wrote a little brochure about some of the highlights south of the Douro for them. I sent a copy to João, who corrected some historical errors (surprisingly few, since I wrote it without recourse to guidebooks, just occasional use of Google to check spelling), and encouraged me to go public with it.

So, with that seal of approval, here it is!

Posted in Uncategorized | Tagged , | 4 Comments

Happy new year

The world has been a bit crazy for several years. Let us hope for better times. I hope to have more mathematics to tell you about soon.

Posted in Uncategorized | 5 Comments

A theorem on polytopes

You know what polygons and polyhedra are. How do we extend their study to higher dimensions?

There are two parts to this question. The first involves incidence geometry: vertices, edges, faces, etc. Here the generalisation is fairly straightforward. A polygon has two types of objects, a polyhedron three; so for an r-dimensional polytope, we take objects of r possible types 0,1,…r−1, with incidence relations between different types satisfying certain conditions. (For convenience we take a single object of type −1 and one of type r incident with everything.)

In a polyhedron, an edge is incident with two vertices and two faces, which are incident with one another; and every vertex or face is contained in a triple of mutually incident objects called a maximal flag. We extend this: every set of mutually incident objects is contained in a maximal flag, having one object of each type. Moreover, a next-to-maximal flag, missing just one type of object, is contained in two maximal flags. Now, if a flag misses two types of object, then the objects of these two types indident with the flag form an incidence structure which is either a polygon (if the two missing types are adjacent) ir complete (if not). For example, in a polyhedron, the edges and faces containing a vertex form a combinatorial polygon; while vertices and faces incident with a common edge are incident with one another).

There are also connectedness conditions which I will not discuss.

I will also not discuss the metric properties (involving distances, angles, etc.) which make a polygon regular, but describe a different take on regularity.

Given a maximal flag F, there are exactly r maximal flags differing from it in just one position. All these are fixed by the stabiliser of F in the group of combinatorial automorphisms. So the order of the group does not exceed the number of maximal flags. We say that the polygon is regular if equality holds, which means that the group acts transitively (and regularly) on the set of maximal flags.

In a regular polygon, there is a unique element si mapping F to the flag Fi differing from it in position i only; it maps Fi back to F, so its square is the identity. Connectedness implies that these r elements generate the automorphism group. Moreover, if |ij|>1, then si and sj commute. So the automorphism group of a regular polytope is what is called a string C-group, which includes an intersection condition implying that the intersection of the subgroups generated by the involutions si for iI and for iJ is generated by those with iIJ.

Thus the search for regular polytopes “reduces” to the search for representations of a group as a string C-group; and a string C-group generating a group G determines a unique regulqr polytope up to isomorphism and duality.

The simplest family of regular polytopes to describe consists of the simplices (extending the sequence triangle, tetrahedron …). In this case the r generators are the adjacent transpositions in the symmetric group Sn, with n = r+1, occurring in the representation of this group as a Coxeter group of type An (discovered by E. H. Moore in 1896).

Maria Elisa Fernandes and Dimitri Leemans investigated regular polytopes with automorphism group Sn. They showed that there is only one of rank n−1 for n≥5 (the simplex), and, up to duality, only one of rank n−2 for n≥7. Moreover, there are examples of every possible rank from 1 to n−1.

Over the last several years, I have collaborated in work on regular polytopes, first with Dimitri, and then with Maria Elisa, on polytopes whose group is a (transitive) proper subgroup of Sn. We showed that these can have rank at most n/2+c. (For our strugle with the alternating groups, see here.) Now, exploiting these results and the techniques used in their proofs, we have shown what I think a remarkable theorem, proving a conjecture based on the first two results in the preceding paragraph and extensions of them.

Theorem. Suppose that n≥2κ+3. Then the number (up to isomorphism and duality) of regular polytopes of rank n−κ with group Sn depends only on κ, not on n.

(Thus these numbers can be computed by just computing these polytopes of rank r with group Sn with n=2r−3.) The numbers for κ = 1,2,… are 1, 1, 7, 9, 35, 48; we are computing the next number but it is a slow process.

I won’t begin to give the proof here; the paper is over 40 pages long and depends on results from our earlier papers and much else besides. I am very grateful to my coauthors for including me in the project. You can read the paper at . I will just say that, if the inequality between degree and rank holds, we show that there is a weak point in the diagram (called a “perfect split”) where one can insert a transposition to increase both degree and rank by 1.

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

The road closure property

My work with João Araújo and other semigroup theorists has produced a number of permutation group properties which lie between primitivity and 2-homogeneity, especially the synchronization family. Another of these is the road closure propery, which I have discussed here before. Last week, we had a workshop to try to understand this property.

Convento do Arrábida

The workshop was in the Convento do Arrábida, an old Franciscan monastery in a national park on the side of a mountain overlooking the sea, just south of Lisbon (on the tongue of land which ends at Cabo Espichel). A beautiful spot, although for the first three days of the workshop there was fog, rain and strong wind, so we had to wait for the stunning views. There was nothing to do but work, and work we did.

Let G be a permutation group on Ω. The orbital graphs for G are the graphs on the vertex set Ω whose edges are the orbits of G on 2-element subsets of Ω, thus one graph for each orbit. A permutation group is transitive if it fixes no subset of Ω except for Ω and the empty set, and is primitive if in addition it fixes no partition of Ω except the partition into singletons and the partition with a single part. According to a theorem of Donald Higman, G is primitive if and only if all its orbital graphs are connected. G is 2-homogeneous if it has just a single orbit on the 2-element subsets of Ω, that is, it has just one orbital graph which is the complete graph. So a 2-homogeneous group is primitive.

We say that G has the road closure property if, for any orbit O of G on 2-sets, and any proper block of imprimitivity B for the action of G on O, the graph with edge set O\B is connected. That is, if an orbital graph for G represents a road network, and if the roads in a block B are all closed for roadworks, it is still possible to travel around the network. It is clear that the road closure property implies primitivity. Also, the complete graph (on more than two vertices) cannot be disconnected by removing a block, since if it could then it would be the union of two disconnected graphs; so a 2-homogeneous group has the road closure property.

Why would anyone invent such a strange property? It turns out that it is motivated by semigroup theory. One very important class of semigroups consists of the idempotent-generated semigroups (an idempotent is an element equal to its square). Now we consider semigroups obtained by adding a non-permutation f to the group G and generating a semigroup ⟨G,f⟩, then removing the elements of G (since the only permutation which is an idempotent is the identity). We look for properties such as idempotent-generation for this semigroup, call it S (depending on G and f). Understanding such semigroups is the first step towards understanding all transformation semigroups having G as group of units, or normalizer.

Now it can be shown, fairly easily, that for a given group G,

S contains an idempotent for any choice of f of rank 2 if and only if G is primitive.

Furthermore, with a rather longer proof,

S is idempotent-generated for any choice of f of rank 2 if and only if G has the road closure property.

(The rank of a transformation is the size of its image.)

The gap between primitivity and the road closure property is not large; most primitive groups have the RCP (as I will call it). One example where it fails is provided by the non-basic groups. A primitive group G is non-basic if it is contained in a wreath product Sq wr Sm in its product action of degree qm. This can be said another way. The Hamming graph H(m,q) has as vertices the set of all words of length m over an alphabet of size q; two vertices are adjacent if the words differ in exactly one coordinate (in coding theory terms, they have Hamming distance 1). Now the automorphism group of the Hamming graph is the wreath product of symmetric groups mentioned above; so G is non-basic if it acts as a group of automorphisms of a Hamming graph. Now, in the Hamming graph, each edge has a direction, the number of the coordinate in which their vertices differ; the set of edges with a given direction is a block of imprimitivity, and if we remove the ith block, then we can no longer change the ith coordinate by moving along the remaining edges, so the graph is disconnected.

Now a primitive group G is basic if it is not non-basic; and the task of the road closure problem is to describe all basic primitive groups which fail to have the road closure property.

Here is an example, which ties in with our deliberations in Arrábida. Consider our old friend the Fano plane.

The Fano plane

Let G be the group of collineations and correlations (dualities) of this plane; this is a group of order 336 isomorphic to PGL(2,7). There are two primitive actions of G, on the 21 flags (the incident point-line pairs) and on the 28 antiflags (the non-incident point-line pairs). Both actions are basic (since their degrees are not proper powers); both fail the road closure property. This can be seen by similar arguments in each case, but there is a simple way to see both.

The orbital graphs are constructed similarly: the vertices are the flags (or antiflags); two vertices are joined if they share either a point or a line. Now construct a 7×7 array whose columns are indexed by the points and rows by the lines. Then G acts on this array with two orbits, the flags and the antiflags. Now it is easy to see that that, in each orbital graph, the horizontal and vertical edges form blocks of imprimitivity; and, just as in the non-basic case, removing a block disconnects both graphs.

According to the O’Nan–Scott Theorem, basic primitive groups are of one of three types: affine, diagonal and almost simple. Pablo Spiga, one of the participants in the workshop, has a proof that all basic affine groups have the RCP. We expect the same for diagonal groups. The problem, then, should reduce to considering almost simple groups, of which PGL(2,7) gives the smallest two examples.

A program written by Leonard Soicher, another participant, examined primitive groups of degree up to 4095 (the limit of the GAP library) and found that, in all cases where the stabilizer of a block contains the socle, there are just two blocks, as in this example. But we do have examples with three blocks. I mentioned one in the previous post; Pablo has another, of degree 6000, which may well be the smallest such. We have no examples with more than three blocks.

So a reasonable goal for the road closure program would be to show that there cannot be more than three blocks, and perhaps to classify the groups which have three blocks.

We cannot yet do that. But we have shown that, apart from cases where the block stabiliser contains the socle of the group, there are two other possibilities:

  • G is the symmetric or alternating group of degree m (the number of blocks), and the given action is of rather large degree (at least 2m);
  • Ω can be identified with a subset of the set of k-element subsets of {1,…,m}, and adjacent pairs of subsets meet in a constant number of points.

No examples are known for any of these cases, and we have further numerical information which hopefully will allow us to elimiate them.

But there was more.

As described above, the RCP is equivalent to the statement that, for every rank 2 map f, the semigroup S obtained by generating a semigroup with G and f and then removing G is idempotent generated. So the alternative name for the RCP is the 2-idempotent generated property, or 2-id for short. But of course we can define k-id for any k≥2, and ask for a list of such groups.

The first major step has already been taken. A permutation group G has the k-universal transversal property, or k-ut for short, if given any k-subset A and k-partition P of Ω, there is an element g of the group G which maps A to a transversal to P. This property is equivalent to the statement that the semigroup S contains an idempotent, and so is weaker than k-id. Now we have previously studied groups with k-ut; they are all known apart from some families and some sporadic groups where we have been unable to decide. So the problem is to investigate these groups and determine which (out of those which definitely or possibly have k-ut) have k-id. At the workshop, João Araújo and Wolfram Bentz made some significant progress on this question.

I should add here that, for the case of 2-id groups, we have a combinatorial property involving objects of size polynomial in n which is equivalent, namely the RCP. This is lacking for higher values of k, and it is difficult for someone like me to understand exactly what makes the semigroup S idempotent-generated. Fortunately, negative results can be obtained by making a good guess about the k-partition to test, without needing to test them all.

In conclusion, we had a week in a stunningly beautiful place. The food was absolutely outstanding; Portuguese cuisine at its best. The weather was a mixed blessing but at least kept us to the task. And the facilities were adequate, apart from rather limited access to wi-fi (this is good and bad: like the weather it took away distractions, but it also made it difficult to look up previous results). So many thanks to João for organising a memorable occasion. I should not let this post conclude without mention of Gavril Farkas, who had come because he is interested in monodromy groups of covers of surfaces; both primitivity and 2-transitivity have natural interpretations in this context, and he was looking for intermediate properties which might have similar interpretations.

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

A warning

I have just learned that I am losing my personal webpages at St Andrews,

I know people have found some of this material useful. I will try to make it available in some other form, though this may have to be at my own expense.

Feel free to write to the university to complain.

Posted in the Web, Uncategorized | 7 Comments

COBS and equitable partitions

It happens sometimes that researchers working in different fields study the same thing, give it different names, and don’t realise that there is further work on the subject somewhere else. Here is a story of such a situation, which arose indirectly from the work Rosemary and I were doing with statisticians in Covilhã, Portugal, namely Dário and Sandra Ferreira and Célia Nunes.

I begin with the statistics. We are designing an experiment to test a number of different “treatments” (fertilizers, drugs, or whatever). We have a number of experimental units available: these may be plots of land, fruit trees, human or animal subjects, etc. For brevity I will call them “plots”.

The design for the experiment is a function from the set of plots to the set of treatments, giving the treatment to be applied to each plot.

The simplest case is where the plots are all alike, apart from small random variations. In this case there is no restriction on how we choose the design function; for efficiency (meaning small variance of estimators of treatment differences) we should apply each treatment the same number of times, or if this is not possible, choose the numbers of occurrences to differ by at most one.

But in practice things may be more complicated. The plots may differ on a number of factors, each corresponding to a partition of the set of plots. For example, an agricultural experiment may use several plots on each of a number of farms in different parts of the world; plots on the same farm will be more similar than plots on different farms, and analysis of the experiment should take this into consideration. The plots are partitioned into “blocks”, one for each farm.

Indeed, there may be several such partitions. In an experiment on fruit trees, the trees in an orchard may be arranged in a rectangular array, and may have been used for an experiment last year; then the rows, columns, and earlier treatments all form significant partitions. In an experiment on animal feed, the animals may be divided into pens, a number of pens on each of several farms. In a clinical trial, the gender of the subject and the hospital at which they are treated may be relevant.

Thus we have to consider “plot structure”, usually (as above) defined by a collection of partitions of the set of plots. It is convenient of the partitions satisfy some conditions: each should have all parts of the same size; if possible, any two should be “orthogonal”, meaning that they intersect proportionally; and perhaps the set of partitions should be closed under meet and join and contain the two trivial partitions (the partition with a single part and the partition into singletons). Such a plot structure is called an orthogonal block structure, or OBS for short.

The plot structure is given; the experimenter has no control over it. All that she can control is the design function.

The result of the experiment will typically be a real number measured on each plot, that is, an element of the real vector space V of functions from the set of plots to the real numbers. In this vector space, each partition of the set of plots is represented by a subspace of V, consisting of functions which are constant on each part of the corresponding projection. There is a natural inner product on V (the characteristic functions of singletons forming an orthonormal basis), and so there is an orthogonal projection onto the space corresponding to any partition: this has the effect of averaging the function over each part of the partition.

Even if the plot structure is not completely described by partitions, it may still be the case that it gives rise to a collection of linear maps on V. For example, if the plots lie in a circle, there may be a neighbour effect, and we could consider the adjacency matrix of the cycle graph.

Statisticians introduced a helpful notion here, that of a commutative orthogonal block structure, or COBS for short. Noting that the design function allocating treatments to plots corresponds to another partition of the set of plots (where plots getting the same treatment lie in the same part), they argued that it is helpful if the orthogonal projection onto the treatment subspace commutes with the matrices arising from the plot structure. They call such a set-up a commutative orthogonal block structure, or COBS.

Now we leave statistics for a while and turn to graph theory.

Let Γ be a graph, and Δ a partition of its vertex set with parts P1, … Pr. Then Δ is said to be equitable if there is a r×r matrix M such that, for any i,j, the number mij of vertices of Pj joined to a given vertex in Pi depends only on i and j, and not on the chosen vertex. Among the various consequences of this definition, I mention just one: The matrix M is the restriction of the adjacency matrix of the graph to the subspace consisting of functions constant on the parts of Δ; so this subspace is invariant under the adjacency matrix of the graph, and moreover, the minimal polynomial of the matrix M divides that of the adjacency matrix of the graph, so that its eigenvalues are among those of the adjacency matrix.

Equitable partitions occur widely in finite geometry and combinatorics; among geometrix examples, one could mention ovoids in projective spaces. Also, it is clear that the orbit partition of any group of automorphisms of the graph forms an equitable partition of its vertex set.

Once one suspects that there is a connection between COBS and equitable partitions, it soon becomes clear what theorem needs to be proved to connect them. It is the following, whose proof is straightforward once we have decided what is needed.

Theorem A partition Δ is equitable for a graph Γ if and only if the projection matrix onto the subspace of functions constant on parts of Δ commutes with the adjacency matrix of Γ.

A simple consequence of this theorem (not immediately obvious) is that, if the graph Γ is distance-regular, then an equitable partition of Γ is also equitable for the distance-i graph of Γ, for all i up to the diameter of the graph. For distance-regularity means that the distance-i graphs have adjacency matrices which are polynomials in the adjacency matrix of Γ so any matrix which commutes with the adjacency matrix of Γ commutes with the adjacency matrices of all distance-i graphs.

The work we were doing in Covilhã concerned COBS for the half-diallel, a genetic term referring to the situation where the genome of an individual comes from two parents but there is no distinction in their role. Designs for such experiments could also be applied to the situation where an experimental unit consists of a pair of individuals from a population. This might, for example, involve comparing the efficiency of various communication methods (face-to-face, telephone, video call, email, etc.). Thus a COBS for such an experiment is an equitable partition of the triangular graph, whose vertices are the 2-element subsets of the set of individuals, two vertices joined if the subsets have non-empty intersection.

My earlier foray into equitable partitions, with Rosemary Bailey, Sasha Gavrilyuk and Sergei Goryainov, involved Latin square graphs; this could be applied in the situation of an n×n array of fruit trees where last year an experiment in the form of a Latin square was done on the trees.

So how did we come to realise the connection? It happened like this. Rosemary was working on a classification of the COBS for the triangular association scheme. I noticed that what she was doing had a superficial resemblance to what she had done on equitable partitions of Latin square graphs on a plane returning from China a few years ago. As said above, once you suspect that a connection exists, it is fairly straightforward to see what it is and to prove the required theorem.

Posted in doing mathematics | Tagged , , , , , | 1 Comment

An apology

What would life be like if I could remember all the things I ever knew?

Yesterday I was led to something I posted here twelve years ago. This was based on a talk to the London Algebra Colloquium by Mark Wildon.

He told us about results he had proved using Jordan’s theorem – this is the theorem of Jordan which gave me my fifteen minutes of fame when Jean-Pierre Serre talked about it at Queen Mary – on the existence of derangements in finite transitive permutation groups. Mark applied this to show the following, though he didn’t phrase it in these terms.

The conjugacy supercommuting graph on a group G is the graph whose vertex set is G, with an edge from x to y if there are conjugates of x and y which commute. Mark’s theorem asserted that an element of G is joined to all others if and only if it belongs to the centre of G. As a corollary, the graph is complete if and only if G is abelian.

These results form parts of theorems 4 and 5 in my paper with G. Arunkumar, Rajat Kanti Nath, and Lavanya Selvaganesh on “Super graphs on groups”, described here and now published in Graphs and Combinatorics. Our proof is the same as Mark’s.

We apologise to Mark for not attributing the result to him, and are happy to do so now.

Posted in doing mathematics | Tagged , , | 4 Comments