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 …
What is the meaning of the abbreviation AS? Associative Scheme?
Yes. If one defines analogous concepts for coherent configurations, then any group is CC-friendly, and a group is CC-free if and only if it is 2-transitive. So all the mystery here comes from the “symmetry” of the relations.
I’d say, it’s not even symmetry, it’s commutativity, for every commutative association scheme has a symmetrisation—gluing together opposite classes gives you a symmetric association scheme. That is, unless your commutative scheme is 2-homogeneous (and it’s a very restrictive class), you end ups with a nontrivial symmetric association scheme.
Yes, so commutativity gives you a similar, but slightly different, problem.
It would be good to understand how—if at all— (n-1)-factors subgroups live inside the n-factor examples. Are there some natural geometric sub-structures corresponding to this?
Doesn’t the Latin square construction generalize in a straightforward way? The ground set is for some . Connect if there are distinct indices such that . This fails only for because the resulting graph is too trivial.
Actually, maybe that doesn’t work because the graph is not strongly regular: it’s not enough to know just whether there are such indices ; we need to know how many, and how they’re arranged. So for each partition of the indices , define relation by if and only if the partition defined by coincides with . Does this work?
In the case we’re saved by the conjugacy classes thing, at least for finite groups. (Incidentally I think we need to combine each conjugacy class with its inverse to get symmetry.) On the other hand if is an infinite group with just two conjugacy classes then the corresponding diagonal group is 2-transitive!
I am not sure whether or not this works.
There is a nice graph invariant under the diagonal group with any number of factors, which I used to show that these groups are non-synchronizing. I thought at first that it would be a “Latin hypercube graph”, analogous to the Latin square graph for 3 factors. (The Latin hypercube being constructed as the set of all k-tuples with product 1 in the group.) But these graphs are not the same, and the one built from the hypercube does not admit the full diagonal group except in the case of 3 factors.
There is some subtlety here I think.
Your graph (the one in your “Hall–Paige conjecture…” paper) corresponds to my when consists of a 1-cell and an (n-1)-cell. I’m pretty sure that if you consider all partitions (up to isomorphism) together, then the whole thing is an association scheme.