Prime Power Graphs for Groups of Lie Type

By William M. Kantor, Á. Seress. 2002

63 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/4d0a529352066a9bf04b01aa71c628db71512016