Some recent results on scale-free randomgraphsAlan Frieze. – p.1Random deletion in a scale free random graph:Colin Cooper, Alan Frieze, Juan Vera.Adversarial deletion in a scale free random graph:Abie Flaxman, Alan Frieze, Juan Vera.A geometric scale free random graph:Abie Flaxman, Alan Frieze, Juan Vera.. – p.2Random deletion in a scale free random graph:Colin Cooper, Alan Frieze, Juan Vera.Adversarial deletion in a scale free random graph:Abie Flaxman, Alan Frieze, Juan Vera.A geometric scale free random graph:Abie Flaxman, Alan Frieze, Juan Vera.. – p.2Random deletion in a scale free random graph:Colin Cooper, Alan Frieze, Juan Vera.Adversarial deletion in a scale free random graph:Abie Flaxman, Alan Frieze, Juan Vera.A geometric scale free random graph:Abie Flaxman, Alan Frieze, Juan Vera.. – p.2Random deletion in a scale free random graphWe consider a model where edges are added usingpreferential attachment and vertices/edges are deletedrandomly.Same model considered byChung and Lu.. – p.3Random deletion in a scale free random graphWe consider a model where edges are added usingpreferential attachment and vertices/edges are deletedrandomly.Same model considered byChung and Lu.. – p.3Gt= (Vt, Et) denotes the graph at time t.Initialisation: Start with G1with vertices x1and no edges.Stept ≥ 2A Probability 1 − α − α0: delete a randomly chosenvertex.B Probability α0we delete m randomly chosen edges.C Probability α1: add new vertex xtand m randomneighbours w1, . . . , wm.Pr(wi= w) =d(w, t − 1)2et−1. (1)D Probability α − α1: Add m random edges withendpoints chosen independently as in(1).. – p.4Gt= (Vt, Et) denotes the graph at time t.Initialisation: Start with G1with vertices x1and no edges.Stept ≥ 2A Probability 1 − α − α0: delete a randomly chosenvertex.B Probability α0we delete m randomly chosen edges.C Probability α1: add new vertex xtand m randomneighbours w1, . . . , wm.Pr(wi= w) =d(w, t − 1)2et−1. (1)D Probability α − α1: Add m random edges withendpoints chosen independently as in(1).. – p.4Gt= (Vt, Et) denotes the graph at time t.Initialisation: Start with G1with vertices x1and no edges.Stept ≥ 2A Probability 1 − α − α0: delete a randomly chosenvertex.B Probability α0we delete m randomly chosen edges.C Probability α1: add new vertex xtand m randomneighbours w1, . . . , wm.Pr(wi= w) =d(w, t − 1)2et−1. (1)D Probability α − α1: Add m random edges withendpoints chosen independently as in(1).. – p.4Gt= (Vt, Et) denotes the graph at time t.Initialisation: Start with G1with vertices x1and no edges.Stept ≥ 2A Probability 1 − α − α0: delete a randomly chosenvertex.B Probability α0we delete m randomly chosen edges.C Probability α1: add new vertex xtand m randomneighbours w1, . . . , wm.Pr(wi= w) =d(w, t − 1)2et−1. (1)D Probability α − α1: Add m random edges withendpoints chosen independently as in(1).. – p.4Gt= (Vt, Et) denotes the graph at time t.Initialisation: Start with G1with vertices x1and no edges.Stept ≥ 2A Probability 1 − α − α0: delete a randomly chosenvertex.B Probability α0we delete m randomly chosen edges.C Probability α1: add new vertex xtand m randomneighbours w1, . . . , wm.Pr(wi= w) =d(w, t − 1)2et−1. (1)D Probability α − α1: Add m random edges withendpoints chosen independently as in (1).. – p.4We skip over details of what to doif there are no vertices to delete orwhat to do with multiple edges etc.. – p.5Dk(t) is the number of vertices of degree k in GtandDk(t) = E(Dk(t)).β =2(α − α0)3α − 1 − α1− α0TheoremUnder natural restrictions on the parameters, there exists aconstant C = C(m, α, α0, α1) such that for k ≥ 1,Dk(t)t− Ck−1−β= Ot−ε+ Ok−2−β.. – p.6Suppose that vt, etdenote the number of vertices andedges in Gt.Dk(t + 1) = Dk(t)+(2α − α1)mE−kDk(t)2et+(k − 1)Dk−1(t)2etet> 0Pr(et> 0)+ (1 − α)(k + 1)EDk+1(t) − Dk(t)vtet> 0Pr(et> 0)+ α11k=m+ error terms.. – p.7Suppose that vt, etdenote the number of vertices andedges in Gt.Dk(t + 1) = Dk(t)+(2α − α1)mE−kDk(t)2et+(k − 1)Dk−1(t)2etet> 0Pr(et> 0)+ (1 − α)(k + 1)EDk+1(t) − Dk(t)vtet> 0Pr(et> 0)+ α11k=m+ error terms.. – p.7Letν = α + α0+ α1− 1 > 0 and η =m(α − α0)ν1 + α1− α − α0.We show|vt− νt| ≤ t1/2log t, qs.Pr(|et− ηt| ≥ t1−ε) = O(t−ε).We used Chebychef to handle et. Chung and Lu modifyAzuma’s inequality, avoids constraint on edge deletion prob.. – p.8Letν = α + α0+ α1− 1 > 0 and η =m(α − α0)ν1 + α1− α − α0.We show|vt− νt| ≤ t1/2log t, qs.Pr(|et− ηt| ≥ t1−ε) = O(t−ε).We used Chebychef to handle et. Chung and Lu modifyAzuma’s inequality, avoids constraint on edge deletion prob.. – p.8Letν = α + α0+ α1− 1 > 0 and η =m(α − α0)ν1 + α1− α − α0.We show|vt− νt| ≤ t1/2log t, qs.Pr(|et− ηt| ≥ t1−ε) = O(t−ε).We used Chebychef to handle et. Chung and Lu modifyAzuma’s inequality, avoids constraint on edge deletion prob.. – p.8Letν = α + α0+ α1− 1 > 0 and η =m(α − α0)ν1 + α1− α − α0.We show|vt− νt| ≤ t1/2log t, qs.Pr(|et− ηt| ≥ t1−ε) = O(t−ε).We used Chebychef to handle et. Chung and Lu modifyAzuma’s inequality, avoids constraint on edge deletion prob.. – p.8As a consequence we can writeDk(t + 1) = Dk(t) + (A2(k + 1) + B2)Dk+1(t)t+(A1k+B1+1)Dk(t)t+(A0(k−1)+B0)Dk−1(t)t+α11k=m+O(t−ε).A2=1 − α − α0ν+mα0ηB2= 0A1= −(2α − α1+ 2α0)m2η−1 − α − α0νB1= −1 −1 − α − α0νA0=(2α − α1)m2ηB0= 0. – p.9Assuming Dk(t) ∼ dkt we consider the recurrence: d−1= 0and for k ≥ −1,(A2(k + 2) + B2)dk+2+ (A1(k + 1) + B1)dk+1+ (A0k + B0)dk= −α11k=m−1. (2)To justify this attention we prove: Let dkbe a solution to (2)such thatdk≤Ckfor k > 0 for some C, then there exists aconstantM > 0 such that for t ≥ 2, k ≥ −1,|Dk(t) − tdk| ≤ Mt1−ε.. – p.10Assuming Dk(t) ∼ dkt we consider the recurrence: d−1= 0and for k ≥ −1,(A2(k + 2) + B2)dk+2+ (A1(k + 1) + B1)dk+1+ (A0k + B0)dk= −α11k=m−1. (2)To justify this attention we prove: Let dkbe a solution to (2)such that dk≤Ckfor k > 0 for some C, then there exists aconstantM > 0 such that for t ≥ 2, k ≥ −1,|Dk(t) − tdk| ≤ Mt1−ε.. – p.10Solution of (2):We first tackle homogeneous