Autumn 2008

30th September | Hugh Montgomery (University of Michigan, Ann Arbor) Analytic inequalities |

7th October | David Craven (Oxford) Symmetric groups, partitions and representation growth (abstract) |

14th October | Mark Jerrum (QMUL) An approximation trichotomy for #CSP |

21st October | Titus Hilberdink (Reading) Well behaved generalised primes and integers |

28th October | Malwina Luczak (LSE) Glauber dynamics for the Mean-field Ising Model: cut-off, critical power law, and metastability (abstract) |

4th November | Henri Johnsten (Oxford) Non-existence and splitting theorems for normal integral bases. |

11th November | James McKee (RHUL) Galois theory of Salem polynomials (abstract) |

18th November | Nigel Boston (University College Dublin) Random groups in number theory and topology (abstract) |

25th November | Graham Everest (East Anglia) Elliptic Divisibility Sequences and Hilbert's Tenth Problem |

2nd December | Tim Riley (Bristol) Dual spanning trees in planar graphs, and 'filling invariants' for finitely presented groups (abstract) |

Spring 2009

13th January | Martin Bright (Bristol) The local-global appraoch to Diophantine equations (abstract) |

20th January | Peter Allen (Warwick) Turán to Pósa-Seymour: minimum degree conditions for large subgraphs (abstract) |

27th January | Christopher Voll (Southampton) From subgroup growth to representation growth |

3rd February | Jens Marklof (Bristol) The Boltzmann–Grad limit of the periodic Lorentz gas and the distribution of visible lattice points (abstract) |

10th February | Simon Blackburn (RHUL) Inaugural lecture |

12th February | Ben Martin (Canterbury) Polynomial representation growth and alternating quotients (abstract) |

17th February | Maura Paterson (RHUL) Combinatorial batch codes (abstract) |

3rd March | Arie Koster (Warwick) Recent advances in integer programming |

10th March | Yvo Desmedt (UCL) Applying Recreational Mathematics to Secure Mutliparty Computation |

17th March | Norman Biggs (LSE) Curious curves and graph polynomials. |

24th March | Dudley Stark (QMUL) Poisson approximation of the number of cliques in random intersection graphs |

Thursday 26th March | Mark Berman (Ben-Gurion University of the Negev) Counting conjugacy classes using p-adic integrals |

Summer 2009

28th April | Alan Hayes (York) Recent results about Farey fractions (abstract) |

12th May | Simon Blackburn (RHUL) Distinct difference configurations and wireless sensor networks (abstract) |

19th May | Steven Galbraith (RHUL) Fast elliptic curve cryptography using endomorphisms, and security considerations (abstract) |

26th May | Jon Gonzalez (Santander) Parameterisation of a Smooth Cubic Surface (abstract) |

2nd June | Reto Spöhel (ETH Zurich) Small subgraphs in the Achlioptas process (abstract) |

9th June | Mihyun Kang (HU Berlin) How to count planar graphs? (abstract) |

15th June | Mikhail Ershov Kazhdan quotients of Golod–Shafarevich groups |

16th June | Yvonne Buttkewitz Multiplicative arithmetic functions at consecutive integers |

21st July | Colin Reid (Queen Mary) Subgroups of finite index and the just infinite property (abstract) |

28th July | Claas Roever (National University of Ireland, Galway) The commensurator of Thompson's group (abstract) |

David Craven: Symmetric groups, partitions and representation growth

The representation growth of residually finite groups — studying the dimensions of irreducible complex representations of a, usually infinite, group — is a relatively new area. Of particular interest are the degrees of characters of symmetric groups, which are determined by combinatorial objects associated with partitions. In this talk I will discuss the multiplicities of character degrees of symmetric groups, and an application to the field representation growth.

Malwina Luczak: Glauber dynamics for the Mean-field Ising Model: cut-off, critical power law, and metastability

We study the Glauber dynamics for the Ising model on the complete graph, also known as the Curie-Weiss Model. For β < 1, we prove that the dynamics exhibits a cut-off: the distance to stationarity drops from near 1 to near 0 in a window of order *n* centered at [2(1-β)]^{-1}*n*log *n*. For β = 1, we prove that the mixing time is of order *n*^{3/2}. For β > 1, we study metastability. In particular, we show that the Glauber dynamics restricted to states of non-negative magnetization has mixing time O(*n* log *n*). This is joint work with David Levin and Yuval Peres.

James McKee: Galois theory of Salem polynomials

This is joint work with Christos Christopoulos. Let *f*(*x*) be the minimal polynomial of a Salem number, and let *g*(*x*) be the associated 'trace polynomial'. Let *F* and *G* be the Galois groups of *f*(*x*) and *g*(*x*). The group *G* is a quotient of *F* by a normal subgroup *N*. The group extension splits, so that *F* is isomorphic to the semidirect product of *N* and *G*.

Nigel Boston: Random groups in number theory and topology

In a recent Inventiones paper Dunfield and Thurston compare fundamental groups of random 3-mainfolds and random discrete groups. Analogously, we develop a theory comparing certain random Galois groups and random *p*-groups. In particular, what is the probability that *r* relators chosen at random from a *g*-generator free group present a particular group? We make sense of and answer this question for *p*-groups. This leads to some mysterious mass formulae, some infinite groups that arise with nonzero probability, and applications to number theory.

Tim Riley: Dual spanning trees in planar graphs, and 'filling invariants' for finitely presented groups

I will describe some work with W. P. Thurston on how duality conditions affect the existence of efficient spanning trees in planar graphs. I will explain the significance of the topic for the study of filling invariants for finitely presented groups.

Martin Bright: The local-global appraoch to Diophantine equations

The study of whole-number solutions of polynomial equations has attracted mathematicians for thousands of years, yet we are still far from understanding anything but the simplest equations. One approach is to look at "local" information: that is, information over the real numbers and modulo prime powers; and to try to deduce information about the 'global' solutions: that is, solutions in integers or rational numbers. For example, Hasse proved that a quadratic form in any number of variables has a rational zero if, and only if, it has zeros in the real numbers and modulo each prime power. More general equations do not satisfy this 'Hasse principle'; I will describe ways to understand this failure.

Peter Allen: Turán to Pósa-Seymour: minimum degree conditions for large subgraphs

The *r*th power of a graph *G* is the graph *G*_{r} on the same vertex set, with *uv* an edge of *G*_{r} if the distance from *u* to *v* in *G* is at most *r*. Extremal graph theory begins with Turán's theorem, which guarantees that an n-vertex graph whose minimum degree is (*r*-1/*r*)*n* must contain a complete subgraph *K*_{r+1}. Generalisations (such as the Erdős–Stone theorem) guarantee the existence of all small subgraphs with chromatic number *r*+1 at around the same minimum degree threshold; this includes the *r*th power of a short path. At the other extreme Dirac's theorem guarantees that an *n*-vertex graph with minimum degree *n*/2 contains a path covering all *n* vertices; and the Pósa-Seymour conjecture (proved by Komlós, Sárközy and Szemerédi for large graphs) generalises this, guaranteeing the *r*th power of a path covering all *n* vertices when the minimum degree is at least (*r*-1/*r*)*n*. This leaves a gap: what minimum degree condition guarantees the existence of the *r*th power of a path on *n* vertices for some 0 < *a* < 1? We answer this question for *r* = 1 and 2, give conjectures for larger *r*, and mention a further generalisation to 'path-like' graphs. This is joint work with Julia Böttcher and Jan Hladký.

Jens Marklof: The Boltzmann–Grad limit of the periodic Lorentz gas and the distribution of visible lattice points

The periodic Lorentz gas describes a particle moving in a periodic array of spherical scatterers, and is one of the fundamental mathematical models for chaotic diffusion in a periodic set-up. In this lecture (aimed at a general mathematical audience) I describe the recent solution of a problem posed by Y. Sinai in the early 1980s, on the nature of the diffusion when the scatterers are very small. The problem is closely related to some basic questions in number theory, in particular the distribution of lattice points visible from a given position, see e.g. Polya's 1918 paper on the visibility in a forest. The key technology in our approach is measure rigidity, a branch of ergodic theory that has proved valuable in recent solutions of other problems in number theory and mathematical physics, such as the value distribution of quadratic forms at integers, quantum unique ergodicity and questions of diophantine approximation. (This lecture is based on joint work with A. Strombergsson, Uppsala.)

Ben Martin: Polynomial representation growth and alternating quotients

Let Γ be a group. Given a positive integer *n*, we define *r*_{n}(Γ) to be the number of isomorphism classes of complex representations of Gamma of dimension at most *n* (note that *r*_{n}(Γ) can be infinite). We say that Γ has polynomial representation growth if there exist positive α and β such that *r*_{n}(Γ) is at most α*n*^{β} for every *n*. In this talk I will discuss a question of Brent Everitt: does there exist a finitely generated group Γ such that (1) Γ has polynomial representation growth; and (2) Γ has the alternating group *A*_{m} as a quotient for infinitely many *m*?

Maura Paterson: Combinatorial batch codes

A batch code specifies a method to distribute a database of *n* items among *m* devices (servers) in such a way that any *k* items can be retrieved by reading at most *t* items from each of the servers. It is of interest to devise batch codes that minimize the total storage, denoted by *N*, over all *m* servers. In this talk we consider the special case *t* = 1, under the assumption that every server stores a subset of the items. This is purely a combinatorial problem, so we call this kind of batch code a 'combinatorial batch code'. We consider how batch codes that are optimal with respect to the storage requirement *N* can be constructed for various combinations of parameters. We also discuss uniform codes, where every item is stored in precisely *c* of the *m* servers (such a code is said to have rate 1/*c*), presenting interesting new results in the cases *c* = 2, *k*-2 and *k*-1. In addition, we describe improved existence results for arbitrary fixed *c* using the probabilistic method.

Alan Hayes: Recent results about Farey fractions

In the 1920's Franel and Landau proved that the Riemann Hypothesis is equivalent to a statement about the discrepancy of the Farey sequence. In 1971 M. N. Huxley proved an analogous theorem for Dirichlet L-functions. Over the last decade these results have motivated an investigation into the structure of relevant subsets of the Farey fractions. We will discuss some of the fruit of this investigation, as well as some potential applications and unsolved problems.

Simon Blackburn: Distinct difference configurations and wireless sensor networks

This seminar is based on joint work with Tuvi Etzion, Keith Martin and Maura Paterson. See the preprints at http://arxiv.org/abs/0811.3832 and http://arxiv.org/abs/0811.3896 for full details. A set *X* = {*x*_{1}, *x*_{2}, …, *x*_{n}} of points in **R**^{2} is a distinct difference configuration if the vectors *x*_{i} - *x*_{j} for *i* not equal to *j* are all distinct. A typical question we might want to ask is: Suppose the points have integer co-ordinates, and that any pair of points are at Euclidean distance at most *d*. How large can *n* be (as a function of *d*)? Similar questions have been studied as part of the theory of Costas arrays and of *B* sequences, for example. Our motivation comes from a key predistribution scheme for wireless sensor networks that uses distinct difference configurations. I plan to introduce this key predistribution scheme, talk about some combinatorial problems this scheme motivates and give some good constructions and bounds for distinct difference arrays. I will show how our work settles aconjecture of Golomb and Taylor from 1984 on honeycomb arrays.

Steven Galbraith: Fast elliptic curve cryptography using endomorphisms, and security considerations

Public key cryptography based on the discrete logarithm problem in a finite group started with the work of Diffie and Hellman in 1976. In the mid-1980s it was suggested that the group of points on an elliptic curve might offer better security than the multiplicative group of a finite field. It turns out that elliptic curves have other features which make them attractive for cryptography. This talk will summarise the Gallant–Lambert–Vanstone trick of speeding up elliptic curve cryptography using an endomorphism. I will present some recent extensions of this idea. I will then explain why this trick motivates research on the multi-dimensional discrete logarithm problem, which is a topic I have been investigating together with my students Waldyr Benits Jr. and Raminder Ruprai.

Jon Gonzalez: Parameterisation of a Smooth Cubic Surface

A cubic surface *S* is the vanishing set of a homogeneous polynomial of degree 3 in complex 3-dimensional projective space. A proper parametrisation of *S* is a birational map from 2-dimensional projective space to *S*, given by homogeneous polynomials of the same degree and without any common divisors. By a classical result of Clebsch, every cubic surface admits a proper parametrisation by cubic polynomials over the complex numbers. In my talk I will discuss how such a parameterisation can be obtained explicitly and under which circumstances it can be obtained over a smaller field, e.g. the real or the rational numbers.

Reto Spöhel: Small subgraphs in the Achlioptas process

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with *G*_{0} as the empty graph on *n* vertices, in every step a set of *r* edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining *r*-1 edges are discarded. Thus after *N* steps, we have seen *rN* edges, and selected exactly *N* out of these to create a graph *G*_{N}. In a recent paper by Krivelevich, Loh, and Sudakov, the problem of avoiding a copy of some fixed graph *F* in *G*_{N} for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs *F* . We disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions *N*_{0}(*F*,*r*,*n*) for arbitrary graphs *F* and any fixed integer *r*. Joint work with Torsten Mütze and Henning Thomas.

Mihyun Kang: How to count planar graphs?

Random graphs on surfaces, in particular random planar graphs, have recently received much attention from the viewpoint of typical properties, uniform sampling and enumeration.The focus of this talk will be the enumeration problem. We briefly surveyrecent results and methods of how to count labelled planar graphs with given numbers of vertices and edges. We also discuss the power and limitations of each method.

Colin Reid: Subgroups of finite index and the just infinite property

An infinite residually finite (profinite) group is just infinite if every non-trivial (closed) normal subgroup is of finite index, and hereditarily just infinite if every subgroup of finite index is just infinite. But which subgroups of finite index need to be just infinite to ensure that all of them are? I will present a partial answer to this question, after a brief overview of the basic types of just infinite groups and why they are of interest.

Claas Roever: The commensurator of Thompson's group

I shall describe how one can determine the abstract commensurator of Thompson's group *F* and what is know about its structure. All terms occuring in the previous sentence will be explained during the talk; no preknowledge of commensurators or Thompson's group are required.