Investigation of insertion tableau evolution in the Robinson-Schensted-Knuth correspondence

Full Text

Robinson-Schensted-Knuth (RSK) algorithm also known as Robinson- Schensted-Knuth correspondence which maps permutations to the pairs of Young tableaux, plays an important role into various combinatorial problems. The combinatorics of Young diagrams and Young tableaux including RSK algorithm, finds numerous applications in physics, mathematics and informatics [1]-[3]. RSK correspondence can be easily generalized from the case of permutations to the case of infinite sequences of linearly ordered set. In such instance, an insertion tableau is a semi-standard Young tableau filled by elements of this ordered set. This implies that the RSK algorithm is applicable to a sequence of random independent values uniformly distributed over the interval [0, 1], i.e. to the Bernoulli scheme. A correspondence between two dynamical systems such as Bernoulli shift and iterations of Schützenberger transformation was built in [4]. Later [5] it was proved that this correspondence is isomorphism. It was also proved there that the first element of an infinite sequence of uniformly distributed random values can be unambiguously restored only by the limit angle of inclination of Schützenberger path of a recording tableau. In practice, we are interested in the restoration of the first element of a finite sequence. Unlike the case of infinite sequences, we also need an insertion tableau in addition to a recording tableau to restore the first element. Since tableau changes during every iteration, the investigation of tableau evolution properties is also important for studying the algorithms of restoration of an entire sequence. The results of computer experiments related to the estimation of the first element value in a finite segment of an infinite sequence using tableau are given in [6]. The subject of this article is to examine how tableau changes during RSK insertions. 2. Definitions Young diagrams are popular combinatorial structures which correspond to integer partitions. There are many ways to present a Young diagram. Particularly, in this paper we define it by so-called French notation as leftjustified and bottom-justified finite set of square boxes (see Figure 1 (a)). y 12 v y x x 0 12 -2 1. French notation u 0 2 2. Russian notation Figure 1. An example of a Young diagram Another way of presenting Young diagrams called Russian notation is shown in Figure 1 (b). The Russian notation was proposed by Vershik and Kerov [7] and is derived from the French notation by rotating the axes 45 degrees counterclockwise. Note that the diagram in Figure 1 (b) is normalized in such a way that the total area of boxes is 1. This notation is used in many papers because it makes studying the Plancherel measure much easier. It is convenient to consider Young diagrams as vertices of infinite oriented graded graph called the Young graph. In this graph, edges connect diagrams which differ in one box. If the edge connects a diagram of the size with a diagram +1 of the size + 1, then +1 can be obtained from by adding a single box. If we assign to each edge a certain transition probability, a Markov process will be defined on the graph. The most important class of such processes is the class of central processes for which the probabilities of different paths between a fixed pair of diagrams are equal. A complete description of all central processes on the 2D Young graph was obtained by Vershik in [8]. The only central process on the Young graph with o() speed of growth along the axes is called the Plancherel process. This process and explicit formulas of its transition probabilities are described in [8]. The limit shape of the Plancherel process called the Vershik- Kerov-Logan-Schepp (VKLS) limit shape [7] is given by the formula: ⎧{ 2 ( arcsin() + √ 1 - 2), || ⩽ 1, (1) { = ⎨ ⎩||, || ⩾ 1, where is a coordinate in the Russian notation. A Young tableau is a Young diagram filled by values increasing in rows and columns. These values can be elements of an arbitrary linearly ordered set. Wherein we say that is a shape of . A standard Young tableau (SYT) is a Young diagram filled by integers [1, ], > 0 which grow strictly in rows and columns. It is easy to see that a Young tableau corresponds to a path on the Young graph. The numbers in tableau set the order of adding the boxes when walking from the root of the graph. A semistandard Young tableau (SSYT) is a Young tableau with values strictly increasing in columns and weakly increasing in rows. In addition to the finite Young tableaux consisting of boxes, infinite tableaux can be considered as well. By infinite Young tableau we mean + a mapping ∶ ℤ2 ⇒ ℕ such that for the fixed , ∈ ℕ the values , and ,, ∈ ℕ grow strictly. These infinite tableaux are also called enumerations ℤ of the integer lattice 2 . For the case of SYT or SSYT, some integers may be + ℤ missing, i.e. the corresponding mapping 2 + → ℕ is not necessary bijective. In this research we consider SYT filled by integers and SSYT filled by real numbers belonging to the interval [0, 1]. 3. Robinson-Schensted-Knuth algorithm RSK algorithm establishes a bijection between a set of permutations of distinct integers and a set of pairs of standard Young tableaux of size of the same shape. These tableaux are called insertion tableau and recording tableau . At the beginning, the first value of a permutation is put into the empty tableau and 1 is inserted in the tableau . In each step of the algorithm, the next value of permutation is being compared with values of the first column of . If exceeds all these values, it is being put on the top of the first column. Otherwise, it replaces the closest larger value of the first column. The replaced value is being bumped in the second column and being processed in the same way. This process continues until a certain value is put on the top of a column at position (, ). Finally, the index of a processed value is being put into tableau at (, ). So, and tableaux are supported to have the same shape. The algorithm finishes when all the values of a permutation are processed. Note that above steps can be performed in reverse order, i.e. a permutation can be constructed from a pair of Young tableaux of the same shape. Such a procedure is called reverse RSK algorithm. Also, RSK algorithm is applicable to any ordered sequences such as sequences of integer or real values. RSK algorithm defines two equivalence relations on a set of permutations. The permutations are called Knuth-equivalent if they correspond to the same tableau and dual Knuth-equivalent if they correspond to the same tableau . Another Donald Knuth’s definition of these equivalence classes directly in terms of permutations is given in [9]. Some interesting properties of Knuth-equivalent and dual Knuth-equivalent permutations were investigated in [6]. 4. Visualization of Plancherel tableaux In order to study the properties of the RSK algorithm, it is of interest to examine how the shape of tableau changes in time. The evolution of tableau has a simple description: it is proved by Donald Knuth that RSK transforms an uniformly distributed random sequence in a pair of Plancherel-distributed Young tableaux. Therefore, tableau grows as a tableau in a Markov process which generates the Plancherel measure. There exists an interesting way to visualize a Young tableau in the 3D space proposed by A. M. Vershik. Consider a function on the set of boxes of the corresponding Young diagram. The values of this function are the numbers within the corresponding boxes. A Young tableau can be represented as a 3D graph of this function. For the Plancherel tableaux, with a rise of their sizes this graph tends to a surface which can be described as follows. Consider a set of positively directed rays on the 2D plane emanating from the origin. Each ray intersects with the VKLS limit shape (1) at some point (′, ′). For a point ( ⋅ ′, ⋅ ′) which lies on this ray, = 2. So, this surface intersects with the planes containing axis along parabolas which touches the coordinate plane , in the origin. This property completely characterizes the surface. An example of such a visualization for the tableau of size 105 is shown in Figure 2 (a). Note that the coordinates (, ) are divided by √. A very similar picture can be produced by generating a Markov chain of Plancherel distributed Young diagrams. Figure 2 (b) demonstrates how the number of added box divided by 105 depends on normalized coordinates of this box in a Young tableau. 1 0.9 0.8 Number 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.5 00 0.25 1.25 0.75 1 x/Ö`n 1.5 1.75 2 0 0.5 0.25 1 0.75 1.5 1.25 y/Ö`n 2 1.75 1 0.9 Adding No./Ö`n 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.5 00 0.25 1.25 0.75 1 x/Ö`n 1.5 1.75 2 0 0.5 0.25 1 0.75 1.5 1.25 y/Ö`n 2 1.75 (a) (b) Figure 2. (a) Values of boxes in tableau after 105 RSK iterations; (b) Positions of added boxes in Plancherel process after adding 105 boxes 5. Bumping forest Each time a new value comes to the input of the RSK algorithm, it bumps a certain element in the first column of tableau and takes its position. Then, the bumped element bumps another element in the second column and so on. A bumping route is a sequence of all boxes bumped in a single RSK iteration. A bumping route is defined for each position in the first column. Bumping routes were presented in [10]. Also a problem of hydrodynamic description of bumping routes was raised there. The limit behaviour of bumping routes including explicit formula of their limit shape was described in [11]. The possible use of bumping routes to speed up the RSK algorithm was discussed in [12]. In the current research we have constructed all the bumping routes for tableau of size 108. Some of them are shown in Figure 3. 20000 18000 16000 14000 12000 10000 8000 6000 4000 2000 0 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 Figure 3. Some bumping routes of tableau A bumping tree is a set of bumping routes converging into a single box. A bumping forest is a union of all bumping routes. Figure 4 (a) demonstrates an example of a Young tableau and its bumping forest. The bumping forest itself is illustrated in Figure 4 (b). 100 98 97 94 93 90 89 74 96 72 86 59 82 58 67 79 52 65 78 39 43 66 76 95 32 40 60 70 85 29 37 50 69 80 27 35 36 55 61 17 19 26 47 49 56 63 73 13 16 21 23 38 45 53 62 81 92 8 9 10 15 31 34 42 54 57 68 77 91 3 5 7 11 20 25 30 33 46 48 51 83 88 1 2 4 6 12 14 18 22 24 28 41 44 64 71 75 84 87 99 (a) (b) Figure 4. (a) A Young tableau and its bumping forest; (b) A bumping forest 6. Dynamics of insertion tableau Along with studying the dynamics of the entire tableau, we are also interested in investigating the dynamics of concrete values in tableau . Here we discuss the results of our computer experiment dedicated to analysis of motion of these values within a semi-standard Young table filled by random real numbers from the interval [0, 1]. The idea of this algorithm is as follows. Firstly, we construct tableau of size . Next, the observed value is fed to the input of RSK. Then, we observe how the position of changes while RSK processes next - values. Each trajectory is close to a Vershik-Kerov-Logan-Schepp limit shape (1). The results of this experiment is illustrated in Figure 5. We examined trajectories of 9 different numbers: = [0.1, 0.2, … , 0.9]. The horizontal curves are trajectories of different . Black points are the final positions of for / = [0.1, 0.3, 0.5, 0.7, 0.9], = 107. It is easily seen from the Fig. 5 that the dynamics of motion of different values in RSK looks very similar. The average dynamics of a certain can be obtained by rescaling the unique average motion dynamics of = 1. Note that, with a rise of , the motion of these value continues until they eventually reach the coordinate plane. Unfortunately, this process often takes a really huge amount of RSK iterations what makes it hard to simulate it using available computation power. 0.9 0.8 0.7 0.6 0.5 z 0.4 0.3 0.2 z=0.9 z=0.8 z=0.7 z=0.6 z=0.5 z=0.4 z=0.3 z=0.2 z=0.1 2 1.8 1.6 1.4 0.1 0 0 0.2 0.4 0.6 0.8 1 x 1.2 1.4 1.6 0 1 0.8 0.6 0.4 0.2 1.2 y Figure 5. Evolution of random values in RSK algorithm 7. Conclusions The results of numerical experiments presented in this article demonstrate two types of dynamics in an insertion tableau of the Robinson- Schensted-Knuth algorithm. The first investigated dynamics is a modification of tableau after a single RSK iteration when a new value moves along a certain path called a bumping route. The second dynamics is related to the motion of the concrete value during many RSK iterations. Numerical experiments for studying these dynamics are presented in this paper.

About the authors

Vasilii S. Duzhin

Author for correspondence.
Email: vsduzhin@etu.ru

assistant of Department of Algorithmic Mathematics

References