Multiply transitive permutation sets

Bill Fahle asked, in a comment on the preceding post, for information about sets of permutations which are multiply transitive (but not necessarily groups or sharply multiply transitive).

I take “t-transitive set” to mean a set S of permutations of {1,…,n} such that, given any two t-tuples of distinct elements of {1,…,n}, there is at least one permutation in S carrying the first to the second.

I don’t know much in general about this. One can easily construct such a set by listing all pairs of t-tuples, and for each pair, choosing a permutation mapping the first to the second. The size of such a set is not more than the square of the number of t-tuples, which is not too large if t is relatively small.

However, I think a more interesting question concerns uniformly t-transitive sets, those for which, given any two t-tuples of distinct elements, there is a constant number μ of permutations in S carrying the first to the second.

Any t-transitive permutation group, and any sharply t-transitive permutation set, is thus uniformly t-transitive. But there are many others.

Nearly 30 years ago, Eiichi Bannai gave me a construction for uniformly t-transitive sets of permutations. I do not know whether it has been published anywhere; so here it is.

We start with a t-(n,k,λ) design, that is, a collection B of k-element subsets of {1,…,n} with the property that any t points are contained in exactly λ sets in B. Many such designs exist; in particular, Teirlinck’s celebrated theorem states that, for every t, there exists such a design with k = t+1 and λ a function only of t, independent of n (for n satisfying a certain congruence).

Now given such a design, assume (without loss of generality) that {1,…,k} is one of the blocks of the design. Let S consist of all permutations of {1,…,n} which map {1,…,k} to a block of the design. Then the set S is uniformly t-transitive.

This sounds implausible at first, since the set {1,…,k} so obviously plays a special role. Here is a proof that it works (with some details omitted).

Take two t-tuples a and b. Suppose that s points of a lie among {1,…,k}; without loss of generality, the first s points. Now choose a block B containing the first s points of b but none of the others. From the theory of t-designs, it is known that the number of such blocks only depends on s and the parameters of the design. Call this number λs, say. Then it is clear that the number of permutations in S mapping a to b and carrying {1,…,k} to B is (ks)!(nkt+s)!. Multiplying this number by λs gives the total number of permutations in S carrying a to b.

So it remains to show that this number is independent of s. I had hesitated to do this calculation, because the usual proof of the constancy of λs is by an inclusion-exclusion argument giving an unwieldy alternating sum. But knowing that λs is constant, we can proceed as follows: counting choices of a block B and a t-set T meeting it in s points, we see that λs is proportional to {k choose s}{nk choose ts}, and some calculation shows that this is exactly what we want.

This gives an upper bound for the size of the smallest uniformly t-transitive set, depending on which t-design you use. Better upper bounds in special cases can be found from groups or sharply transitive sets, but this construction is the most general that I know.

Lower bounds are more problematic. There is a machine invented by Philippe Delsarte for finding lower bounds of sets in association schemes satisfying certain t-design-like conditions. These could in principle by applied to the conjugacy class association scheme of the symmetric group. I don’t know whether anyone has done this, and I rather doubt that it will do better than the trivial lower bound of n!/(nt)! corresponding to sharply transitive sets. The reason for my belief is that, if there were a possibility of getting a better bound this way, someone would no doubt have used it to prove the non-existence of a sharply 2-transitive set of permutations on {1,…,10} (and hence of a projective plane of order 10), for example.

Advertisements

About Peter Cameron

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

10 Responses to Multiply transitive permutation sets

  1. Bill Fahle says:

    I admit I was being a little coy. While the concept of uniformly transitive permutation sets didn’t occur to me, the title of your post is the title of my freshly minted dissertation. Your construction is new to me also. We considered the minimal cardinality of any t-transitive set, defined as you have it. I called them (n, k)-transets, where k is your t. It is one of those things that computer scientists look at rather than mathematicians, because as you hinted, the sets are not always tidy, and are therefore difficult to write proofs about. However we have found a number of theorems giving constructions for non-trivial sets for all n and t (thus giving upper bounds), and also found lower bounds greater than 1+(n!/(n-k)!) for k >= 3 when there is nonexistence on sharply 2-transitive sets (such as through Bruck-Ryser, or Quistorff’s result for 4<=n-k<=k, or Lam et al. for n=10). I'm writing up a paper for submission to ESA 2012 in Ljubjana, Slovenia. My current quest is to prove exact bounds for x=min |y| | y is a (6,2)-transet, which as of now we know 33<=x<=37.

  2. Dima says:

    Delsarte bounds on assoc. schemes of conjugacy classes of $S_n$ were applied by Tarnanen (Eur. J. Comb. 20(1999)), and he obtained in this way nontrivial bounds on permutation codes.
    Lately coding theorists work on this more and more, I am told.

    • Delsarte’s results give upper bounds for “codes” (where you specify the relations which are allowed to occur) and lower bounds on “designs” (where you specify the “strength” in a rather technical sense). I know Tarnanen’s paper; my point was that I don’t know any papers exploiting the lower bounds for permutation sets, or even interpreting what “strength” means for these).

      • Dima says:

        I realise that I don’t know anything about Delsarte’s approach to lower bounds. Could you give a reference?

    • Dima says:

      as well, semidefinite programming based methods could in principle be applied here to certain coherent configurations (of which the assoc. schemes of conjugacy classes are sub-algebras). This has been carried out by Lex Schrijver in 2005 to improve bounds on “usual” binary codes, but it’s certainly applicable to permutation codes too.

      • I think that the best reference to Delsarte’s approach is his own exposition of it in his thesis, which was published more-or-less complete in a volume of Philips Research Reports Supplements in the early 1970s.

        You are right that the most important new idea to come along since Delsarte’s thesis is semidefinite programming. I don’t know for sure but I imagine that it can help with the lower bounds as well as the upper bounds. But as I said, I don’t think that any general technique will, for example, improve on the lower bound n(n−1) for a 2-transitive permutation set, since this would be a painless way of showing that projective planes don’t exist.

      • Bill Fahle says:

        Agreed in the general case. I wonder, though, if we can prove lower bounds in specific cases where a sharp 2-transitive set is known not to exist, such as when n=6. Even finding an exact value for this one small case is proving impossible to compute via brute force, because of the C(720, ~30) search factor. The general upper bound is much more interesting, however, as we have found methods for building (n+1,k) sets from an (n,k) set and n copies of a (n,k-1) set, giving a fairly good upper bound, and we’re finding new theorems to improve this.

      • The reason I think Delsarte’s methods (and probably also semilinear programming) won’t help is that the answer you want depends on the arithmetic structure of n, whereas the methods seem to pay no attention to this. As you know, a sharply 2-transitive set exists if n is a prime power but not if n is congruent to 2 or 3 (mod 4) and not the sum of two squares. The algebraic methods tend to give bounds uniform in n.

        I wonder if your new methods give (or can be adjusted to give) upper bounds for uniformly k-transitive sets. Maybe you can beat Bannai’s method.

  3. my name is Vineet George I have done extensive research on Combination and Permutation. This research which i have done is written on a book known as Junction (an art of counting combination and permutation). To see my research visit my website.

    https://sites.google.com/site/junctionslpresentation/home

    or e-mail me at softlaws4095@gmail.com

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 )

Google+ photo

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

Connecting to %s