Department of Mathematics
Royal Holloway University Of London

Pure Maths Seminars Autumn 2007


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),
  • A hypergraph regularity method for generalised Turán problems (abstract)

  • 9th October: Marcus Appleby (Queen Mary),
  • Geometrie and Measurement (abstract)

  • 16th October: Laura Hitt (University College Dublin),
  • Hyperelliptic Curves in Cryptography (abstract)

  • 23rd October: Trevor Wooley, FRS, (Bristol),
  • A singular approach to solving quintic equations (abstract)

  • 30th October: Artur Czumaj (Warwick),
  • Testing expansion in bounded-degree graphs (abstract)

  • 6th November: Nikolaos Fountoulakis (Birmingham),
  • Percolation on random graphs with a given degree sequence (abstract)

  • 13th November: Oliver Riordan (Oxford),
  • The diameter of G(n,p)

  • 20th November: Rhiannon Hall (Brunel),
  • A chain-type theorem for hyperplanes and a splitter-type theorem for cocircuits (abstract)

  • 27th November: Robert Morris (Cambridge),
  • Bootstrap percolation

  • 4th December: Mark Walters (Queen Mary),
  • Random geometric graphs

  • 11th December: Simon Blackburn (Royal Holloway),
  • Prolific IPP Codes (abstract)


Useful links:

Campus map (The McCrea Building is number 17)

Interactive local street map

Seminars of past years




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 PG2(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 Fq, are those whose group of Fq-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 Fq-isogeny classes for a family of Jacobians of curves of genus 2 over Fq, for q=2m, 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 ˜On1/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* =Θ (a2/(d2 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(d2 n1/2 log(n/ε)/(a2 ε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

Department of Mathematics, Royal Holloway, University of London, Egham, Surrey TW20 0EX
Tel/Fax: +44 (0)1784 443093/430766