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 (Thursday, 2pm McCrea229) | Ben Martin (Canterbury) Polynomial representation growth and alternating quotients (abstract) |

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

24th February | Alexander Kleshchev (University of Oregon) No Seminar. The talk by Alexander Kleshchev on 'Graded representation theory of symmetric groups' had to be canceled. |

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 |

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

David Craven: 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 of representation growth.

Malwina Luczak: 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(log *n*). This is joint work with David Levin and Yuval Peres.

James McKee: 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: 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: 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 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: The *r*th power of a graph *G* is the graph *G _{r}* on the same vertex set, with

*uv*an edge of

*G*if the distance from

_{r}*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*. Generalisations (such as the Erdös—Stone theorem) guarantee the existence of all small subgraphs with chromatic number

_{r+1}*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*/(

*r*+1)

*n*. This leaves a gap: what minimum degree condition guarantees the existence of the

*r*th power of a path on a 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 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: Let Γ be a group. Given a positive integer *n*, we define *r*_{n}(Γ) to be the number of isomorphism classes of complex representations of Γ 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: 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.