Posts Tagged ‘combinatorics’

Supersymmetric Latin squares

July 4, 2011

Latin squares have long been a staple object of study of combinatorics and recreational mathematics.  A Latin square of size n is an n\times n array of elements of some set of n symbols such that each symbol appears exactly once in each row and in each column.  For our purposes, it will be important to have the set of indices for the rows and columns and the set of symbols be the same set.  For some finite index.  The “obvious” choice for the index sets will be \{1,2,3,\ldots,n\} or \{0,1,2,\ldots,n-1\}, but we could use any finite set.  Whenever I display a Latin square here, I will use one of these sets, with row numbers increasing from left to right and column numbers increasing from top to bottom.

It’s illustrative to move from the graphical definition of a Latin square to something more symbolic.  A Latin square on an index set I is a function f assigning each element of I \times I an element I such that for each fixed a\in I, f(a,-) and f(-,a) realize each value in I exactly once.  Blurring the distinction between (I \times I) \times I) and I \times I \times I, we can recast the above definition in the following way.

Definition.  A Latin square on a (finite) index set I is a subset S of I\times I\times I such that, for any fixed a,b\in I, each of the incomplete triples (a,b, - ), (a, - , b), (-, a, b) can be completed to an element of S in exactly one way.  (That is, a subset of I\times I\times I with size |I|^2 whose projection onto any pair of coordinates is exactly I\times I.)

Notice that “function-ness” and the conditions on the rows and columns are absorbed into one pleasantly symmetric condition.  This explains the mysterious fourth paragraph of this Not About Apples post.  (This definition also generalizes gracefully to orthogonal Latin squares; a list of k orthogonal squares corresponds naturally to a subset of I^{k+2} with size |I|^2 whose projection onto any pair of coordinates is exactly I\times I.)  This symmetry also means that S_3 acts naturally on the set of Latin squares on a particular index set by permuting the coordinates.  This led me to think about the following definition.

Definition. A supersymmetric Latin square (ssLs) is a Latin square which (viewed a subset of I\times I\times I) is closed under permutation of coordinates.

That is, a supersymmetric Latin square is in an orbit by itself under the S_3-action.

Example.

There are three supersymmetric Latin squares on {0,1,2}.

021   102   210
210   021   102
102   210   021

For ordinary Latin squares, there is another kind of symmetry.  Rows can be permuted, columns can be permuted, and the symbols themselves can be permuted.  That is, the symmetric group on the index set acts naturally on the set of Latin squares in three ways, by acting on the first, second, or third coordinate of the triples.  This justifies the common convention of assuming without loss of generality that a Latin square has the symbols listed in order across the first row and down the first column; since each of these actions is free (though the composite action of S_I\times S_I \times S_I is not), we have an instant proof that n! divides the number of Latin squares on a set of n (and if you are a little careful, you can improve this to n!(n-1)! for almost no extra work).

This doesn’t work for supersymmetric Latin squares, though; these actions of S_I are not compatible with the action of S_3 in the definition of supersymmetry.  There does, however, exist a natural action of S_I on the set of supersymmetric Latin squares on I, where a permutation of I acts on all permutation .  In further contrast with the ordinary case, this action is not free; it’s not even faithful.

Example.

The first ssLs listed above is stabilized by all of S_3.  The latter two are stabilized by the even permutations; odd permutations interchange them.

I call two supersymmetric Latin squares on I equivalent if they are in the same orbit of this S_I-action.  Likewise, ssls on I is equivalent to an ssls on J if the latter is the image of the former under some bijection I\to J acting on every component of every triple.  I’m interested in classifying supersymmetric Latin squares of size n, up to equivalence.

For n=1,2,4,5, it’s not hard to check that there are no examples.  (Edit: as noted in the comments, that’s just plain not true.)  For n=3 there are the two already given.  Call them \alpha, \beta in the order they are listed in the first example.

There are infinitely many supersymmetric Latin squares. Let me briefly explain the construction of all the ones I know.

There is a natural product on Latin squares.  If S (resp. S’) is a Latin square on I (resp. I’), then we define S\times S', a Latin square on I\times I', by \left\{((a,a'),(b,b'),(c,c'))\in (I\times I')^3~:~(a,b,c)\in S , (a',b',c')\in S'\right\}.  I leave to the reader the verification that this is fact a Latin square, and that it is supersymmetric if S and S’ are.

Since we have two ssLs’s of size 3, we can construct ssLs’s of size 9.  There are four possibilities to consider: \alpha\times \alpha, \alpha\times\beta, \beta\times\alpha, \beta\times\beta.  All will be supersymmetric, of course, but they cannot all be inequivalent.  The middle two are certainly equivalent, since the product operation is commutative up to equivalence.  Now we can just write out  \alpha\times \alpha, \alpha\times\beta, \beta\times\beta.  (In order to write the squares in my preferred way, I have to choose a bijection between \{0,1,2\}^2 and \{0,1,2,3,4,5,6,7,8\}; here I use the one provided by base 3 notation.)

021687354   102768435   435102768
210876543   021687354   354021687
102768435   210876543   543210876
687354021   768435102   102768435
876543210   687354021   021687354
768435102   876543210   210876543
354021687   435102768   768435102
543210876   354021687   687354021
435102768   543210876   876543210

It’s not obvious, but the second and third squares are actually equivalent under e.g. the permutation (0)(14562873).

The same approach enables us to construct two supersymmetric Latin squares \alpha^k=\alpha\times\cdots \times \alpha and \beta^k=\beta\times\cdots \times \beta of size 3^k for k=1,2,3,\ldots.  Any mixed product of \alpha‘s and \beta‘s is equivalent to \beta^k, so we have found all the ssLs’s which arise as products of the ones we know.  These two are inequivalent, because \alpha^k contains all triples of the form (a,a,a) and \beta^k contains no such triples.

Questions.

  1. Do supersymmetric Latin squares exist of any size which is not a power of 3?
  2. For size any positive power of 3, we have found two inequivalent ssLs’s.  Is this a complete list?
  3. We could also consider less strict symmetry conditions, requiring only that the Latin square be invariant under some subgroup of S_3.  If the subgroup is generated by a transposition, then this boils down to considering Latin squares which are symmetric (in the sense of symmetric matrices).  But what about requiring only A_3-symmetry, that the square be invariant under cyclic shifts.  (I haven’t really thought about this yet, but it seems potentially interesting.)

Comparing Nested Binomial Coefficients

August 13, 2010

Lately I’ve been becoming more and more interested in enumerative combinatorics.  Back in the days of contest math problems, I loved counting problems; they were one of my best strengths.  Until the gorgeous sequence of talks by Richard Stanley at January’s Joint Meetings, I never really realized that enumerative combinatorics was of interest to “real, serious” mathematicians.  Now that I know, I’ve been thinking more and more about these problems.

So last weekend at MathFest, I was pleased to learn of the following inequality involving binomial coefficients.

Let 1<a<b<c be positive integers. \displaystyle \binom{\binom{c}{b}}{a}<\binom{\binom{c}{a}}{b}.

Apparently this inequality has been proven, but only by a lengthy and uninspiring computation involving estimating gamma functions.  There is not yet a combinatorial proof.  What do I mean by a combinatorial proof of an inequality?  I mean an interpretation of each of the nested binomial coefficients as the number of objects in some set, and then an explicit bijection of one set with a proper subset of the other.

In this case, I am thinking of \displaystyle \binom{\binom{c}{b}}{a} as counting the number of ways to choose a different (not necessary disjoint) b-element subsets of a set of c elements.  For definiteness I can take the set of c elements to be \{1,2,3,\ldots, c\}, list the elements of a subset in increasing order, and list the subsets in lexicographical order.  This suggests the following combinatorial formulation of the inequality.

Let 1<a<b<c be positive integers.  Let S be the set of a\times b matrices with entries in \{1,2,3,\ldots, c\}.  Let A consist of those matrices in S for which the elements in each row are strictly increasing, and the rows are lexicographically strictly increasing.  Let B consist of those matrices in S for which the elements in each columns are strictly increasing, and the columns are lexicographically strictly increasing.  Find an explicit bijection of A of some proper subset of B.

Haven’t cracked it yet, but I’m enjoying the attempt.

Counting Problems in Apollonian Circle Packings

July 8, 2010

I’ve spent most of the last year and a half contemplating pretty pictures like the one that follows. These pictures, called Apollonian circle packings, have captivated me since I heard Sarnak speak on them at the 2009 Joint Meetings.

Apollonian circle packing with root quadruple (-1,2,2,3)Apollonian circle packing with root quadruple (-1,2,2,3)

Pictures such as these are constructed by inscribing a triple of three circles inside a larger circle, inscribing a circle in each lune created, and iterating the process. The numbers labelling the circles are the curvatures (1/radius). (The exterior circle has radius 1, but because it is exterior we say that it’s curvature is -1 by convention.) To a number theorist, the amazing fact is that if the four circles we begin with have integral curvature (in the figure, the starting circles have curvature -1, 2, 2, 3), or indeed if any four mutually tangent circles in such a packing have integral curvature, all the rest of the circles automatically have integral curvature. Such pictures are called integer Apollonian circle packings (IACPs).

One question I like to think about, the one that got me into the subject, is to think about which numbers appear in IACPs. That is, think about all PACPs at once. How many times does a given curvature appear? What pairs of numbers can appear? How often? All of my counting is up to symmetry; the picture above, for example, accounts for only one occurrence of 6, not four, and only one occurrence of the pair (2,3).

It turns out that answers to these counting problems can be unexpectedly elegant.

(Note: as the “Out[56]” which I clumsily left in the picture suggests, I generated this diagram and all my other Apollonian pictures using Mathematica 7; please contact me if you’re interested in methods for constructing pictures of this sort.)

0. Some basics

Four numbers (a,b,c,d) are the curvatures of four mutually tangent circles iff they satisfy the Descartes equation a^2+b^2+c^2+d^2=2(ab+ac+ad+bc+bd+cd).

Given a triple of mutually tangent circles with curvatures (a,b,c), the possible curvatures of a fourth circle are the roots of the above equation, viewed as a quadratic in d; in general there are two possibilities, a+b+c\pm\sqrt{ab+ac+bc}. In particular, their sum is 2(a+b+c). If we know one curvature d, then the “other” possibility is d'=2(a+b+c)-d.

A nice upshot of this is that, if we know the curvatures of four mutually tangent circles in a packing, we can compute all the rest using only addition and subtraction!

(more…)


%d bloggers like this: