4
$\begingroup$

Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times. I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the total movement of all the "dancers" is minimal. For a pair to "meet" I simply mean that, at some point during the dance, they occupy adjacent positions.

Say that n=8 in this case. Here is a crude illustration of the dance:

    0 -\ /--- 1 -\ /--- 3 -\ /--- 5 
        X         X         X      
    1 -/ \ /- 3 -/ \ /- 5 -/ \ /- 7 
          X         X         X     
    2 -\ / \- 0 -\ / \- 1 -\ / \- 3 
        X         X         X       
    3 -/ \ /- 5 -/ \ /- 7 -/ \ /- 6 
          X         X         X     
    4 -\ / \- 2 -\ / \- 0 -\ / \- 1 
        X         X         X       
    5 -/ \ /- 7 -/ \ /- 6 -/ \ /- 4
          X         X         X     
    6 -\ / \- 4 -\ / \- 2 -\ / \- 0 
        X         X         X       
    7 -/ \--- 6 -/ \--- 4 -/ \--- 2

-----------------------------------------
   t=0       t=1       t=2       t=3

It looks something like a braid. We can define the cost of a dance to be the sum of the distances by which each element is displaced. For the dance above, the cost is 42 (3 permutations x cost of 14 each). The permutation (1,3,0,5,2,7,4,6) has a cost of 14 since it displaces all 8 elements up or down by 2, except for the second and second-last elements which move up and down by a distance of 1.

I should mention that the dance above is not unique, for example there are other dances on {0..7} which also have cost 42 but consist of different permutations, not repeated application of a single permutation as illustrated above. I am reasonably confident that the cost of 42 is minimal for the n=8 case but do not have a solid proof.

The question I have is this: what can be said about dances of minimal (or approximately minimal) cost in the following restricted case: suppose we introduce a radius r, and require not that every pair of dancers meet, but only those initially within distance r of each other. For example, a dance on {0..7} with n=8, r=2 and initial configuration (0,1,2,3,4,5,6,7) does not need {2} and {5} to meet, since these are initially separated by a distance 3, greater than r.

Edit: Can this notion of restriction be cast in the language of forbidden patterns, I wonder?

$\endgroup$
0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.