Development of the Classification of Small Association Schemes

An association scheme of order n is a certain collection of nxn matrices whose entries are 0’s and 1’s that form the basis for an algebra under both ordinary and elementwise multiplication.  They share many of the algebraic properties of finite groups, and have many applications in graph theory and design theory.   One of the difficulties with association schemes is that there are many more association shemes of a given order than there are groups of that order.  During the first five years of the last decade, a group of Japanese researchers classified all association schemes of order at most 30, using the computer algebra program GAP (Groups, Algorithms, and Programming) and some parallel computing algorithms they developed using C+.  They  posted their work on a website called the “Classification of Small Association Schemes”.  This website contains a complete list of these association schemes up to permutation isomorphism, a list of their their character tables, fusion information for the list of association schemes of a given order, and information about which schemes in the list lie in interesting classes.  Limited information was also provided for association schemes of orders 31-40.

The project I am proposing will revisit the classification of association schemes of order up to 30.  We will first try to develop an algorithm that will give accurate fusion data for schemes of orders 24 to 30.  We will then try to extend the classification of small association schemes as far as this machine will allow.   Any results we achieve or programming methods we develop will be posted on a website to make them publicly available to researchers in discrete mathematics and computational algebra. 

The student’s role will be to collaborate with me on the development and testing of programs written in GAP and C+.   They will be expected to learn some of the basic algebraic properties of the 0,1-matrices in a scheme, properties of permuation groups, and permutation matrices.  They will be expected to contribute toward the successful development of a computer program for generating and characterizing these matrices using GAP’s built in permutation matrix and graph automorphism functions and/or C+ search algorithms.

Sourav Sikdar
Faculty Supervisor: 
Dr. Allen Herman