*
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_*
<https://www.eventbrite.co.uk/e/large-scale-structures-in-random-graphs-public-lectures-tickets-29672085005>
*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:
_http://www.lse.ac.uk/maths/Seminars/Large-Scale-Structures-in-Random-Graphs-Workshop-2016.aspx_
<http://www.lse.ac.uk/maths/Seminars/Research_Seminars.aspx>
**********************************************************
*
* 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.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
