Academics

Graph alignment for Erdos-Renyi random graphs | Probability Seminar

Time:2023-12-12 Tue 14:00-15:30

Venue:A3-2a-302 ZOOM:361 038 6975(PW: BIMSA)

Organizer:Yuval Peres

Speaker:Mark Rudelson University of Michigan

Abstract

Consider two copies of the same $G(n,p)$ graph and erase independently the edges of each copy with probability $t < p$. This procedure creates two correlated random graphs. We discuss a randomized algorithm recovering the matching between the vertices of the two graphs for a certain range of parameters.

DATEDecember 12, 2023
SHARE
Related News
    • 0

      YMSC Probability Seminar | Extreme eigenvalues of random regular graphs

      AbstractExtremal eigenvalues of graphs are of particular interest in theoretical computer science and combinatorics. Specifically, the spectral gap—the gap between the first and second largest eigenvalues—measures the expanding property of the graph. In this talk, I will focus on random $d$-regular graphs, for which the largest eigenvalue is $d$.I'll first explain some conjectures on the extr...

    • 1

      Iwasawa Theory on Graph

      BIMSA-YMSC Number Theory Lunch SeminarOrganizers:Yong Suk Moon, Koji ShimizuSpeaker:Xiuwu ZhuTime:12-1 pm on ThursdaysOct. 30, 2025Venue:BIMSA A4-1Title: Iwasawa Theory on GraphAbstract:In graph theory, certain covering maps satisfying specific symmetry conditions can be viewed as analogues of Galois extensions in number theory. Recent studies have revealed that, along the $\mathbb{Z}_p$-ex...