A new formula for the generating function of the numbers of simple graphs (Q2822180)

Let \(n\) be a positive integer, \(a_{n,i}\) the number of simple graphs with \(n\) vertices and \(i\) edges, and \(g_n(z) = \sum_{i=0}^m a_{n,i}z^i\), where \(m = n(n - 1)/2\), be the ordinary generating function for the sequence \(\{a_{n,i}\}\) (see the sequence A008406 from the On-Line Encyclopedia of Integer Sequences (OEIS), https://oeis.org). We have \(g_1(z) = 1\), \(g_2(z) = 1 + z\), \(g_3(z) = 1 + z + z^2 + z^3\), \(g_4(z) = 1 + z + 2z^2 + 3z^3 + 2z^4 + z^5 + z^6\). A formula for \(g_n(z)\) in terms of group cycle index has been found by \textit{F. Harary} [Trans. Am. Math. Soc. 78, 445--463 (1955; Zbl 0065.16702)], on the basis of Polya's efficient method for counting graphs (see [\textit{G. Pólya}, Acta Math. 68, 145--254 (1937; Zbl 0017.23202)], and the book ``Graphical Enumeration'' (by [\textit{F. Harary} and \textit{E. M. Palmer}, York-London: Academic Press, XIV (1973; Zbl 0266.05108)]). The reviewed paper derives another formula for \(g_n(z)\) by an approach of invariant theory. For this purpose, the authors consider the (\(m\)-dimensional) vector space \(V_n\) of weighted graphs on \(n\) vertices over a field \(K\), and the natural action on \(V_n\) (by permutations of the basic vectors) of the pair group \(S_n ^{(2)}\) of the permutation group \(S_n\) on the set \([n] = \{1, 2, \dots, n\}\); \(S_n^{(2)}\) is the permutation group induced by \(S_n\), which acts on the set \([n]^{(2)}\) of \(2\)-subsets of \([n]\). This gives rise to an action of \(S_n^{(2)}\) on the \(K\)-algebra of polynomial functions \(K[V_n] = K[y_{i,u}: {i, u} \in [n]^{(2)}]: = K[x_1, \dots, x_m]\), which induces an action of \(S_n^{(2)}\) upon the \(K\)-algebra \(K[V_n^0]\), where \(V_n^0\) is the set of simple graphs. Denote by \(K[V_n]^{S_{n}^{2}}\) and \(K[V_n^0]^{S_{n}^{2}}\) the corresponding algebras of invariants, and by \(I_m\) the ideal of \(K[V_n]\) generated by the polynomials \(x^ 2 - x_j\), \(j = 1, \dots, m\). The paper under review proves that \(K[V_n^0]\) and \(K[V_n^0]^{S_{n}^{2}}\) are isomorphic to the quotient algebras \(K[V_n]/I_m\) and \(K[V_n]^{S_{n}^{2}}/I_m^0\), respectively, where \(I_m^0 = I_m \cap K[V_n]^{S_{n}^{2}}\). Observing that \(K[V_n^0]\) decomposes into the direct sum \(\oplus_{t=0}^m W_t\) of \(S_n^{(2)}\)-invariant \(K\)-subspaces, where \(W_t\) is the \(K\)-vector space generated by the elements \(x^{\varepsilon_ {1}} \dots x_m^{\varepsilon_ {m}}\), \(\varepsilon_1 + \dots + \varepsilon_m = t\), \(\varepsilon_k \in \{0, 1\}\), the authors show that the dimension of \(W_t\) is equal to the number \(a_{n,t}\), for each index \(t\). Using these results, they deduce their formula for \(g_n(z)\).