Lecture: Large Scale Structures in Random Graphs

Learn more Add to Calendar 12/13/2016 05:37 PM 12/13/2016 05:37 PM Europe/London Lecture: Large Scale Structures in Random Graphs Location of the event
Tuesday 13 Dec 2016
Time: 17:37

About the event

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. Agenda 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 [email protected] or call 020 7955 7494. Event Support: the Heilbronn Institute for Mathematical Research, The Alan Turing Institute and the Department of Mathematics, LSE [caption id="attachment_4716" align="alignleft" width="450"]logos .[/caption]

Further info


The Alan Turing Institute

1st floor of the British Library, 96 Euston Road, London, NW1 2DB

51.5297753, -0.12665390000006