Prime Power Graphs for Groups of Lie Type,

We associate a weighted graph Δ(G) to each finite simple group G of Lie type. We show that, with an explicit list of exceptions, Δ(G) determines G up to isomorphism, and for these exceptions, Δ(G) nevertheless determines the characteristic of G. This result was motivated by algorithmic considerations. We prove that for any finite simple group G of Lie type, input as a black-box group with an oracle to compute the orders of group elements, Δ(G) and the characteristic of G can be computed by a Monte Carlo algorithm in time polynomial in the input length. The characteristic is needed as part of the input in a previous constructive recognition algorithm for G.