Algorithmic Construction of Permutations of High Dispersion
Authors:Juan Carrillo, Carlos Cruz
Mentor:Edward Mosteig, Professor of Mathematics, Loyola Marymount University
Given a collection of objects, a permutation is a function that re-orders the objects into a potentially new arrangement. An example of a permutation of the first five positive integers is (3,5,1,2,4). Here the number of objects being permutated is called the block length of the permutation. We investigate the notion of dispersion, which measures the extent to which objects are ”scattered” or ”dispersed” under the action of a permutation. Dispersion is a numerical value between 0 and 1, where larger values indicate a low level of redundancy in linear patterns found present in a graph of the permutation. The purpose of our two-fold investigation is (i) to shed light on the behavior of dispersion as block length increases and (ii) to construct permutations with dispersion as large as possible. For small block lengths (of at most 12), we compute the average value of dispersion via computer for all permutations of a given block length. The calculation is intractable for large block lengths, and so we produce estimates using sampling techniques. Empirically, dispersion appears to follow a distribution with mean 0.81 and extraordinarily small standard deviation. This small standard deviation poses an obstacle to finding permutations with large dispersion via pseudo-random sampling, and so we developed and analyzed heuristic algorithms to over- come this challenge. Permutations play a role in applications such as coding theory, experimental design, and radar equipment, and so our research has the potential to impact our understanding of some fundamental questions in these areas.