A local limit theorem for the edge counts of random induced subgraphs of a random graph
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_ | 1866909557757837312 |
|---|---|
| author | Balister, Paul Powierski, Emil Scott, Alex Tan, Jane |
| author_facet | Balister, Paul Powierski, Emil Scott, Alex Tan, Jane |
| contents | Consider a `dense' Erdős--Rényi random graph model $G=G_{n,M}$ with $n$ vertices and $M$ edges, where we assume the edge density $M/\binom{n}{2}$ is bounded away from 0 and 1. Fix $k=k(n)$ with $k/n$ bounded away from 0 and~1, and let $S$ be a random subset of size $k$ of the vertices of $G$. We show that with probability $1-\exp(-n^{Ω(1)})$, $G$ satisfies both a central limit theorem and a local limit theorem for the empirical distribution of the edge count $e(G[S])$ of the subgraph of $G$ induced by $S$, where the distribution is over uniform random choices of the $k$-set $S$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23164 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A local limit theorem for the edge counts of random induced subgraphs of a random graph Balister, Paul Powierski, Emil Scott, Alex Tan, Jane Combinatorics Probability Consider a `dense' Erdős--Rényi random graph model $G=G_{n,M}$ with $n$ vertices and $M$ edges, where we assume the edge density $M/\binom{n}{2}$ is bounded away from 0 and 1. Fix $k=k(n)$ with $k/n$ bounded away from 0 and~1, and let $S$ be a random subset of size $k$ of the vertices of $G$. We show that with probability $1-\exp(-n^{Ω(1)})$, $G$ satisfies both a central limit theorem and a local limit theorem for the empirical distribution of the edge count $e(G[S])$ of the subgraph of $G$ induced by $S$, where the distribution is over uniform random choices of the $k$-set $S$. |
| title | A local limit theorem for the edge counts of random induced subgraphs of a random graph |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2503.23164 |