RHUL Mathematics Seminar

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-β)]^-1nlog 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 rth 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 rth 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 rth 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 rth 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₁, x₂, …, x_n} of points in R² 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₀ 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₀(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.