Suppose $G$ is a group and $S \subset G$ is its finite subset. Let’s define the generating graph of $G$ in respect to $S$ as $Gen(G, S)$ - a graph $\Gamma(V, E)$, where $V = S$ and $E = \{(a, b) \in S \times S | a \neq b \text{ and } \langle \{a, b\} \rangle = G\}$.
Let’s define the generating graph representation number as the minimal number $GGRN(n)$, such that any $n$-vertex graph is isomorphic to a commuting subgraph of some group of order $GGRN(n)$.
My question is:
Is there some exact formula (or at least asymptotic) for $GGRN(n)$?
The only thing that I managed to prove, was the following bound:
$$GGRN(n) \leq p_{\frac{n(n+1)}{2}}\#$$
Here $p_n\#$ stands for primorial
Indeed, for any $n$ vertex graph $\Gamma(V, E)$, where $V = \{1, 2, … n\}$ such group and the corresponding subset can be explicitly constructed as
$$G = \langle a \rangle_{p_{\frac{n(n+1)}{2}}\#} $$ $$S = \{a^{f(v)\Pi_{(v, u) \in E}f((v, u))}| v \in V\}$$
where $f$ is some bijection from $V \cup V \times V$ onto first $\frac{n(n+1)}{2}$ primes.
However, this upper bound seems to be too large to be the best one: as the primorial has the asymptotic $p_n\# = e^{(1 + o(1))nlog(n)}$, then our bound is asymptotically $e^{(1 + o(1))n^2log(n)}$. Quite large, isn't it? Thus there is very likely to be something better. Much better. However, I do not know how to prove it.
