Home > Department of Mathematics > Seminars > Large-Scale Structures in Random Graphs Workshop 2016

Large-Scale Structures in Random Graphs Workshop 2016

The aim of this workshop was primarily to work on open problems which will contribute to a better understanding of the general area of large-scale structures in random graphs.  The majority of the workshop was private but two Public Lectures were open to all on 13 December 2016.

Dates: 12 - 16 December 2016
Venue: The Alan Turing Institute, headquartered at the British Library
Organisers: Peter Allen, Julia Böttcher, Jozef Skokan and Rebecca Lumb (all Department of Mathematics, LSE)
Event Support: the Heilbronn Institute for Mathematical Research, The Alan Turing Institute and the Department of Mathematics, LSE



Public Lectures - 13 December 2016 (morning)

This event was free to attend but pre-registration was required via our Eventbrite page

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

Venue: The Alan Turing Institute, headquartered at the British Library.

Directions: 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.

10.00 - Refreshments and networking
10.30 - Rob Morris (IMPA): 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.

This lecture was broadcast live at bit.ly/TuringLive

11.40 - Stefanie Gerke (RHUL): 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.