On the composition of permutons

Source abstract

Permutons can be thought of as "continuum limits" of permutations of diverging size, which encode information about the number of occurrences of any given finite subpattern. We construct a natural composition operation on permutons, analogous to composition of permutations, and explore its properties via a correspondence between permutons, Markov kernels, and Markov operators. We show that no extension of permutation composition to permutons can be (jointly) continuous with respect to the usual "weak" topology on permutons, but we construct a "strong" topology with respect to which composition is jointly continuous. Moreover, we characterize strong convergence of sequences of permutations of diverging size: a sequence of permutations converges strongly if and only if it converges weakly and its limit is the transpose of the graph of a measure-preserving function. The key insight behind these results is to apply functional analysis to certain operators associated to permutons; with this shift in perspective, our results have elegant and relatively "soft" proofs. As an application, we describe the permuton limit of a product of finitely many independent uniformly sampled separable permutations and give a formula for the expectation of this limit. We also show that in this case, as the number of compositions goes to infinity, the aforementioned expectation tends to the uniform permuton.