of the Jeu de Taquin Property

The Company Rules:

Suppose that a company has a fixed organizational chart, in which each position can have two or more supervisory positions directly above it. The employees of the company have distinct seniorities, and are assigned to positions in such a way that no employee ever has a supervisor with less seniority.

If an employee should resign or die, then the most senior person who was supervised by the departed employee will be promoted to the vacant position. This creates a new vacancy which is lower in the organizational chart. This promotion rule is to be repeatedly applied, until only a position which is minimal in the organizational chart is vacant.

If two or more vacancies arise simultaneously, then this procedure is first followed for the vacancy created by the absence of the least senior of the departed employees. Then the procedure is followed for the other vacancies, in the order of increasing seniority for the departed employees. Here the demotion of a particular vacancy stops when it reaches a minimal position in the chart or a position which supervises only currently vacant positions.

A Fundamental Question Concerning the Consequences of a Plane Crash:

Suppose that all of our company's positions are currently filled. A subset of our company's positions is said to be an "upper echelon" if there is no other position in the company outside of this subset which supervises one of the positions in this subset. Suppose that an airplane carrying all of the people who occupy some upper echelon of positions in the company crashes, and that there are no survivors. Following the company rules, all of the other employees will be promoted until the only vacant positions are at the bottom of the company's chart. We should expect the final pattern of assignments to positions to depend upon the pattern of seniorities in the upper echelon of people killed in the crash at the time of the crash, since this pattern of seniorities dictated the order in which those positions were filled. Here's the fundamental question:

Are there any organizational charts for which the final pattern of assignments will always be independent of the pattern of seniorities held by the people killed in the plane crash?

Such organizational charts could be said to be "fair":

Why should a survivor's new assignment depend upon the pecking order of employees who are no longer with the company?

Do any such charts exist? How can one find many of them?

Two Examples:

Here is an organizational chart with 5 positions for which the final pattern depends upon the pattern of seniorities of those killed: Suppose that A supervises B, C, and D, and that each of B, C, and D supervise E. Suppose that A, B, and C are killed in a plane crash. Then D will always end up in the top position which was originally held by A. However, the final new position held by E will depend upon the relative seniorities of the deceased B and C.

Now, on the other hand, we present an organizational chart with 6 positions for which the final pattern is always independent of the relative seniorities of the employees killed. Some readers may prefer to come back to this example after reading the concluding remarks below. Suppose that A supervises B and C, each of whom supervise D. In addition, C also supervises E. Finally, both D and E supervise F. There are ten possible sets of plane crash victims, but there is nothing to do when no one is killed or when everyone is killed. The scenarios where only A is killed or where only F survives can present no inconsistencies in the final assignments. Inconsistencies can also not arise for the victim sets {A,B}, {A,C}, or {A,C,E}, since there is only one possible seniority pattern for those killed in each of these situations. We are left with three potentially interesting plane crashes. For the victim set {A,B,C}, each of two possible survivor seniority patterns must be promoted for each of the two possible victim seniority patterns, and we need to check for consistency within each of these pairs of results. For the victim set {A,B,C,D}, only one survivor pattern must be promoted two different ways. For the victim set {A,B,C,E}, only one survivor pattern must be promoted three different ways. Once these three pairs and one triple of final assignment patterns are confirmed to be internally consistent, we can see that for this chart, the seniority pattern of the victims never influences the final assignment pattern of the surviving employees.

Concluding Remarks:

`
To refer to Schutzenberger's terminology, we will refer to an
organizational chart for which the final results are always
independent of the seniority pattern of the victims as a "jeu de
taquin poset". It should be expected that such organizational charts
should be very rare: to find a deficiency with respect to this
property, a skeptic is allowed to choose any upper echelon of the
chart for the plane crash and any seniority pattern for the
survivors. Then he or she only needs to find two out of all of the
possible seniority patterns for the victims which lead to different
final assignment patterns. This amounts to thousands of potential
failure scenarios for even relatively small organizational charts. In
fact, only 236 of the 14,512 connected posets with 8 elements have the
jeu de taquin property, which is around 1.6%. Of these 236
organizational charts, 181 of them are d-complete. Since Theorem 1
(stated on our home page) states that every d-complete poset has
the jeu de taquin property, it can be said that these 181 cases can be
predicted to provide fair charts via Lie
theoretic insights.
`

or return to Recent Research Table of Contents.