Graphs on groups, 4

Here is a small problem, mixing group theory and number theory, which might appeal to someone.

A couple of definitions. The power graph of a group G has an edge from x to y if one is a power of the other; the enhanced power graph has an edge from x to y if both are powers of an element z.

Every edge of the power graph is an edge of the enhanced power graph. So the clique number of the enhanced power graph is at least as great as that of the power graph. But in the other direction, there is a function f on the natural numbers such that, if the clique number of the power graph is m, then that of the enhanced power graph is at most f(m). The proof below gives a function growing exponentially.

Problem: What is the best possible function here?

So here is the proof. It is easy to see that a maximal clique in the enhanced power graph is a maximal cyclic subgroup of G. (The only non-trivial point in the proof is to show that, if a set of elements of a group has the property that any two generate a cyclic subgroup, then the whole set generates a cyclic subgroup.) So the clique number of the enhanced power graph is the maximum order of a cyclic subgroup.

The clique number of the power graph is not so straightforward. But the power graph of a cyclic group of prime power order is complete; so the clique number is at least as great as the maximum order of a cyclic subgroup of prime power order. Let this number be m. Then the exponent of the group is at most the least common multiple of the numbers 1,2,…,m, and the clique number of the enhanced power graph does not exceed this value. Now it follows easily from the prime number theorem that this lcm is about e^m.