Logo
All Random Solved Random Open
SOLVED - $25
We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$. Is there a graph on $n$ vertices with \[\gg \frac{2^{\binom{n}{2}}}{n!}\] many distinct unique subgraphs?
A problem of Erdős and Entringer [EnEr72], who constructed a graph with \[\gg 2^{\binom{n}{2}-O(n^{3/2+o(1)})}\] many unique subgraphs. This was improved by Harary and Schwenk [HaSc73] and then by Brouwer [Br75], who constructed a graph with \[\gg \frac{2^{\binom{n}{2}-O(n)}}{n!}\] many unique subgraphs.

Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.

Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for such a construction and \$25 for a proof that no such construction is possible.

Bradač and Christoph [BrCh24] have proved the answer is no: if $f(n)$ is the maximum number of unique subgraphs in a graph on $n$ vertices then \[f(n) = o\left(\frac{2^{\binom{n}{2}}}{n!}\right).\] (Quantitatively the $o(1)$ in their argument can be taken to be $O(\frac{\log\log\log n}{\log\log n})$.)