Wednesday, October 20, 2021 — 4:00 PM EDT

Konstantin Tikhomirov, Georgia Institute of Technology

"Shotgun assembly of Erdos-Renyi graphs"

We show that in the regime p>n^{-1/2} polylog(n), the unlabeled G(n,p) random graph can be uniquely reconstructed from its 1-neighborhoods with probability close to one, answering a question of Gaudio and Mossel. Based on joint work with Han Huang.

This seminar will be held jointly online and in person. 

Event tags 

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2022 (7)
    1. January (7)
  2. 2021 (135)
    1. December (11)
    2. November (22)
    3. October (15)
    4. September (5)
    5. August (15)
    6. July (17)
    7. June (15)
    8. May (1)
    9. April (4)
    10. March (11)
    11. February (9)
    12. January (10)
  3. 2020 (103)
  4. 2019 (199)
  5. 2018 (212)
  6. 2017 (281)
  7. 2016 (335)
  8. 2015 (211)
  9. 2014 (235)
  10. 2013 (251)
  11. 2012 (135)