**ALL WELCOME !**

This page lists this term's Pure Mathematics Seminars. All are welcome. All seminars will take place in the McCrea Building, Room 219, on Tuesdays at 4.00pm, unless stated otherwise. Tea is served before the seminar at 3.30 in Room 237 of the McCrea Building.

**Seminars for the autumn term 2007.**

- 2nd October:
**Peter Keevash**(Queen Mary), - 9th October:
**Marcus Appleby**(Queen Mary), - 16th October:
**Laura Hitt**(University College Dublin), - 23rd October:
**Trevor Wooley,**FRS, (Bristol), - 30th October:
**Artur Czumaj**(Warwick), - 6th November:
**Nikolaos Fountoulakis**(Birmingham), - 13th November:
**Oliver Riordan**(Oxford), - 20th November:
**Rhiannon Hall**(Brunel), - 27th November:
**Robert Morris**(Cambridge), - 4th December:
**Mark Walters**(Queen Mary), - 11th December:
**Simon Blackburn**(Royal Holloway),

A hypergraph regularity method for generalised Turán problems (abstract)

Geometrie and Measurement (abstract)

Hyperelliptic Curves in Cryptography (abstract)

A singular approach to solving quintic equations (abstract)

Testing expansion in bounded-degree graphs (abstract)

Percolation on random graphs with a given degree sequence (abstract)

The diameter of G(n,p)

A chain-type theorem for hyperplanes and a splitter-type theorem for cocircuits (abstract)

Bootstrap percolation

Random geometric graphs

Prolific IPP Codes (abstract)

**Useful links**:

Campus map (The McCrea Building is number 17)

**Abstracts**

Peter Keevash, A hypergraph regularity method for generalised Turán problem

We introduce a method that we believe may be foundational for a comprehensive theory of generalised Turan problems. The cornerstone of our approach is a quasirandom counting lemma for quasirandom hypergraphs, which extends the standard counting lemma by not only counting copies of a particular configuration but also showing that these copies are evenly distributed. We demonstrate the power of the method by proving a conjecture of Mubayi on the codegree threshold of the Fano plane, that any 3-graph on n vertices for which every pair of vertices is contained in more than n/2 edges must contain a Fano plane, for n sufficiently large. For projective planes over fields of odd size we show that the codegree threshold is between n/2-q+1 and n/2, but for PG_{2}(4) we find the somewhat surprising phenomenon that the threshold is less than (1/2-c)n for some absolute c>0.

Marcus Appleby, Geometry and Measurement

The solution of many problems in quantum information---for instance, the problem of devising a measurement scheme which maximises the tomographic efficiency---is critically dependent on the geometry of the space of density matrices. For a Hilbert space of dimension 2 this geometry is very simple: it is simply a sphere. However for Hilbert spaces of dimension greater than 2 the geometry is much more interesting, and this makes the problem of devising optimal measurement schemes both difficult, and (we suspect) mathematically deep. One approach, which has been known for a long time, is based on mutually unbiased bases. However, this approach has so far only been shown to work when the Hilbert space dimension is a power of a prime number. Recently a different approach has been proposed, based on symmetric, informationally complete positive operator valued measurements (SIC POVMs). Such POVMs have been constructed numerically for every Hilbert space dimension up to 45, which suggests that they may actually exist in every dimension. However, this has not been proved. In this talk we give an overview of the problem. We then go on to present some new results obtained in collaboration with Chris Fuchs (Bell Labs) and Hoan Dang (Princeton).

Laura Hitt, Hyperelliptic Curves in Cryptography

I will give an overview of hyperelliptic curves in cryptography, and in particular, such curves that are suitable for pairing-based cryptography. These ``pairing-friendly" hyperelliptic curves over a finite field F_{q}, are those whose group of F_{q}-rational points of the Jacobian has size divisible by a large prime, whose embedding degree is small enough for computations to be feasible, and whose minimal embedding field is large enough for the discrete logarithm problem in it to be difficult. I will construct a sequence of F_{q}-isogeny classes for a family of Jacobians of curves of genus 2 over F_{q}, for q=2^{m}, and give their corresponding small embedding degrees for the subgroup with large prime order.

Trevor Wooley, A singular approach to solving quintic equations

In 1957 a race was underway, and the outcome was almost a dead heat. Consider a homogeneous cubic polynomial with rational integral coefficients. The competition was to show, assuming that the cubic has "sufficiently many" variables, that the polynomial necessarily possesses a non-trivial integral zero (and more generally, linear spaces of rational solutions). The three contestants in the photo-finish (Birch, Davenport and Lewis) applied quite different methods, and later developments demonstrated these methods to be applicable in a wider context. In this talk we discuss what can be said for the analogous problem for quintic polynomials. The methods we present are based on simple geometry, linear algebra and harmonic analysis, and should be largely accessible to those less familiar with number theory.

Artur Czumaj, Testing expansion in bounded-degree graphs

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion:

an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time ˜On^{1/2}. We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is ε-far from an a*-expander with probability at least 2/3, where a* =Θ (a^{2}/(d^{2} log(n/ε)) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d^{2} n^{1/2} log(n/ε)/(a^{2} ε^{3})).

Nikolaos Fountoulakis, Percolation on random graphs with a given degree sequence

What happens to a graph when we delete some of its edges or its vertices randomly? In this talk we will study the effect of such random deletions to the typical structure of a graph that is randomly chosen from a specific class of graphs. We will show that there is a critical proportion of deleted edges (or vertices), around which an abrupt change in the typical structure of the remaining graph takes place. We will also discuss some open problems.

Rhiannon Hall, A chain-type theorem for hyperplanes and a splitter-type theorem for cocircuits

Within matroid theory, there has been much interest for some time in being able to remove elements from 3-connected matroids while remaining (almost) 3-connected. Theorems of this nature are generally known as “chain-type” theorems. Furthermore, theorems in which you remove elements, remain (almost) 3-connected and retain a specific 3-connected minor are known as “splitter-type” theorems. In this talk, we discuss a chain-type theorem for hyperplane elements and a splitter-type theorem for cocircuit elements. The talk will be aimed at a general mathematical audience with the first half hour devoted to introducing matroid theory.

Simon Blackburn, Prolific IPP Codes

Codes with the identifiable parent property (IPP codes) are combinatorial objects that were originally used in schemes for copyright protection. There are parallels between the theories of IPP codes and error correcting codes. This talk will explore some of these connections. In particular, I'll define a prolific IPP code by drawingan analogy with perfect error correcting codes and I'll discuss a theorem that classifies linear prolific IPP codes. This is joint work with Tuvi Etzion and Siaw-Lynn Ng, completed when Tuvi was visiting the department on an EPSRC grant earlier this year.

For more information please contact stefanie.gerke@rhul.ac.uk