Non-isomorphic subgraphs in random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912384352780288 |
|---|---|
| author | Krivelevich, Michael Zhukovskii, Maksim |
| author_facet | Krivelevich, Michael Zhukovskii, Maksim |
| contents | We establish the asymptotic behaviour of $μ(G(n,p))$, the number of unlabelled induced subgraphs in the binomial random graph $G(n,p)$, for almost the entire range of the probability parameter $p=p(n)\in[0,1]$. In particular, we show that typically the number of subgraphs becomes exponential when $p$ passes $1/n$, reaches maximum possible base of exponent (asymptotically) when $p\gg 1/n$, and reaches the asymptotic value $2^n$ when $p$ passes $2\ln n/n$. For $p\gg \ln n/n$, we get the first order term and asymptotics of the second order term of $μ(G(n,p))$. We also prove that random regular graphs $G_{n,d}$ typically have $μ(G_{n,d})\geq 2^{c_d n}$ for all $d\geq 3$ and some positive constant $c_d$ such that $c_d\to 1$ as $d\to\infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14623 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Non-isomorphic subgraphs in random graphs Krivelevich, Michael Zhukovskii, Maksim Combinatorics We establish the asymptotic behaviour of $μ(G(n,p))$, the number of unlabelled induced subgraphs in the binomial random graph $G(n,p)$, for almost the entire range of the probability parameter $p=p(n)\in[0,1]$. In particular, we show that typically the number of subgraphs becomes exponential when $p$ passes $1/n$, reaches maximum possible base of exponent (asymptotically) when $p\gg 1/n$, and reaches the asymptotic value $2^n$ when $p$ passes $2\ln n/n$. For $p\gg \ln n/n$, we get the first order term and asymptotics of the second order term of $μ(G(n,p))$. We also prove that random regular graphs $G_{n,d}$ typically have $μ(G_{n,d})\geq 2^{c_d n}$ for all $d\geq 3$ and some positive constant $c_d$ such that $c_d\to 1$ as $d\to\infty$. |
| title | Non-isomorphic subgraphs in random graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.14623 |