Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.16233 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913558157066240 |
|---|---|
| author | Bradač, Domagoj Christoph, Micha |
| author_facet | Bradač, Domagoj Christoph, Micha |
| contents | A folklore result attributed to Pólya states that there are $(1 + o(1))2^{\binom{n}{2}}/n!$ non-isomorphic graphs on $n$ vertices. Given two graphs $G$ and $H$, we say that $G$ is a unique subgraph of $H$ if $H$ contains exactly one subgraph isomorphic to $G$. For an $n$-vertex graph $H$, let $f(H)$ be the number of non-isomorphic unique subgraphs of $H$ divided by $2^{\binom{n}{2}}/n!$ and let $f(n)$ denote the maximum of $f(H)$ over all graphs $H$ on $n$ vertices. In 1975, Erdős asked whether there exists $δ>0$ such that $f(n)>δ$ for all $n$ and offered $\$100$ for a proof and $\$25$ for a disproof, indicating he does not believe this to be true. We verify Erdős' intuition by showing that $f(n)\rightarrow 0$ as $n$ tends to infinity, i.e. no graph on $n$ vertices contains a constant proportion of all graphs on $n$ vertices as unique subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16233 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unique subgraphs are rare Bradač, Domagoj Christoph, Micha Combinatorics A folklore result attributed to Pólya states that there are $(1 + o(1))2^{\binom{n}{2}}/n!$ non-isomorphic graphs on $n$ vertices. Given two graphs $G$ and $H$, we say that $G$ is a unique subgraph of $H$ if $H$ contains exactly one subgraph isomorphic to $G$. For an $n$-vertex graph $H$, let $f(H)$ be the number of non-isomorphic unique subgraphs of $H$ divided by $2^{\binom{n}{2}}/n!$ and let $f(n)$ denote the maximum of $f(H)$ over all graphs $H$ on $n$ vertices. In 1975, Erdős asked whether there exists $δ>0$ such that $f(n)>δ$ for all $n$ and offered $\$100$ for a proof and $\$25$ for a disproof, indicating he does not believe this to be true. We verify Erdős' intuition by showing that $f(n)\rightarrow 0$ as $n$ tends to infinity, i.e. no graph on $n$ vertices contains a constant proportion of all graphs on $n$ vertices as unique subgraphs. |
| title | Unique subgraphs are rare |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.16233 |