Pseudo-random graphs and applications

Probability Seminar

Suman Chakraborty (UNC)

Thursday, November 9, 2017 -
4:15pm to 5:15pm
Location: 
Hanes Hall 125 UNC

We consider classes of pseudo-random graphs on n vertices for which the degree of every vertex and the co-degree between every pair of vertices are in the intervals (np-Cn^δ,np+Cn^δ) and (np^2-Cn^δ,np^2+Cn^δ) respectively, for some absolute constant C, and p,δ∈(0,1). We show that for such pseudo-random graphs the number of induced isomorphic copies of subgraphs of size s are approximately same as that of an Erdos-Renyi random graph with edge connectivity probability p as long as s=O(logn), when p∈(0,1/2]. When p∈(1/2,1) we obtain a similar result. We apply our results to different graph ensemble including exponential random graph models (ERGMs), thresholded graphs from high-dimensional correlation networks, Erdos-Renyi random graphs conditioned on large cliques, random d-regular graphs and graphs obtained from vector spaces over binary fields. If time permits, we will discuss dense graph limits of some exponential models of weighted networks.

Last updated: 2017/11/18 - 10:21am