![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Julien Portier (Cambridge)
Thursday 21 November 2024, 14:30-15:30
Reconstructing a large subset of a point set in R from random sparse distance information
- 👤 Speaker: Julien Portier (Cambridge)
- 📅 Date & Time: Thursday 21 November 2024, 14:30 - 15:30
- 📍 Venue: MR12
Abstract
Let $V$ be a set of $n$ points in $\mathbb{R}$, and let $\epsilon > 0$ be a small enough fixed constant. Suppose the distances between each pair of points are revealed according to an Erd\H{o}s-Rényi random graph $G(n,(1+\epsilon)/n)$, meaning that the distance between any two points is revealed independently with probability $p=\frac{1+\epsilon}{n}$. We show that, with high probability, this information is sufficient to reconstruct, up to isometry, a subset of $V$ of size $\Omega_{\epsilon}(n)$. This confirms a conjecture posed by Gir\~ao, Illingworth, Michel, Powierski, and Scott. Our approach involves proving certain structural properties of the $2$-core of $G(n,(1+\epsilon)/n)$, which can be of independent interest. This work is joint with Julian Sahasrabudhe.
Series This talk is part of the Combinatorics Seminar series.
Included in Lists
- All CMS events
- All Talks (aka the CURE list)
- bld31
- CMS Events
- Combinatorics Seminar
- DPMMS info aggregator
- DPMMS lists
- DPMMS Lists
- DPMMS Pure Maths Seminar
- Hanchen DaDaDash
- Interested Talks
- MR12
- School of Physical Sciences
Note: Ex-directory lists are not shown.