A problem

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 …

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , , . Bookmark the permalink.

8 Responses to A problem

  1. Dima says:

    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.

      • Dima says:

        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.

  2. Yes, so commutativity gives you a similar, but slightly different, problem.

    • Dima says:

      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?

  3. Sean Eberhard says:

    Doesn’t the Latin square construction generalize in a straightforward way? The ground set is \Omega = T^k / T_\text{diag} for some k\geq 2. Connect x, x' \in \Omega if there are distinct indices i, j such that x_i x_j^{-1} = x'_i {x'_j}^{-1}. This fails only for k=2 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 i, j; we need to know how many, and how they’re arranged. So for each partition P of the indices \{1, \dots, k\}, define relation \sim_P by x \sim_P y if and only if the partition defined by x_i x_j^{-1} = x'_i {x'_j}^{-1} coincides with P. Does this work?

    In the k=2 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 T 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 \sim_P when P 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.