Large motifs in homogeneous networks
Speaker 
Dr. Anirban Basak
ICTS, Bangalore


When 
Nov 19, 2018
from 02:00 PM to 03:15 PM 
Where  LH 006 
Add event to calendar 
vCal iCal 
Abstract: A graph is termed to be homogeneous if the degrees and the codegrees (the number of common neighbors of a pair of vertices) are approximately the same throughout the graph. In this talk, we will discuss the existence and the number of isomorphic copies of subgraphs in large homogeneous graphs. Under the assumption that in a homogeneous graph on \(n\) vertices the degrees and the codegrees are close to \(np\) and \(np^2\), respectively, with an error of at most \(O(n^\delta)\), for some \(p \in (0,1)\) and \(\delta \in [0,1)\), we will show that for some constant \(C_\delta >0\), depending only on \(\delta\), the number of isomorphic copies of any subgraph of (vertex) size at most \(C_\delta \log n /\log(1/p)\) is asymptotically same as that of an Erd\({o}\)sR\('{e}\)nyi graph with edge connectivity probability \(p\). The constant \(C_\delta\) will be shown to be optimal. This result is applicable to a wide class of graphs including but not limited to Exponential Random Graph Models, threshold graphs from highdimensional correlation networks, and Erd\({o}\)sR\('{e}\)nyi graphs conditioned on large cliques.
The talk is based on a joint work with Shankar Bhamidi, Suman Chakraborty, and Andrew Nobel.