Site percolation on pseudo-random graphs

Seminar
Speaker
Sahar Diskin, Tel Aviv University
Date
02/01/2022 - 15:30 - 14:00Add to Calendar 2022-01-02 14:00:00 2022-01-02 15:30:00 Site percolation on pseudo-random graphs In the site percolation model, a random induced subgraph G[R] of a given graph G is formed by putting every vertex v of G into a random subset R with probability p and independently. One then researches typical properties of G[R], like the sizes of its connected components.  Here we study site percolation on pseudo-random graphs, specifically on (n,d,\lambda)-graphs, which are d-regular graphs on n vertices with all eigenvalues but the first (trivial) one bounded in absolute values by \lambda. It is well known that, assuming that the eigenvalue ratio \lambda/d is small, the edge distribution of an (n,d,\lambda)-graph resembles closely that of a truly random graph G(n,p) with the same expected density p=d/n.   We focus on the so-called supercritical regime p=(1+\epsilon)/d, for a positive constant \epsilon>0. In this range, we establish the asymptotic order of the giant component (a component of size proportional to |R|) in G[R] and show that it is typically unique. We also discuss further properties of the giant.  A joint work with Michael Krivelevich. zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
zoom
Abstract

In the site percolation model, a random induced subgraph G[R] of a given graph G is formed by putting every vertex v of G into a random subset R with probability p and independently. One then researches typical properties of G[R], like the sizes of its connected components.

 Here we study site percolation on pseudo-random graphs, specifically on (n,d,\lambda)-graphs, which are d-regular graphs on n vertices with all eigenvalues but the first (trivial) one bounded in absolute values by \lambda. It is well known that, assuming that the eigenvalue ratio \lambda/d is small, the edge distribution of an (n,d,\lambda)-graph resembles closely that of a truly random graph G(n,p) with the same expected density p=d/n. 

 We focus on the so-called supercritical regime p=(1+\epsilon)/d, for a positive constant \epsilon>0. In this range, we establish the asymptotic order of the giant component (a component of size proportional to |R|) in G[R] and show that it is typically unique. We also discuss further properties of the giant.

 A joint work with Michael Krivelevich.

Last Updated Date : 29/12/2021