Originators: I. Pak and A. Redlich (presented by D. McDonald - REGS 2009)
Definitions: For each positive integer k, let k={1,…k}. Choose integers n and m with 1≤m≤n. A block partition (A1,…,Am) is a partition of [n] into nonempty segments A1,…Am of consecutive integers. Such a partition A is determined by choosing the lengths of the blocks; by a standard computation, the number of block partitions of [n] into m blocks is the binomial coefficient C(n-1,m-1).
Given a block partition A into m blocks and a permutation τ of [m], the block permutation σ(τ,A) on [n] is the permutation that reorders the blocks A1,…,Am according to the permutation τ on the indices. For example, let n=8 and m=3, with block lengths 3,1,4 in order to specify A. If τ=321 in one-line form, then the block permutation σ(321,314) is (56784123), in one-line form.
A permutation of [n] is a cycle if each element first returns to its original position after n iterations (that is, the functional digraph is a single cycle). Given a permutation τ on [m] and an integer n at least m, let p(τ,n) be the probability (over all equally likely choices of the m lengths specifying a block permutation) that σ(τ,A) is a cycle.
Conjecture 1: [PR] For any τ, the limit limn→∞p(τ,n) exists.
Comment: Pak and Redlich [PR] showed that p(τ,n)→6⁄π².
Problem 2: In terms of τ, find necessary and/or sufficient conditions on A so that σ(τ,A) is a cycle.
Comment: Pak and Redlich [PR] showed for τ=321 that σ(τ,A) is a cycle if and only if |A1|+|A2| and |A2|+|A3| are coprime. From this they obtained an exact formula for σ(τ,A). It would be natural to consider Problem 2 when τ=4321.
Motivation: An interval exchange transformation is a dynamical system that generalizes the idea of circle rotation. For λ=(λ1,…,λm) with each λi>0 and ∑λi=1, let ai=∑j≤i&lambdaj. For a permutation τ of [m], define the interval exchange transformation Tτ,λ:[0,1)→[0,1) to be the mapping that sends the segment [ai-1,ai) to the segment [aτ(i)-1,aτ(i)) without changing the internal ordering of [ai-1,ai). Block permutations are the discrete analogues of interval exchange transformations.
References:
[PR] Pak, Igor; Redlich, Amanda Long cycles in abc-permutations. Funct. Anal. Other Math., vol. 2 (2008), no. 1, 87--92.