Large subgraphs in pseudo-random graphs

MaRDI QIDQ6278558zbMATH OpenFDO

Authors Anirban Basak, Shankar Bhamidi, Suman Chakraborty, Andrew B. Nobel

Publication date 12 October 2016

Abstract: 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-C{n}^{d}elta,np+C{n}^{d}elta)$ and $(n{p}^2-C{n}^{d}elta,n{p}^2+C{n}^{d}elta)$ respectively, for some absolute constant $C$, and $p,deltain(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 ErdH{o}s-R'{e}yni random graph with edge connectivity probability $p$ as long as $sle(((1-delta)wedgefrac12)-o(1))logn/log(1/p)$, when $pin(0,1/2]$. When $pin(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, ErdH{o}s-R'{e}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.

This page was built for publication: Large subgraphs in pseudo-random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6278558)