## Previous Pure Mathematics Colloquia - 2011 to 2012

Previous Pure Mathematics Colloquia from: 2013/14, 2012/13, 2011/12, 2010/11, 2009/10, 2008/09, 2007/08

### Wednesday, 12th of September 2012, 4pm, Theatre C

The finite basis problem for unary matrix semigroups

An algebra $$A$$ (a variety $$V$$) is non-finitely based (NFB) if its equational theory is not finitely axiomatisable; otherwise, A is finitely based (FB). If $$A$$ generates a locally finite variety, a stronger property of being inherently non-finitely based (INFB) requires that any locally finite variety $$V$$ containing $$A$$ is NFB. Thus, if $$A$$ and $$B$$ are finite algebras, $$A$$ is INFB, and $$A$$ belongs to the variety generated by $$B$$, then $$B$$ must be (I)NFB, too. For a given class $$C$$ of algebraic systems, the finite basis problem (FBP) asks for a characterisation of (non)finitely based members of $$C$$. Perhaps the most interesting case occurs when $$C$$ consists of finite algebras.

As shown by R.McKenzie, the general question whether a finite algebra is NFB (known as Tarski's finite basis problem) is algorithmically unsolvable. On the other hand, the finite basis problem for finite algebras led to extensive and fruitful investigations in several particular algebraic theories, one of the most successful in this regard being semigroup theory. In this talk I will review some recent results concerning the finite basis problem for finite involution semigroups. Natural examples of involution semigroups include groups, inverse semigroups, and matrix semigroups equipped with various unary operations, such as the matrix transposition.

Somewhat surprisingly, the initial expectation that the additional, seemingly well-behaved unary operation cannot disturb the state of affairs holding for plain semigroups turned out to be rather far from the truth. There are several aspects of a number of universal-algebraic questions (including the FBP), where involution semigroups take on a life of their own. Among other things, I plan to mention aspects of the FBP related to the following topics: \begin{itemize} \item the problem of characterising INFB finite involution semigroups; \item matrix semigroups endowed with natural unary operations, such as the transposition and the Moore-Penrose inverse (the classification of these with respect to the FBP will be the main focus of the talk); \item various partition monoids with involution, such as the Brauer monoid and the annular monoid; \item power semigroups of finite groups; \item finite inverse semigroups; etc. \end{itemize} I will point out several open questions.

Some of the original research presented was done jointly with Karl Auinger (Vienna, Austria) and Mikhail V. Volkov (Ekaterinburg, Russia).

### Thursday, 6th of September 2012, 4pm, Theatre C

James East
(University of Western Sydney)
Generating rank N semigroups with fewer than N elements

It is well-known that the full transformation semigroup $$T(n)$$ and symmetric inverse semigroup $$I(n)$$ both have rank 3, but can be embedded in 2-generator subsemigroups of $$T(n+1)$$ and $$I(n+1)$$. We investigate the corresponding problem in the partition monoids $$P(n)$$.

### Thursday, 23rd of August 2012, 4pm, Theatre D

Peter Cameron
(Queen Mary, University of London)
The random graph

The random graph $$R$$ is a paradoxical object: if you choose at edges independently at random with fixed probability from a countable vertex set, the result is isomorphic to $$R$$ with probability $$1$$. This graph has many fascinating properties and direct constructions. Moreover, it is one of a collection of objects (countable homogeneous structures) which include the rational numbers (as ordered set) and a countable metric space whose completion is the famous Urysohn space. Finally, a fairly recent result of Kechris, Pestov and Todor\v{c}evi\'c establishes an amazing connection between homogeneous structures, Ramsey theory, and topological dynamics. There is far too much to fit into a single talk, but I will give a whistle-stop tour of some of the highlights.

### Thursday, 23rd of August 2012, 2pm, Theatre D

Rosemary Bailey
(Queen Mary, University of London)
From Rothamsted to Northwick Park: designing experiments to avoid bias and reduce variance

In March 2006 the topic of designed experiments briefly hit the newspaper headlines when a clinical trial went badly wrong. Even when the health of volunteers is not at stake, there are some important factors to consider in the design of any comparative experiment. If you want to find out how much school milk improves children's health, it is no good giving the milk just to the poorest children, no matter how laudable that may be on other grounds. To avoid bias, some children in each income group should be given milk while the others in each group are not.

As well as avoiding bias, we want to reduce variance, because smaller variance indicates that our estimate of treatment differences is more likely to be close to the true value. Statisticians thought that they knew how to combine variance reduction with avoidance of bias, but the explosion of microarray experiments in the early 2000s showed that our received wisdom was wrong.

Experience from designing experiments in one field of science can be applied to other fields, once the necessary vocabulary has been learnt. In particular, the variance in dose-escalation trials can be reduced by a factor of three without reducing safety or using more volunteers.

### Wednesday, 22nd of August 2012, 12pm-1pm Theatre D

Peter Cameron
(Queen Mary, University of London)
Permutation groups and transformation semigroups

I will be talking about joint work with Jo\~ao Ara\'ujo and others. Jo\~ao's belief is that the group of units of a semigroup, or the normaliser of a transformation semigroup, should control the structure of the semigroup to a greater effect than previously thought, and that our improved knowledge of groups should be used to investigate this. Among the work I will report on are a near classification of the permutation groups $$G$$ with the property that, for any rank $$k$$ map $$f$$, the semigroup $$\langle G,f\rangle$$ is regular. The results used in the proof are very similar to the classical result of Livingstone and Wagner on set-transitivity, but (so far at least) use the Classification of Finite Simple Groups in the proofs.

### Tuesday, 7th of August 2012, 3pm, Theatre D

Mark Holland
(University of Exeter)
Recurrence statistics and extreme events

We will begin by exploring some simple, but counter-intuitive examples of recurrence statistics in coin tossing sequences. Typical questions we ask are: how long do we have to wait until we see a particular sequence, and which sequences are more likely to occur first? We then explore analogous problems for chaotic dynamical systems, where in this latter setting we consider the probability distributions that govern first visit to certain subsets of the phase space. This talk will be accessible to a broad mathematical audience.

### Wednesday, 27th of June 2012, 2pm, Theatre C

Prof. David Damanik
(Rice University, Houston)
Spectral Properties of the Fibonacci Hamiltonian

### Thursday, 10th of May 2012, 4pm, Theatre C

Alagacone Sri Ranga
to be announced

### Thursday, 26th of April 2012, 4pm, Theatre C

Robert Archbold
(University of Aberdeen)
Measuring non-commutativity in operator algebras

Let $$A$$ be a non-commutative normed algebra with centre $$Z(A)$$. A simple application of the triangle inequality shows that if $$a\in$$A is close to $$Z(A)$$ then $$a$$ almost commutes with elements of the unit ball of $$A$$ and so the inner derivation implemented by $$a$$ has small norm. The extent to which the converse holds is a basic question in the study of non-commutativity and has been investigated extensively in the case of von Neumann algebras and other $$C^*$$-algebras. In this context, $$K(A)$$ is defined to be the smallest number in $$[0,\infty]$$ such that ${\rm distance}(a,Z(A)) \leq K(A)\Vert{\rm ad}(a)\Vert$ for all $$a\in A$$, where $${\rm ad}(a)$$ is the inner derivation $$x\to xa-ax$$ $$(x\in A)$$.

We shall describe some old and new results in this area and give some indication of their dependence on

(i) the constrained optimization of the bounding radius of compact subsets of the plane,

(ii) primal ideals and the quantification of the failure of the Hausdorff property in the primitive ideal space $${\rm Prim}(A)$$,

(iii) some spectral theory.

### Tuesday, 24th of April 2012, 4pm, Theatre D

George Havas
(The University of Queensland)
Perfect palindromic presentations

Many researchers have considered various short presentations for groups over the years. Edmund Robertson and I have included in our considerations {\bf palindromic} presentations for perfect groups. This has led us to consider one specific family of such presentations in detail:

$P(n) = \{ x,y \mid xyx^{-1}yxy^{-1}, yxyx^ny^{2n}x^n \}$

We conjecture that $$\langle P(n) \rangle$$ maps onto a finite direct product of $$PSL_2( p^k)$$, for selected primes and for $$1 \leq k \leq 4$$, but not onto any other finite simple groups.

We discuss this and other conjectures about this family of groups, including information on both group theoretic and associated number theoretic computations.

This is joint work with Edmund and with Victor Scharaschkin (of The University of Queensland).

### Thursday, 19th of April 2012, 4pm, Theatre C

Simon Blackburn
(Royal Holloway college London)
The Probability that a Pair of Group Elements are Conjugate

Let $$G$$ be a finite group. Let $$\kappa(G)$$ be the probability that elements $$g,h\in G$$ are conjugate, when $$g$$ and $$h$$ are chosen uniformly and independently at random. In this talk, I will present results that classify groups $$G$$ with $$\kappa(G)$$ very large or very small, and I will give asymptotically good bounds on $$\kappa(G)$$ when $$G$$ is the symmetric group. This is joint work with John Britnell (Bristol) and Mark Wildon (RHUL).

### Thursday, 12th of April 2012, 4pm, Theatre C

Jeffrey Burdges
(University of St Andrews)
Genericity arguments in groups of finite Morley rank

We will discuss the classification project for simple groups of finite Morley rank. These are exactly the simple groups determined up to isomorphism by their cardinality and first-order theory and they are conjectured to be algebraic groups over algebraically closed fields. We shall focus upon the result that, inside any connected group of finite Morley rank, the centralizers of divisible torsion groups, aka tori, are connected. This result provides a nice framework for discussing the style of genericity argument that works well in a connected group of finite Morley rank. We hope to provide a non-technical impression of how similar genericity techniques generalize beyond finite rank as well.

### Thursday, 22th of March 2012, 4pm, Theatre C

Max Neunhoeffer
(University of St Andrews)
Algorithmic generalisations of Small Cancellation Theory

In this talk I explain how Jeffrey Burdges, Steve Linton, Richard Parker, Colva Roney-Dougal and I want to generalise the classical Small Cancellation Theory in an algorithmic direction. The essential idea is to replace the static Small Cancellation conditions by an algorithmic search, which automatically finds a suitable set of conditions for the problem instance at hand, and proves that these deliver a solution of the word problem. In addition, our methods can not only be applied to the word problem in quotients of free groups, but also to word problems in quotients of free products as well as corresponding problems for semigroups, monoids and rewrite systems. We expect that our approach leads to a completely new way to work with word hyperbolic finitely presented groups on a computer.

### Thursday, 8th of March 2012, 4pm, Theatre C

Agata Smoktunowicz
(University of Edinburgh)
Some results and open problems in noncommutative ring theory

We survey some open problems and results in Noncommutative ring theory. In particular we mention algebraic algebras, nil algebras, Golod-Shafarevich algebras, the Jacobson radical, connections with Group theory, growth of algebras.

### Thursday, 1st of March 2012, 4pm, Theatre C

James Mitchell
(University of St Andrews)
The lattice of subsemigroups of the semigroup of all functions on an infinite set

I'll tell you tomorrow what the talk is about...

### Thursday, 9th of February 2012, 4pm, Theatre C

Victor Maltcev
(Ukraine)
Congruence-free finitely presented monoids

In the talk we will prove a folklore result that every countable semigroup embeds in a finitely generated congruence-free monoid. Leading to understanding the Boone-Higman conjecture -- whether every finitely presented monoid with soluble word problem embeds in a finitely presented congruence-free monoid, we will provide several examples of f.p. cong-free monoids, and prove that at least every finite monoid does embed in the needed way. We will also give a countable series of bisimple H-trivial cong-free f.p. monoids. Any questions and suggestions will be very welcome.

### Thursday, 15th of December 2011, 4pm, Theatre C

Armando Martino
(University of Southhampton)

The Hanna Neumann conjecture is a well-known conjecture from 1957 which deals with the rank of the intersection of finitely generated subgroups of a free group which has recently been settled this year by Igor Mineyev. Mineyev's ingenious proof uses the orderability of a free group in a surprising way via l^2 cohomology. I'd like to talk about the proof of this conjecture and a natural generalisation to free products using an approach suggested by Warren Dicks which does not use analysis and relies instead on the Bass-Serre theory of group actions on trees. For free products rank is replaced with Kurosh rank, which will be familiar to those who know the Kurosh subgroup theorem, and the generalisation to free products contains the Hanna Neumann conjecture for free groups as a special case.

### Thursday, 8th of December 2011, 4pm, Theatre C

Simon Blackburn
(Royal Holloway college London)
The Probability that a Pair of Group Elements are Conjugate

Let $$G$$ be a finite group. Let $$\kappa(G)$$ be the probability that elements $$g,h\in G$$ are conjugate, when $$g$$ and $$h$$ are chosen uniformly and independently at random. In this talk, I will present results that classify groups $$G$$ with $$\kappa(G)$$ very large or very small, and I will give asymptotically good bounds on $$\kappa(G)$$ when $$G$$ is the symmetric group. This is joint work with John Britnell (Bristol) and Mark Wildon (RHUL).

### Thursday, 1st of December 2011, 4pm, Theatre C

Sophie Huczynska
(University of St Andrews)
From sum-free sets to subgroups: what lies between?

Given a group $$G$$ or an interval $$[1,N]$$ in the natural numbers, investigating those subsets $$S$$ such that $$|{(x,y)\in S^2:x+y\in S}|=0$$, known as sum-free sets, has attracted considerable attention. For a finite subset $$S$$ of a group $$G$$ or of the interval $$[1,N]$$, define $$r(S):=|{(x,y)\in S^2: x+y\in S}|$$ and consider its behaviour as $$S$$ ranges over all subsets of the group or interval. Concentrating mainly on the two cases of the group $$\mathbb{Z}/p\mathbb{Z}$$ under addition ($$p$$ prime), and the interval $$[1,N]$$ in the natural numbers, I will give a description of the spectrum of attainable $$r$$-values for the $$s$$-sets, constructive existence results and structural characterizations for sets attaining extremal and near-extremal values, as well as describing various open problems on the topic.

### Thursday, 24th of November 2011, 4pm, Theatre C

Sergey Kitaev
(University of Strathclyde)
On graphs representable by words

A simple graph G=(V,E) is (word-)representable if there exists a word W over the alphabet V such that any two distinct letters x and y alternate in W if and only if (x,y) is an edge in E. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. It is known that a graph is representable if and only if it is k-representable for some k. Minimum k for which a representable graph G is k-representable is called its representation number.

Representable graphs appeared first in algebra, in study of the Perkins semigroup which has played a central role in semigroup theory since 1960, particularly as a source of examples and counterexamples. However, these graphs have connections to robotic scheduling and they are interesting from combinatorial and graph theoretical point of view (for example, representable graphs are a generalization of circle graphs, which are exactly 2-representable graphs).

Some of questions one can ask about representable graphs are as follows. Are all graphs representable? How do we characterize those graphs that are (non-)representable? How many representable graphs are there? How large the representation number can be for a graph on n nodes?

In this talk, we will go through these and some other questions stating what progress has been made in answering them. In particular, we will see that a graph is representable if and only if it admits a so called semi-transitive orientation. This allows us to prove a number of results about representable graphs, not the least that 3-colorable graphs are representable. We also prove that the representation number of a graph on n nodes is at most n, from which one concludes that the recognition problem for representable graphs is in NP. This bound is tight up to a constant factor, as there are graphs whose representation number is n/2.

### Thursday, 10th of November 2011, 4pm, Theatre C

Georges Gonthier
(INRIA-Microsoft Research)
Proof engineering, from the Four Color to the Odd Order Theorem.

Thirty five years ago computers made a dramatic debut in mathematics with the famous proof of the Four Color Theorem by Appel and Haken. Their role has been expanding recently, from computational devices to tools that can tackle deduction and proofs too complex for (most) human minds, such as the Kepler conjecture or the Classification of Finite Simple Groups.

These new "machine" proofs entail fundamental changes in the practice of mathematics: a shift from craftsmanship, where each argument is a tribute to the ingenuity of the mathematician that perfected it, to a form of engineering where proofs are created more systematically. In addition to formal definitions and theorems, mathematical theories also contain clever, context-sensitive notations, usage conventions, and proof methods. To mechanize advanced mathematical results it is essential to capture these more informal elements, replacing informal and flexible usage conventions with rigorous interfaces, and exercise apprenticeship with precise algorithms. This can be difficult, requiring an array of techniques closer to software engineering than formal logic, but it is essential to obtaining formal proofs of graduate-level mathematics, and can give new insight as well.

In this talk we will give several examples of such empirical formal mathematics that we have encountered in the process of mechanizing a large corpus of Combinatorics and Algebra required by the proofs of the Four Colour and Odd Order Theorem.

### Thursday, 13th of October 2011, 4pm, Theatre C

Matt Brin
Some questions about the R. Thompson groups

I will briefly introduce Thompson's groups and then discuss questions about the groups and related structures that I would most like to see settled.

### Thursday, 6th of October 2011, 2:30pm, Theatre A

Geoff Whittle
(Victoria University of Wellington)
Well-quasi-ordering Binary Matroids

The Graph Minors Project of Robertson and Seymour is one of the highlights of twentieth-century mathematics. In a long series of mostly difficult papers they prove theorems that give profound insight into the qualitative structure of members of proper minor-closed classes of graphs. This insight enables them to prove some remarkable banner theorems, one of which is that in any infinite set of graphs there is one that is a minor of the other; in other words, graphs are well-quasi-ordered under the minor order.

A canonical way to obtain a matroid is from a set of columns of a matrix over a field. If each column has at most two nonzero entries there is an obvious graph associated with the matroid; thus it is not hard to see that matroids generalise graphs. Robertson and Seymour always believed that their results were special cases of more general theorems for matroids obtained from matrices over finite fields. For over a decade, Jim Geelen, Bert Gerards and I have been working towards achieving this generalisation. In this talk I will discuss our success in achieving the generalisation for binary matroids, that is, for matroids that can be obtained from matrices over the 2-element field.

In this talk I will give a very general overview of my work with Geelen and Gerards. I will not assume familiarity with matroids nor will I assume familiarity with the results of the Graph Minors Project.

### Thursday, 6th of October 2011, 4pm, Theatre C

Einar Steingrimmson
(University of Strathclyde)
Permutation Patterns

A pattern p in a permutation (of integers) is a subsequence of the permutation whose entries appear in the same order of size as those in p. For example, an occurrence of the pattern 123 is simply an increasing subsequence of length three. Also, the permutation 315264 has two occurrences of the pattern 231, namely 352 and 564. The permutation 312645, on the other hand, avoids the pattern 231.

The study of patterns, although implicit in work going back more than a century, has developed very rapidly in the last two decades. This is both because of the intrinsic interest of many problems in the field, and because of the many, and constantly growing, connections to other fields of mathematics, computer science, biology and physics. Examples of such connections are to sorting in computer science (which is the origin of the modern development of the subject), genome rearrangement, dynamical systems and certain models in statistical mechanics, and classification of Schubert varieties according to topological properties, in addition to a myriad connections to other combinatorial structures.

I will give the necessary background, some examples of current interesting problems in the field and examples of how patterns show up in other fields. To give just one example of the current (miserable :)) state of the art, nobody knows how many permutations of length n avoid the pattern 1324, although I will mention some recent progress on that.