Since I have been saying rather a lot about association schemes and coherent configurations lately, I thought I would mention an open problem. This is probably one for the experts, and I guess it has been ignored because of the problems of terminology I mentioned in the last post (and also because it appeared in a conference proceedings).
So to recall: a coherent configuration is, in essence, the combinatorial structure arising from the partition of the set of ordered pairs from X into orbits of a permutation group on X. In order of increasing specialisation, we have the following kinds of structure:
- coherent configurations;
- homogeneous configurations (where the diagonal is a single relation rather than a union of relations: this would arise in the case that the group is transitive on X;
- commutative configurations (where the relation matrices commute; this would arise in the case where the group action is multiplicity-free);
- symmetric configurations (where the relations are all symmetric; this would arise in the case where the group is generously transitive, that is, any pair of points of X can be interchanged by an element of G).
I will use the term association scheme for “symmetric coherent configuration”. If you prefer a different convention, you may think the problem I pose is less interesting; but the interest of a problem should not depend on the language used to describe it!
One of the features of coherent configurations which is crucial for their use in the graph isomorphism problem is that the coherent configurations on a given finite set form a lattice. The join operation in the lattice is just the join in the lattice of set partitions. The meet is defined because there is at least one coherent configuration finer than two given configurations (namely the trivial configuration where all relations are singletons), and the meet of the two is then just the join of all the configurations finer than both.
A permutation group G on X is
- primitive if it is transitive and preserves no non-trivial partition of X;
- basic if it is primitive and preserves no Hamming structure (Cartesian power structure) on X;
- 2-homogeneous if it acts transitively on the set of unordered pairs of distinct elements of X;
- 2-transitive if it acts transitively on the set of ordered pairs of distinct elements of X;
- generously transitive if any two distinct points of X can be exchanged by an element of G.
These are all standard in permutation group theory, but we need to add a few more, defined in terms of association schemes. The permutation group is
- stratifiable if the configuration formed by the symmetrised orbits of G on ordered pairs (taking the union of converse pairs of orbits) is an association scheme;
- AS-friendly if there is a unique minimal G-invariant association scheme on X;
- AS-free if the only G-invariant association scheme is the one with just two classes.
These concepts are related by the following implications:
Moreover, none of these implications reverses, and no further implications hold except for those obtained from these by the transitive law.
This theorem, and examples to prove the claims, are in my paper “Coherent configurations, association schemes, and permutation groups”, in Groups, Combinatorics and Geometry, World Scientific, Singapore, 2003.
The problem concerns AS-free groups. These are primitive, and basic (since otherwise they would preserve a Hamming association scheme), and so, by the O’Nan–Scott theorem, they are affine, diagonal or almost simple. The affine groups must be 2-homogeneous. Almost simple examples have been constructed computationally by Faradzev, Klin and Muzichuk; but they are few and far between, and there seems to be no pattern to their occurrence.
This leaves diagonal groups. Now a diagonal group whose socle has two simple factors preserves the conjugacy class scheme of the simple group; and one with three simple factors preserves the strongly regular Latin square graph associated with the Cayley table of the simple group. For four or more factors, the answer is unknown.
Problem: Are primitive diagonal groups with four or more factors in their socles AS-free or not?
The smallest possible degree of such a group would be 216000, so probably computation is not feasible …