Combinatorial Theory

I learned yesterday of a new free and open-access journal, Combinatorial Theory, owned by its editorial board. There is a temporary web page here, on which the editorial board (including some familiar names) is listed. This journal joins a list headed by the Electronic Journal of Combinatorics (more than a quarter of a century old), and including also the Australasian Journal of Combinatorics and Algebraic Combinatorics, along with many in other fields.

More information can be found on the FPSAC website here. This is a letter from Victor Reiner announcing that the new journal is to be regarded as the successor of the Elsevier publication Journal of Combinatorial Theory (A). Since I am in favour of free open-access journals owned by the editorial board, I welcome the new journal. On the other hand, I don’t want to disparage JCT(A), but merely note that the last couple of papers I published there have had almost no citations (9 and 6 respectively, according to Google Scholar which is not prone to undercounting).

Paying page charges (sorry, APCs) to major publishers with large profit margins has always seemed to me uncomfortably close to vanity publishing, where authors desperate to see their work in print are prepared to pay unscrupulous publishers. Of course, it is very difficult to occupy the high moral ground now, when publishers offer universities package deals including open-access publishing (but you can be sure that somebody is paying them, money which might be better spent supporting young scholars starting out).

Posted in publishing | Tagged , , | 3 Comments

The Fitting subgroup

I have talked a bit about the Frattini subgroup. Time for its big brother.

The definition of the Fitting subgroup F(G) of a finite group G is the unique maximal normal nilpotent subgroup of G. As such, of course, it contains the Frattini subgroup Φ(G). (I showed here the Frattini argument used to prove its nilpotence.)

But wait a minute, that definition makes no sense until you have proved that the object in question exists. I learned this proof as a student; I can remember that it seemed to me to be more complicated than you would expect, but I cannot remember how it went.

So here is a simple proof, using nothing more than Sylow’s theorem. Since Sylow’s theorem is the most important theorem about finite groups, this is entirely fitting.

We need also the fact that a finite group is nilpotent if and only if it has a unique Sylow p-subgroup for each prime p. This is the same property I used for the Frattini subgroup. You can, if you wish, use it as a definition of nilpotence for finite groups. In the end you don’t escape the work, since this won’t do for infinite groups, so you have to come to terms with central series. But it will do as a working definition here.

The key lemma is the following:

If A and B are normal nilpotent subgroups of G, then AB is a normal nilpotent subgroup of G.

Given this, it is clear that the product of all the normal nilpotent subgroups is the required unique maximal one.

So let A and B be as given. It is elementary that AB is a normal subgroup of G. Also, |AB| = |A|.|B|/|AB|.

Choose a prime p, and let R be a Sylow p-subgroup of AB. By Sylow’s theorem, R is contained in a Sylow p-subgroup P of A, and in a Sylow p-subgroup Q of B. Moreover, PQ = R, since there is no larger p-subgroup in AB.

Now P is the unique Sylow p-subgroup of A, and so is characteristic in A, and thus normal in G. Similarly Q is normal in G. So PQ is a normal subgroup of G, and its order is |P|.|Q|/|PQ|. Comparing the equations for |AB| and |PQ|, we see that the latter is the p-part of the former; so PQ is a normal (and hence unique) Sylow p-subgroup of AB.

Since this holds for all primes p, AB is nilpotent.

Posted in exposition | Tagged , , , | 3 Comments

Groups and graphs

Two new preprints have appeared on the arXiv (2008.09291 and 2009.02884), about which I would like to say something. One is by Saul Freedman, the other by him and two co-authors (his PhD supervisors).

The intersection graph of a group G is the graph whose vertices are the proper non-trivial subgroups of G, two vertices joined if they have non-trivial intersection. (Here, as usual, the trivial subgroup of any group is the subgroup whose only element is the identity of the group. For obvious reasons we exclude the cyclic groups of prime order.) The history of this graph is explained in the preprint on the arXiv. It was defined by Csákány and Pollák in 1964; they determined the non-simple groups for which it is disconnected, and proved that if it is connected (for non-simple G), then its diameter is at most 4.

What about simple groups?

In 2010, Shen proved that the the intersection graph is connected and asked for an upper bound on the diameter. In the same year Herzog, Longobardi and Maj gave a bound of 64. This was reduced to 28 by Ma in 2016. Meanwhile Shasavari and Khosravi gave a lower boud of 3.

Now Saul has reduced the upper bound to 5; shown that this is best possible (the intersection graph of the Baby Monster has diameter 5, the distance 5 realised by two subgroups of order 47), and shown moreover that any other simple group whose intersection graph has diameter 5 must be a simple unitary group of odd prime degree. There exist unitary groups where the diameter is 5, and others where it is 4; we do not currenly have a complete classification.

So let me interpolate a question here which is relevant to this and may be interesting to finite geometers. The classical unital U(q), for a prime power q, has q3+1 points, and the unitary group PGU(3,q) acts on it 2-transitively. This group has a cyclic subgroup of order q2q+1, which acts with q+1 regular orbits. Is the following true? If O is one of these orbits, and g is any element of PGU(3,q), then O and Og have non-empty intersection.

The other paper turns to territory more familiar to me. Consider the following graphs whose vertices are the non-identity elements of a group G:

  • the power graph, with x joined to y if one is a power of the other;
  • the enhanced power graph, with x joined to y if both are powers of an element z;
  • the commuting graph, with x joined to y if xy = yx;
  • the non-generating graph, with x joined to y if x and y do not generate G;
  • the complete graph, with all pairs adjacent.

Each graph is a spanning subgraph of the following one, except possibly for the third and fourth, for which this holds if G is non-abelian.

When can it happen that two consecutive graphs on this list coincide? For the first and second, and for the second and third, this question was answered in a paper I wrote with Ghodratollah Aalipour, Saieed Akbari, Reza Nikandish, and Farzad Shaveisi in 2017, using classical results of Frobenius, Burnside, Zassenhaus, and Gruenberg and Kegel, among others. For non-abelian G, the third and fourth are equal if and only if G is minimal non-abelian (all proper subgroups abelian); these groups were classified back in 1903 by Miller and Moreno. The last pair are equal if and only if G cannot be generated by two elements.

The next question one might ask about this hierarchy (assuming G non-abelian) is whether successive differences are connected, and what can be said about the diameter of connected components. For the last pair, the difference is the generating graph of the group, in which two vertices are joined if together they generate the group. This graph has received a lot of attention, not least from Scott Harper (a St Andrews graduate); a recent theorem of his with Tim Burness and Robert Guralnick shows that if G is finite and all proper quotients of G are cyclic, then the generating graph has diameter 2 (arXiv 2006.01421).

The next difference is the so-called non-generating, non-commuting graph; this is the graph considered in Saul’s other preprint. I won’t describe here the results (which chiefly concern connectedness and diameter in the case where G is nilpotent, though there is much more in Saul’s thesis), since I want to add some further comments to the general set-up.

Firstly, after examining connectedness and diameter, one could ask questions such as Hamiltonicity, clique size, chromatic number, domination number, and so forth. However, for the first two “difference graphs”, even the question of connectedness is open. (The connectedness of the commuting graph has been much studied, but this is the edge-union of the first three of the difference graphs.)

A second comment is that, if G is non-abelian and 2-generated, then we have partitioned the complete graph on the non-identity elements of G into (at most) five parts. What happens if we run the Weisfeiler–Leman algorithm on this partition, to find the coarsest coherent configuration refining it?

For the final comment, note that in the enhanced power graph, two vertices are joined if and only if they generate a cyclic group; in the commuting graph, if and only if they generate an abelian group; and in the non-generating graph, if and only if they generate a proper subgroup. This inevitably suggests many further graphs, defined by imposing an appropriate condition on the subgroup generated by the two elements, either intrinsic (e.g. nilpotent or soluble) or with relation to the whole group. This opens a large number of problems. Are any of them interesting? Perhaps the best way to find out is to study them and see!

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

On the Frattini subgroup

I wrote earlier about the Frattini subgroup of a group. It can be defined in either of two ways (as the set of non-generators of a group, the elements which can be dropped from any generating set containing them; or as the intersection of all the maximal subgroups), and the proof that it is nilpotent is a good illustration of the Frattini argument.

As you will see from the preceding post, I have been thinking about the Frattini subgroup recently. What I propose to do here is to tell you something about it which I don’t recall meeting when I was a student (and so perhaps you didn’t either), and also to throw some light on two other things: how research is done, and how mathematics was written a century ago.

In the course of what I was doing, I began to wonder whether the Frattini subgroup of the direct product G×H is the direct product of the Frattini subgroups of G and H. GAP confirmed that this was so in a couple of examples. In the past, I would have had to go to the library and look through books, and probably lug huge volumes of Mathematical Reviews down from the shelves. Now I can’t go to the library, but I do have the internet. So I googled the question. I found a fairly recent paper determining exactly when this holds, for arbitrary (possibly infinite) direct products of arbitrary (possibly infinite) groups. In the bibliography was a paper by G. A. Miller from 1915 which, it was claimed, proved the result for finite direct products of finite groups.

The paper was in the Transactions of the American Mathematical Society, long enough ago that it is freely available, so I downloaded a copy. It is only seven pages long, but does not contain a single theorem; it just consists of text, with a few important points italicised. A quick glance didn’t lead me to the theorem quoted, although he deals with the Frattini subgroup of a Sylow subgroup of the symmetric group, so has to handle direct products.

This is how mathematics was done in those days. I think the change in style was not too abrupt; in Burnside’s book, he often rambles on for several pages, but at least he states a theorem at the end of his ramblings. I think that today we would not allow our students to write like that, and journals would not accept our papers if we did it ourselves.

So I had to prove it for myself, to be sure it was right. I will also explain why finiteness of the groups is needed.

I will use the definition as intersection of maximal subgroups, though Miller uses the other definition of the Frattini subgroup.

Consider G×H. If A is a maximal subgroup of G, then A×H is a maximal subgroup of G×H; the intersection of all these is Φ(GH. Similarly the other way around. So certainly Φ(G)×Φ(H) is an intersection of some maximal subgroups, so contains Φ(G×H). We have to show that intersecting this with other maximal subgroups does not make it any smaller.

So we have to think about arbitrary maximal subgroups of a direct product G×H. In fact, it is known (I did learn this as a student) that all subgroups of the direct product are produced in the following way. Let A and C be subgroups of G, with A a normal subgroup of C; and similarly B and D in H. Suppose that the factor groups C/A and D/B are isomorphic; let α be an isomorphism between them. Now consider the set of all pairs (g,h) in G×H such that gC, hD, and (Ag)α = Bh. This is a subgroup, and every subgroup has this form.

It is easy to see that, in order for the subgroup in the previous paragraph to be maximal, we have to have C = G, D = H, and the isomorphic quotients G/A and H/B simple.

Now we can see why the formula for the Frattini subgroup of a direct product can fail for infinite groups. Let G be an infinite simple group which has no maximal subgroups. Then Φ(G) = G. But G×G has a diagonal subgroup consisting of all (g,gα) for gG, which is maximal; so Φ(G×G) is not equal to G×G.

But the Frattini subgroup of a finite simple group G is trivial; for every finite group has a maximal subgroup, so its Frattini subgroup is proper, and it is normal, so is trivial if G is simple.

Thus, for a maximal subgroup of the type we are considering, A contains Φ(G) and B contains Φ(H), so our maximal subgroup contains Φ(G)×Φ(H), as required.

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

Surprising fun fact

I have just found a proof of the following. Usual caveat: nobody else has read the proof yet, and I have not carefully checked it.

Let G be a finite group. The finite group H will be called an inverse Frattini group of G if G is isomorphic to the Frattini subgroup of H. As the climax of a series of papers going back to Gaschütz, Bettina Eick proved a beautiful theorem: G has an inverse Frattini group if and only if the inner automorphism group of G is contained in the Frattini subgroup of the automorphism group of G.

Now here is my new fact.

For a positive integer n, the following are equivalent:

  • every group of order n has an inverse Frattini group;
  • every group of order n is abelian.

It is certainly not true that a group has an inverse Frattini group if and only if it is abelian!

Part of the proof involves showing that, for every prime number p and positive integer m ≥ 3, there is a group of order pm which has no inverse Frattini group. This is true, but computational evidence suggests that much more is true; I conjecture that the proportion of groups of order pm with no inverse Frattini group tends to 1 as m tends to infinity, for fixed p. Here are the proportions for p = 2, m = 3,…,8: 0.4, 0.5, 0.62745…, 0.74906…, 0.87715…, 0.96213….

Posted in doing mathematics | Tagged , | 2 Comments

Integrals of groups revisited

After my trip to Florence in February, I wrote about the work I did there with Carlo Casolo and Francesco Matucci.

After Carlo’s untimely death the following month, we were left with many pages of notes from him about the work he had done on the problem during my visit and subsequently.

Our job, then, was to distil these notes into a paper and publish it in his memory.

It has taken a while to do this, but the resulting paper has just appeared on the arXiv. I won’t go through it blow by blow, but I would like to draw attention to two things about it, one major and the other rather smaller.

Let me remind you that we use the term “integral of a group G” to mean a group H whose derived group (generated by all commutators) is isomorphic to G. Every abelian group is integrable, but we were concerned in our first paper with the smallest integral of a given abelian group. In particular, if G is an infinite abelian group, does it have an integral in which it has finite index?

Carlo had put a lot of effort into this question, and had come up with, not a complete solution, but something close to it, at least in the case of a countable torsion abelian group. Unfortunately, his argument depended quite heavily on an “obvious” result from linear algebra. We had trouble with this, and spent a long time trying to come up with a proof. In the end, trying to track down where the proof attempts failed, I came up with a counterexample. Then, of course, the failure of this lemma brought down a lot of the beautiful arguments that followed from it.

I think that much of what Carlo did will prove to be correct, but a different approach needs to be found. So we simply took out everything depending on the lemma. (The paper is still a very solid 40 pages without this material.)

So I will state a very special case of this analysis. A proof of this would hopefully open the door to restoring much of the rest. I state it as a conjecture, though it was a corollary of a big theorem in Carlo’s notes.

Conjecture Let G be a countable group which is a direct product of finite cyclic groups. Then G has finite index in some integral if and only if the number of even positive integers n for which the cyclic group of order n occurs with multiplicity 1 in the product is finite.

The other matter is the solution of one of the problems in our earlier paper by Efthymios Sofos, from Glasgow. We had characterised the set of positive integers n for which every finite group of order n is integrable, and asked for the asymptotics of the number of such n up to x, for any x. It turns out that the leading asymptotics of this number is the same as for various similar-looking sets, “every group of order n is cyclic” (this was done by Paul Erdős in 1948), “every group of order n is abelian”, or “every group of order n is nilpotent”. The answer is

e−γ x/log log log x,

where γ is the Euler–Mascheroni constant.

There is much more in the paper; take a look.

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


In the last week of August, I attended for the first time a virtual conference. This was the 2020 Ural Workshop on Group Theory and Combinatorics, organised by Natalia Maslova at the Ural Federal University in Yekaterinburg and her colleagues. The conference was held as a Zoom meeting, and ran with only one hitch. As fate would have it, it was Natalia’s talk that was disrupted by a technological failure, so she started ten minutes late and had to talk fast. My co-author and St Andrews student Liam Stott was talking in the other parallel session immediately afterwards, so I switched as quickly as I could, only to find that the chair of that session had started him early (I assume the previous speaker hadn’t shown up), and he was three-quarters of the way through his talk already. Fortunately I knew what he was talking about!

Yekaterinburg is four hours ahead of St Andrews, so we had a week of very early rising; we had lunch at 10am, and were finished for the day (in both senses) by 2pm most days.

There were some very enjoyable talks, and as usual I can only mention a few. Cheryl Praeger talked about totally 2-closed finite groups. A permutation group G is 2-closed if every permutation preserving all the G-orbits on ordered pairs belongs to G. Cheryl and her colleagues call an abstract group 2-closed if every faithful transitive permutation representation of it is 2-closed. These groups were first studied by Abdollahi and Arezoomand, who found all nilpotent examples; with Tracey they subsequently found all soluble examples. Now this team augmented by Cheryl has considered insoluble groups. At first they found none, but they found that in fact six of the 26 sporadic simple groups (the first, third and fourth Janko groups, Lyons group, Thompson group, and Monster) are totally 2-closed. Work continues.

We had a couple of plenary talks about axial algebras; Sergey Shpectorov and Alexey Staroletov explained what these things (generalised from the Griess algebra for the Monster) are, and what the current status of their study is.

Greenberg’s Theorem states that any finite or countable group can be realised as the automorphism group of a Riemann surface, compact if and only if the group is finite. Gareth Jones talked about this. The proof, he says, is very complicated. He gave a new and much simpler proof; it did less than Greenberg’s Theorem in that it only works for finitely generated groups, but more in that the Riemann surface constructed is a complex algebraic curve over an algebraic number field.

Misha Volkov gave a beautiful talk about synchronizing automata. He began with the basic stuff around the Černý conjecture, which I have discussed before, but added a couple of things which were new to me: a YouTube video of a finite automaton taking randomly oriented plastic bottles on a conveyor belt in a factory and turning them upright; and the historical fact that the polynomial-time algorithm for testing synchronization was in the PhD thesis of Chinese mathematician Chung Laung Liu (also transliterated as Jiong Lang Liu), two years before the Černý conjecture was announced. Then he turned to new results, and showed that, with only tiny changes (allowing the automaton to have no transition for some state-symbol pair, or restricting the inputs from arbitrary words to words in a regular language) the synchronization problem can jump up from polynomial to PSPACE-complete!

Alexander Perepechko gave a remarkable talk, connecting the Thompson group T, the Farey series, automorphism groups of some affine algebraic surfaces, and Markov triples, solutions in natural numbers to the Diophantine equation x2+y2+z2 = 3xyz. (There is a long-standing conjecture that a natural number occurs at most once as the greatest element in some such triple. The sequence of such numbers begins 1, 2, 5, 13, 29, 34, 89, …. I will not attempt to explain further.)

Rosemary became the fourth author of the “diagonal structures” quartet to talk about that work, which I discussed here. She concentrated on the heart of the proof, the first place in the work where the remarkable appearance of algebraic structure (a group) from combinatorial (a Latin cube with a mild extra hypothesis) appears. Without actually describing how the hard proof goes, she explained the context and ideas clearly. I think this ranks among my best work; and all I did, apart from the induction proof of which Latin cubes form the base, was to insist to my co-authors that a result like this might just be possible, and we should go after it.

One of my early heroes in group theory was Helmut Wielandt; his book on permutation groups was my first reading as a graduate student. Danila Revin gave us a Wielandt-inspired talk. Wielandt had asked, in Tübingen lectures in the winter of 1963-4, about maximal X-subgroups of a group G, where X is a complete class of finite groups (closed under subgroups, quotients and extensions). Let kX(G) be the number of conjugacy classes of maximal X-subgroups of G, Wielandt said that the reduction X-theorem holds for the pair (G,N) if kX(G/N) =  kX(G), and holds for a group A if it holds for (G,N) whenever G/N is isomorphic to A. Wielandt asked for all A, and then all pairs (G,N), for which this is true; this is the problem which Danila and his co-authors have now solved.

(I hope Danila will forgive me an anecdote here. At an Oberwolfach meeting in the 1970s, one of the speakers told us a theorem which took more than a page to state. Wielandt remarked that you shouldn’t prove theorems that take more than a page to state. Yet the solution to his own problem took nearly ten pages to state. I think this is inevitable, and simply teaches us that finite group theory is more complicated than we might have expected, and certainly more complicated than Michael Atiyah expected. Indeed, in the very next talk, Chris Parker told us about work he and his colleagues have done on subgroups analogous to minimal parabolic subgroups in arbitrary groups. This is intended as a contribution to revising the Classification of Finite Simple Groups, and they hoped to show that with an appropriate list of properties only minimal parabolics in groups of Lie type and a few other configurations could arise; they obtained the full list and were rather dismayed by its length, which would make the applications they had in mind very difficult.)

Among other fun facts, I learned that the graph consisting of a triangle with a pendant vertex is called the paw in Yekaterinburg, but is the balalaika in Novosibirsk.

On the last day of the seven-day meeting, we had two talks on dual Seidel switching, by Vladislav Kabanov and Elena Konstantinova, who were using it and a more general operation to construct new Deza graphs and integral graphs.

After a problem session, the conference ended by a virtual tour of Yekaterinburg (or Sverdlovsk, as it was in Soviet times), covering the history, architecture and economics, and illustrated by photographs and historical documents; the tour guide was Vladislav’s daughter.

Life was made more difficult and stressful for me because I was doing something which would have been completely impossible in pre-COVID times: I spent some time moonlighting from the Urals conference to attend ALGOS (ALgebras, Graphs and Ordered Sets) in Nancy, France, a meeting to celebrate the 75th birthday of Maurice Pouzet, which I didn’t want to miss. Many friends from a different side of my mathematical interests were there; as well as Maurice himself, Stéphan Thomassé, Nicolas Thiéry, Robert Woodrow, Norbert Sauer, and many others.

The three hours’ time difference between Yekaterinburg and Nancy meant that there was not too much overlap between the two meetings, so although I missed most of the contributed talks in Nancy, I heard most of the plenaries.

Stéphan Thomassé talked about twin-width, a new graph parameter with very nice properties. Given a graph, you can identify vertices which are twins (same neighbours) or nearly twins; in the latter case, there are bad edges joined to only one of the two vertices; the twin-width is the maximum valency of the graph of bad edges. Bounded twin-width implies bounded treewidth (for example) but not conversely; a grid has twin-width 4. Graphs with bounded twin-width form a small class (at most exponentially many of them), and, remarkably, it is conjectured that a converse also holds.

Jarik Nešetřil and Honza Hubička talked about EPPA and big Ramsey degrees respectively; I had heard these nice talks in Prague at the MCW, but it was very nice to hear them again.

Norbert Sauer talked about indivisibility properties for permutation groups of countable degree. I might say something about this later if I can get my head around it, but this may take some time. In particular, Norbert attributed a lemma and an example to me, in such a way that I was not entirely sure what it was that I was supposed to have proved! (My fault, not his – it was the end of a long day!)

Nicolas Thiéry gave a very nice talk on the profile of a countable relational structure (the function counting isomorphism types of n-element induced substructures), something to which Maurice Pouzet (and I) have given much attention, and on which there has recently been a lot of progress. (I discussed some of this progress here, but there has been more progress since.) In particular, structures whose growth is polynomially bounded are now understood, due to Justine Falque’s work, and for primitive permutation groups there is a gap from the all-1 sequence up to growth 2n/p(n), where p is a polynomial, thanks to Pierre Simon and Sam Braunfeld.

Unfortunately the conference was running on BigBlueButton, some conference-enabling software which I had not encountered before but which is apparently popular in France. I am afraid that it was simply not up to the job. The second day of the conference saw some talks and sessions abandoned, because speakers could not connect; I could sometimes not see the slides at all, and the sound quality was terrible. I discovered that one is recommended to use Chrome rather than Firefox, and indeed it did work a little better for me, but not free of problems. On this showing I would not recommend this system to anyone.

In particular, a beautiful talk by Joris van der Hoeven was mostly lost for me. I couldn’t see the slides. Joris’ explanations were perfectly clear, even without the visuals, but sometimes I lost his voice as well. The talk was about the connections between different infinite systems: ordinals, Hardy fields, and surreal numbers. In better circumstances I would have really enjoyed the talk.

I hasten to add that the problems were completely ouside the control of Miguel Couceiro, the organiser, and marred what would have been a beautiful meeting.

Posted in events | Tagged , , , , , , , , , , , , , , , , , , | 6 Comments

A problem

I seem to have too many balls in the air at the moment. So let me drop one here. Any thoughts very welcome.

A k-hypergraph consists of a set X of vertices and a collection of k-element subsets called edges. It is k-partite if there is a partition of the vertices into k parts so that every edge is a transversal to this partition, which I will call a k-partition.

Clearly there is a tension between edges and k-partitions; you would expect that more k-partitions would imply fewer edges. In one special case this is true. The existence of a second k-partition implies the existence of two vertices x,y which lie in the same part of one of the k-partitions and different parts of the other; then no edge can contain x and y.

My conjecture is very specific:

Suppose that the k-hypergraph on n vertices has at least kr k-partitions, for some positive integer r. Then there is a k-partite k-hypergraph H1 on n−r vertices which has at least as many edges as H.

The hypotheses are not pulled out of the air. Adding an isolated vertex v to a k-partite k-hypergraph multiplies the number of k-partitions by k, since v can be added to any one of the parts. So the conjecture is true if the hypergraph has r isolated vertices.

The conjecture is true if k = 2. For a connected bipartite graph has a unique bipartition; so a graph with 2r bipartitions has at least r connected components, and a simple calculation gives the result.

Posted in doing mathematics | Tagged | 4 Comments


If you have been trying to contact me by email at QMUL recently, please try my St Andrews address instead.

Inevitably, I suppose, technology tends to fail in the middle of a pandemic. Both QMUL and St Andrews use Outlook for email. While the St Andrews version continues to work fine, the QMUL version has gone into a sulk and does nothing. I get a page looking like it has been written in unadorned HTML with a very large font size; none of the links work, and no new mail has shown up for a week. The problem occurs on both the laptops I have access to now, and in both Firefox and Chrome, so I doubt that the trouble is at my end. I have put in a trouble ticket and wait for a response.

Of course, this has only been one of a rash of problems in the last couple of weeks. Just before I went to Prague for the Midsummer Combinatorics Workshop, my new Dell laptop started giving trouble. Mail and web pages would fail to download. At first I assumed it was a problem with the wi-fi. But when various other difficulties started happening, like failing to shut down properly, and failing to read USB drives, and then failing to work even when connected via an ethernet cable, it appeared to be more serious. Fortunately I was in Prague, where Honza Hubička took it as a challenge to get it working. The problem turned out to be way outside my competence, and I am not even sure I can describe it properly. On the Dell, it seems, everything connects to the USB rather than directly to the CPU; at some point Linux was upgraded, but the upgrade was incompatible with the USB driver in the Dell. So Honza was able to fix it by going back to an earlier version of Linux.

At almost exactly the same time, my fairly new compact camera broke. This seemed to be a mechanical problem: if you touch the zoom control, it seizes up and goes into a sulk, demanding to be turned off. So back to my old camera, which had no direct communication with the computer, so I have to take out the memory card and read that. Now I had a gadget which connects a card to a USB port, but I lost it before Christmas (I left it behind after giving a seminar at Imperial College). So what to do? Eventually I took both cameras to Prague, used the old one to take photographs, put the card into the new one, and transferred the pictures.

I didn’t take my ancient Acer laptop to Prague; it is big and heavy compared to the Dell. But soon after my return, it developed a problem of its own: the battery refused to charge, and was running down at an alarming rate. Fortunately this had happened once before. The fix is just to leave it for a couple of days, after which it behaves itself again.

My third (and preferred) laptop, by Entroware, is (sad to say) in London, and unavailable to me until I am brave enough to travel south.

Posted in Uncategorized | Tagged , , , , | 4 Comments

Puzzle solution

Thank you, Honza, spot on.

In 1964, Richard Rado published a construction of a universal graph, a countable graph which embeds every finite or countable graph as an induced subgraph. His graph turns out to be an explicit example of the Erdős–Rényi “random graph”.

The construction goes like this. (Here we are being logicians, so 0 is a natural number.) Any finite subset S of the natural numbers can be represented as a single number, the sum of the powers 2s for sS. To reverse the construction, take a number n, write it in base 2 (as a sum of powers of 2), and take the set of exponents which occur. (In this way the natural numbers form a model for hereditarily finite set theory, that is, Zermelo–Fraenkel set theory with the negation of the axiom of infinity, so that all sets are finite.

Let S(n) be the finite set corresponding to the number n.

Now the construction of the graph goes like this. Take two numbers n and m. One is smaller than the other; without loss, m < n. Now we join m to n if (and only if) m belongs to the set S(n).

What do we learn from this representation? Maybe not much, since the graph is most usually recognised by its properties. But here is one thing we learn. The graph is homogeneous, that is, any isomorphism between finite subgraphs extends to an automorphism of the graph. Using Rado’s representation, we see that the automorphism can be chosen to be a primitive recursive function (though, unfortunately, this does not mean that there is a simple representation for it: if you think it should, try to find a simple representation for an automorphism which interchanges vertices 0 and 1.)

In 1971, Ward Henson constructed a family of graphs with similar properties. The Henson graph Hn has the properties that it is homogeneous, it contains no copy of the complete graph on n vertices, and it is universal for finite or countable graphs containing no Kn. Later, Lachlan and Woodrow showed that, up to complementation, these graphs and Rado’s are the only “non-trivial” countable homogeneous graphs.

For simplicity I will stick to the case n = 3 here.

Henson found H3 inside Rado’s graph R, by a simple construction. Consider the set of natural numbers n such that n is not the largest vertex of a triangle in R. This is done by taking the natural numbers in turn, and including n in our set if and only if S(n) contains no edge of the graph; that is, for no i and j in S(n) does it happen that i is in S(j). Thus, the vertex set can be found iteratively; this is the set which was given in the puzzle.

Now this is a simple enough construction. If we had a simple formula for the vertex set, then we would have a simple explicit presentation of H3: the vertices would be given by the formula, and the edges would be defined exactly as in Rado’s graph.

But a simple formula of this sort is still lacking …

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