Lecture: Large Scale Structures in Random Graphs

Date: 13 December 2016

Time: 10:00-12:40pm

Registration: Prior online registration is compulsory.





The first talk with Robert Morris will be live streamed: bit.ly/TuringLive

The recording will also be made available on our YouTube channel following the event. By attending the event you consent to audio and video recording and its/their publication.


10:00 – 10:30 Refreshments and networking

10:30 – 11:30 Robert Morris (IMPA)

11:40 – 12:40 Stefanie Gerke (RHUL)

Robert Morris: The sharp threshold for making squares

Many of the fastest known algorithms for factoring large integers rely on finding subsequences of randomly generated sequences of integers whose product is a perfect square. Motivated by this, at the 1994 ICM Pomerance posed the problem of determining the threshold of the event that a random sequence of N integers, each chosen uniformly from the set {1,…,x}, contains a subsequence, the product of whose elements is a perfect square. In 1996, Pomerance gave good bounds on this threshold and also conjectured that it is sharp.

A few years ago, in major breakthrough, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In the talk we will discuss a proof of their conjecture, which combines techniques from number theory and probabilistic combinatorics. In particular, at the heart of the proof lies a self-correcting random process of non-uniform hypergraphs.

Joint work with Paul Balister and Béla Bollobás.

Stefanie Gerke: Matchings in random bipartite graphs

We consider maximum matchings in random bipartite graphs with a fixed degree distribution. We then introduce an adversary and show for a simplified model under which conditions a matching exists that covers the smaller partition class.

This is joint work with Paul Balister.

This event is free to attend but pre-registration is required. On the day please enter through the main entrance of The British Library and make your way to The Alan Turing Institute, which is located on the first floor.

For any queries email Rebecca Lumb at r.c.lumb@lse.ac.uk or call 020 7955 7494.

Event Support: the Heilbronn Institute for Mathematical Research, The Alan Turing Institute and the Department of Mathematics, LSE