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}.

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.