Combinatorial Yang-Baxter

My paper with Tatiana Gateva-Ivanova is to be published. I’ll describe it here to demonstrate that one can find permutation groups almost anywhere.

The Yang–Baxter equation (YBE) is a kind of braiding equation for a linear map R on VV. We define two linear maps on VVV, namely R12, acting on the first two components of a 3-tensor and fixing the third, and R23, acting on the second and third component and fixing the first. The Yang–Baxter equation is R12R23R12 = R23R12R23. It has connections with mathematical physics which I don’t feel competent to describe here.

The combinatorial (or set-theoretic) YBE is defined for a map r on X×X, where X is a set; it asserts that r12r23r12 = r23r12r23, where r12 and r23 are similarly defined. Of course, a solution of this equation gives a solution of the “linear” equation over any field F, on setting V = FX.

We impose three further conditions on the function r, namely

  • r is an involution;
  • r fixes pointwise the diagonal of X×X;
  • r is non-degenerate (see below).

We can describe the function r in a different way: if r(x,y) = (u,v), we set u = fx(y) and v = gy(x); for each x, the function fx is a map from X to itself, and similarly for gy. Non-degeneracy is the requirement that each of the functions fx and gy is a bijection on x.

I will use the short term solution for a function r that satisfies the combinatorial Yang–Baxter equation and our extra three conditions.

Here are two examples.

  • The function r(x,y) = (y,x) satisfies the Yang–Baxter equation (essentially by the usual proof that the transpositions (1,2) and (2,3) in the symmetric group S3 satisfy the braid relation), and also our three additional conditions. In this case, the functions fx and gy are the identity, for all choices of x and y. This is referred to as the trivial solution.
  • The function which swaps (1,2) with (3,1), (1,3) with (2,1), and (2,3) with (3,2) (and fixes all diagonal pairs) is a solution on X = {1,2,3}.

If r is non-degenerate then the functions f and g can be regarded as maps from X into the symmetric group on X. It can be shown that a pair of maps f,g: X → Sym(X) arise in this way from a solution if and only if they satisfy the following conditions:

  • fx(x) = x;
  • ffx(y)gy(x) = x;
  • ffx(y)fgy(x) = fxfy.

(Unlike my usual convention, maps act on the left and compose right-to-left.)

Note that the second equation shows that g is determined by f. So everything can be expressed in terms of f. In our second example above, f1 and g1 are equal to the transposition (2,3), while the other functions are the identity.

One of the most important unsolved problems about this set-up is the following.

Problem. If f and g satisfy the above conditions and |X| > 1, is it true that there exist two points x and y with fx = fy?

I will say something about the significance of this problem later.

The commonest way to turn this situation into algebra is to define the Yang–Baxter group corresponding to r to be the group

G(r) = ⟨X | xy=uv whenever r(x,y)=(u,v)⟩

For the trivial solution, this is a free abelian group of rank |X|.

One can also consider the semigroup, or the F-algebra (for a field F) generated by X with the same relations.

However, to me a more natural construction is to let G* be the group of permutations of X generated by the functions fx. This is the Yang–Baxter permutation group of the solution r. It turns out that the map x → fx extends to a homomorphism from G to G*.

There are some slightly surprising things that can be said. For example,

  • The YB permutation group cannot be transitive if |X|>1.
  • The YB group (and hence the YB permutation group) of every finite solution is a solvable group.

In fact, one of the things we prove is that the derived length of G is
always one greater than that of the finite group G*.

Define an equivalence relation on X by x ≡ y if fx = fy. An affirmative answer to the problem stated earlier would say that this equivalence relation is not the relation of equality whenever |X|>1. It is easy to see that the given solution induces a solution (called a retract) on the set of equivalence classes. We can repeatedly take retracts; if the corresponding congruences are always non-trivial, eventually we get a solution on a 1-element set. Such a solution is called a multipermutation solution; its level is the number of retractions required to reach the 1-element set.

For a multipermutation solution, the YB group is solvable with derived length bounded by the multipermutation length; so the derived length of the YB permutation group is bounded by one less than the multipermutation length.

Our constructions of solutions with finite multipermutation level indicate that the cardinality of X grows exponentially with the multipermutation level; our smallest example of level m has cardinality 2m-1+1.

We also have a structure theorem for finite solutions with abelian YB permutation group; they are necessarily multipermutation, with level at most the number of orbits of G*, and they can be constructed from the solutions corresponding to the orbits by a construction known as strong twisted union. Every finite abelian group is isomorphic to the YB permutation group of such a solution.

There is surely much more to say about this situation!


About Peter Cameron

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

One Response to Combinatorial Yang-Baxter

  1. I believe the answer to the problem is “no”. Here there is an example:
    Let X={1,2,…,8} and
    f_1 = g_1 = (5,7),
    f_2 = g_2 = (6,8),
    f_3 = g_3 = (2,6)(4,8)(5,7),
    f_4 = g_4 = (1,5)(3,7)(6,8),
    f_5 = g_5 = (1,3),
    f_6 = g_6 = (2,4),
    f_7 = g_7 = (1,3)(2,6)(4,8),
    f_8 = g_8 = (1,5)(2,4)(3,7).
    Then all the conditions you mentioned are satisfied. However, f_x=f_y if and only if x=y.

Leave a Reply

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

You are commenting using your 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