On the capacity of graphs (Q2555083)

Let \(G_n\) be a graph of \(n\) vertices. Denote by \(v(G_n)\) the capacity of \(G_n\) (i.e. the number of non isomorphic spanned (in other words induced) subgraphs of \(G_n\)). Put \(v(n) = \max_{G_n} v(G_n)\). Clearly \(n \leq v(n) \leq 2^n-1\). Goldberg conjectured \(\lim_{n \to \infty} v(n)/2^n = 0\). The authors disprove this conjecture and in fact prove the following stronger Theorem. For every \(\epsilon >0 \) and almost all graphs \(G_n\) (i.e. all but \(o(2^{\binom{n}{2}}\) graphs \(G_n\)) we have \(v(G_n)>2^n-2^{n(1+\epsilon)/2}\). On the other hand for all graphs \(G_n\) we have \(v(G_n) \leq 2^n-2^{[n/2]}-1\). After submitting their paper the authors found that their main result has been proved earlier in a somewhat different form by \textit{A. D. Korshunov} [Mat. Zametki 9, 263-273 (1971; Zbl 0206.26201), Engl. translation in Math. Notes 9, 155-160 (1971; Zbl 0226.05118)].