What are the largest known regular transposal squares and double transposal rectangles?

No solution was found in the collected postings.

[ Editor: the question was sent to the archive by Richard Sabey
  <rsa@walnut.gpsemi.com> in October 1994, with this example and
  explanation.  No largest examples were given in reply, but Chris Long
  sent the characterization below. ]

By a double transposal rectangle I mean a rectangular arrangement of
letters, where each row and each column is a transposal of a word. No two
of these lines should be transposals of each other. Somewhat like this:

        some E M S O
        what A W T H
        like L I K E
        this T H I S

             l w k h
             a h i o
             t i t s
             e m s e

Sometimes you can choose different words for rows or columns because the
letters can be transposed in different ways to make a word.

I count two double transposal rectangles "the same" if you can get from
one to the other by reflecting in the main diagonal, permuting rows, and
permuting columns.

By a regular transposal square I mean a square arrangement of letters,
symmetrical about the diagonal from top left to bottom right, where each
row is a transposal of a word. No two of the rows should be transposals
of each other.

I count two regular transposal squares "the same" if you can get from
the one to the other by permuting rows, then permuting columns so as to restore
symmetry.

-- Richard Sabey <rsa@walnut.gpsemi.com>

The regular transposal square problem appears to be a close relative
of the marriage problem in combinatorics.

The Marriage Problem:

  Let there be m boys and n girls.  Each boy likes some subset of
  the girls, perhaps none.  Is it possible for each boy to marry a
  girl they like?

  It turns out that this can happen if and only if for each set of
  k boys, between them they like at least k different girls.

Regular Transposal Squares:

  Consider a set W of words.  Then they can form a regular transposal
  square of size |W| if and only if for each w \in W and for each
  subset S of W, w \notin S, the total number of letters that the
  words in S have in common with w is >= |S|.

For example, consider the three words "abc", "ade", "aeg".  Now, the
number of letters "abc" has with "ade"&"aeg" is only 1 (the "a");
it follows that a regular transposal square cannot be formed.  However,
replacing "aeg" with "ace" we get a collection that satisfies the
criteria, so a square can be formed.  In fact, one such square is

  bac
  ade
  cea

I don't know if a better characterization is possible, but the proof
that the criteria given above works is constructive, inductive, and
quite fast i.e. when run on a given set of n words it'll quickly return
a square of size n or let you know none exists.  Coming up with a likely
candidate set of n words is a bit trickier, however, as is finding all
regular transposal squares of order m given a set of n words, n>m.  As
this is a very interesting problem, hopefully I'll be able to come up
with something; but then again, I estimate that considering the small
number of letters in the alphabet, just about any set of n words for n
large enough should work, so perhaps this is not a real problem.

-- Chris Long <clong@cnj.digex.net>

[ Editor: a 20x20 regular transposal square, mailed by Chris Long to
Richard Sabey and the archive in October 1994 as a revision of an
earlier one; each row is a transposal of the word to its right. ]

Here's another 20x20 that gets rid of the questionable word.  I don't
know how large a regular transposal square is possible just using NI2
or NI3.  I chose 20-letter words for a first try since there were
enough NI2 words (about 200) so that I could choose a nice subset of
20.  You do have to be somewhat careful about which words you choose,
since it's fairly easy to make it impossible, usually as the result of
"orphan" letters (the first set of 20 that I tried had this problem).
Chris, what are the counts of the NI3 words of lengths 20 and above?  I
haven't even considered double transposal squares yet.

uaacghhilmooopprrrtt   ultraphotomicrograph
anaceeghilllpoorttoo   anthropoteleological
aaeacghllilopnoortop   paleoanthropological
ccarahglohhirnootppo   photochronographical
gecaialnlolhtoptpooy   phytopaleontological
heghapaceoiplttrllyo   phototelegraphically
hghglaaaceptirrponoo   anthropogeographical
ihllncaoaptgyrreoegn   roentgenographically
lilolecatporaaeeoomg   palaeometeorological
mlihooepptrosoyoagnc   oophorosalpingectomy
ollhliptoryoeeacgcis   electrophysiological
oloihptgroohyaclimsl   histomorphologically
opprtliyaseylcgahhlm   plethysmographically
ponnotrraoeacycghmhi   chronocinematography
poooptrreyacgcnhmiih   cinephotomicrography
rrootrpeeoclaghnhcci   electrochronographic
rtrtploooagihhmhiacc   lithochromatographic
rttpolneogcmhmicaiaa   phoneticogrammatical
toopoyogmnislhiccaia   physiologicoanatomic
topoyoongcslmihicaai   anatomicophysiologic

-- Chris Long <clong@cnj.digex.net>