2016/10/12 by Anirban Basak, Basak, Anirban, Shankar Bhamidi +5
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1610.03762
openalex publication_date 2016/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (np2- C nδ, np2 +C nδ) 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 Erdős-Réyni random graph with edge connectivity probability p as long as s ≤ (((1-δ)\wedge (1)/(2))-o(1))log n/log (1/p), when p ∈ (0,1/2]. When p ∈ (1/2,1) we obtain a similar result. Our result is applicable for a large class of random and deterministic graphs including exponential random graph models (ERGMs), thresholded graphs from high-dimensional correlation networks, Erdős-Réyni random graphs conditioned on large cliques, random d-regular graphs and graphs obtained from vector spaces over binary fields. In the context of the last example, the results obtained are optimal. Straight-forward extensions using the proof techniques in this paper imply strengthening of the above results in the context of larger motifs if a model allows control over higher co-degree type functionals.