Position at St Andrews

We have just advertised a lectureship in Pure Mathematics. The advertisement is here.

Come join us!

Posted in Uncategorized | Tagged | Leave a comment

Combinatorics at Strathclyde

Two years ago, we enjoyed a successful British Combinatorial Conference at the University of Strathclyde in Glasgow. For me it was memorable for several reasons: the appearance of my book “Notes on Counting”, my fall to the floor during the ceilidh, the booksale, and (more seriously) some fine lectures including Graham Farr’s lecture commemorating Bill Tutte’s centenary.

Now the Combinatorics group at Strathclyde (David Bevan, Sergey Kitaev and Einar Steingrímsson) is under threat.

I have received two documents; one on reshaping the Department of Computer and Information Sciences, signed by the Head of Department; and a response from the three members of the Combinatorics group.

The first document is pretty much what you might expect, with lots of fine words about “emerging vision”, “imperative”, “resources … aligned with opportunities for future growth”. Mathematics finds no place in this emerging vision.
I quote:

Combinatorics is not considered to be of fundamental importance to UG-teaching. More broadly speaking, discrete mathematics is of fundamental importance but this can be covered by many staff (eg MSP, Data Analytics and Cybersecurity staff) in the Department.

And more along the same lines. In particular, the group is castigated for not getting “grants around a million pounds or more”. [How many mathematicians anywhere hold such grants?]

The response is a much better written and argued document. (Mathematicians, after all, have to be clear – it is an important part of the job – so I am not at all surprised by this.)

They point out that the three-member group is one of the very strongest research groups in the department, having produced 35% of the department’s four-star papers in the current REF and earning REF and grant funding of close to a million pounds in the last four years. Moreover, discrete mathematics underpins computer science, and the group (being the departments only experts in the area) have developed courses for this. Members of the group have had important administrative roles in the department, having greatly improved systems for interacting with PhD students (criticised in an earlier report).

Moreover, combinatorics, or discrete mathematics (the terms are closer in meaning than the Head of Department seems to think, and if there is a difference, the group’s expertise is broader than “just combinatorics”) is perhaps the most applicable part of mathematics in the information age.

Last year, the Bond report, titled “The era of mathematics”, highlighted the importance of knowledge exchange in mathematics, argued (with many examples) that all parts of mathematics can have application, and pushed for a big increase in funding for mathematics, especially the training of PhD students and postdocs. The Council for the Mathematical Sciences has set up two committees to push forward with this, one to prioritise the recommendations in the Bond Report, and the other to convince policymakers of their importance. I would have thought that Strathclyde would be well-placed to benefit from this, if it is successful. (But not of course under the current reshaping plan.)

There have, sad to say, been several instances in Britain of universities closing down mathematics or getting rid of mathematicians in other ways. One incident that sticks in my mind, in a case where I was involved, occurred when the head of another department, at the start of an interview with the committee, said “I couldn’t hold up my head to be in a University with no mathematics department”. In another case, mathematics was closed down so that computer science could expand; this computer science department now finds that its main job consists of teaching arts students how to switch on the computer. (I exaggerate, but not too much.)

It seems to me that the Strathclyde proposal is a very short-sighted move, and unlikely to be in the department’s long-term interest. Moreover, there is plenty of evidence that collaboration between mathematicians (either a department of them, or a group in a computer science department) and informaticians can be of enormous benefit to both.

If you feel as I do, you may wish to know that the head of Computer and Information Sciences at Strathclyde is Professor Neil Ghani. I am sure you can find his address; you can probably even guess it. You may also wish to contact higher authorities in the University. These are our friends and colleagues; please help if you can.

Posted in Uncategorized | Tagged , , , | 18 Comments

Tuna Altınel

Many of you have probably already heard the news that Tuna Altınel, a mathematician of Turkish nationality working in France, was arrested on a family visit to Turkey. His alleged crimes are signing a petition requesting peace talks, and taking part in a public meeting in Lyon “displeasing to the Turkish government”.

You can find latest news here. This website also explains what you can do to help.

Please do anything you can to call for his immediate release.

Posted in Uncategorized | Tagged | Leave a comment

Association schemes for diagonal groups

Sean Eberhard commented on my posts on diagonal groups (see here and here). He is correct; there is an association scheme preserved by the full diagonal group with n factors in the socle; it is non-trivial if n > 2. The details take a few pages to write out but the basic idea is completely fine.

This shows that an AS-free group (one which does not preserve a non-trivial association scheme) must be either 2-homogeneous or almost simple. Clearly every 2-homogeneous group is AS-free; there are almost simple examples, but they are rather strange and no pattern has emerged thus far.

I hope a preprint will go on the arXiv sometime soon. But you read it first here (in Sean’s comments over the last few days).

Posted in open problems | Tagged , , , | 1 Comment

London Combinatorics Colloquia 2019

In London last week for the two combinatorics colloquia, at Queen Mary and LSE. The weather was unusually grey and rainy; it seems in retrospect that it is almost always fine and sunny for this event, but I know that this is a trick of memory.

Two days, with six talks on each day; as usual I will only say a bit about my favourites.

The first talk on Wednesday at Queen Mary was by Péter Pál Pach, on Polynomial Schur’s Theorem. The Schur’s theorem here is the one that says, if you colour the natural numbers with finitely many colours, there is necessarily a monochromatic solution of the equation x+y = z. His talk was about the related equation x+y = p(z), where p is a polynomial. He described the case p(z) = z2 in detail; in this case, a pointer to what follows, the statement is true for two colours but false for three or more. In general, there is one case which is easily dispatched, typefied by the polynomial p(z) = 2z2+1; the right-hand side is always odd, so if we colour the even numbers red and the odd numbers blue, there is no monochromatic solution. Excluding this and related things, the same result holds: true for two colours, false for three or more.

Julia Wolf gave a talk which made some interesting connections, about an “additive combinatorics” version of the regularity lemma. The bounds which appear in the regularity lemma are very large (tower functions, as Gowers showed). But there is a graph called the “half graph” such that excluding it makes the proof easy and the bounds polynomial. The graph has vertices xi and yi for 1 ≤ i ≤ k, with xi joined to yj if and only if i ≤ j. This (and its infinite analogue) is a familiar object in parts of combinatorics and model theory; it is the case which must be excluded to get a Ramsey theorem for bipartite graphs, and its exclusion gives what model theorists call k-stability. To get nice results for subsets of finite abelian groups, you have to exclude the half-graph from the “additive Cayley graph” of the group, whose vertices are group elements, joined if their sum lies in the special subset. Julia and her collaborators proved strong results under this hypothesis, at which point the model theorists (including Anand Pillay) got into the act, and there was a race between the two groups.

In the afternoon, a rather low-key but very entertaining talk from Keith Ball. He began by exhibiting the Hadamard matrix of order 4, normalised so that its first row is positive. Any other row has two +s and two −s. The positions of the +s and the −s in the rows give a 1-factorisation of K4. So Keith asked: for which normalised Hadamard matrices of order n (a multiple of 4) is there a 1-factorisation of Kn with a bijection between 1-factors and rows after the first such that the two ends of each edge in the 1-factor have the same entry in the corresponding row? And (different question) for which normalised Hadamard matrices is there a 1-factorisation with a bijection between 1-factors and rows sso that the two ends of each edge in the 1-factor have opposite entries in the corresponding row? He conjectures that it is always so. He showed us the proof of the conjecture for Sylvester matrices (which he called “Walsh matrices”), and certain Paley matrices (the prime p has to have the property that 2 is the square of a primitive root).

His proof for Sylvester was by induction; to get from one to the next you take the Kronecker product with the Hadamard matrix of order 2. I wondered whether the property would be preserved by arbitrary Kronecker products of Hadamard matrices. After the talk, Natalie Behague assured me that it was so, and showed me the simple proof.

The next day, at LSE, I will describe just two of the six talks. The first, by Dhruv Mubayi, was my favourite of the whole two days. He talked about classical Ramsey numbers: colour the k-sets of an N-set red and blue; how large does N have to be to guarantee either a s-set with all subsets red, or a n-set with all subsets blue? He was particularly interested in the “off-diagonal” case where k and s are fixed, and n grows. Typically, upper and lower bounds are known, and they are tower functions of heights k and k−1 respectively. He surveyed the state of the art on this.

But his real interest was a refinement, due to Erdős and Hajnal, which introduces a new parameter t, between 1 and {s choose k}. The question is, how large does N have to be to guarantee either a s-set containing at least t red k-sets, or an n-set all of whose k-subsets are blue? Erdős and Hajnal conjectured that there are “threshold” values for t, at which the value of N jumps from polynomial to exponential, and from exponential to double exponential, and so on for each possible order of the tower. Dhruv and his colleagues have shown the existence of the first threshold, and found its precise value. Dhruv explained very clearly how this is a complicated mixture of randomness and induction, and neither part can be left out.

The other talk that impressed me was by Johannes Carmesin. He started off by telling us, or reminding us, about Kuratowski’s theorem: a graph is planar if and only if it has no K5 or K3,3 minor. It was not until 2006 that Lovász thought to ask about higher-dimensional analogues. Johannes interprets this as asking what are the obstructions to embedding a 2-dimensional simplicial complex into 3-space. He developed a theory of “space minors” for 2-dimensional complexes, rather more complicated than graph minors, and gave an excluded minor characterisation of embeddability in 3-space for a simply connected, locally 3-connected 2-complex. One remarkable feature of the theorem is the proof. You show that if the excluded minors don’t occur, then you can embed the complex in a simply connected 3-dimensional manifold. Now you use Perelman’s solution to the Poincaré conjecture: this manifold must be a 3-sphere, and you are done. And there is much more beside. He also has generalisations of Whitney’s theorems, matroid interpretations of everything, and so on. I don’t usually enjoy topology, but this was a very nice talk!

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

A virtual colloquium

I feel a bit nervous about advertising this.

This Thursday, 25 April, I am for the first time ever giving a virtual colloquium. The Northeast Combinatorics Network (that’s Northeast North America, for pedants) have an occasional Virtual Combinatorics Colloquium, and I will be speaking at 2pm Eastern Time (19.00 British Summer Time). When I consider all the things that might go wrong, and the distance my words and pictures have to travel, I am not filled with confidence …

So wish me well, and join if you feel so inclined.

Posted in events | Tagged , , | 4 Comments