Tuesday, December 6, 2016

[DMANET] Large-Scale Structures in Random Graphs Workshop 2016 – PUBLIC LECTURES -- Tuesday 13 December

* *Large-Scale Structures in Random Graphs Workshop 2016 – PUBLIC LECTURES

Tuesday 13 December – 10.00 - The Alan Turing Institute, headquartered
at the British Library

This event is free to attend but *_pre-registration is required via our
Eventbrite page_*
*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 a 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.
*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.
Further details:

* Contributions to be spread via DMANET are submitted to
* DMANET@zpr.uni-koeln.de
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/