English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Induced Subgraphs in Sparse Random Graphs with Given Degree Sequence

MPS-Authors
/persons/resource/persons44475

Gao,  Pu
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:1011.3810.pdf
(Preprint), 307KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Gao, P., Su, Y., & Wormald, N. (2010). Induced Subgraphs in Sparse Random Graphs with Given Degree Sequence. Retrieved from http://arxiv.org/abs/1011.3810.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DBFD-4
Abstract
For any $S\subset [n]$, we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is a given graph $H$ on the vertex set $S$. The result holds for any $d=o(n^{1/3})$ and is further extended to $\mathcal{G}_{{\bf d}}$, the probability space of random graphs with a given degree sequence $\bf d$.