Permutation flip processes

EUROCOMB’23

Jan Hladký Hanka Řada

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-081

PDF
Abstract
We introduce a broad class of stochastic processes on permutations which we call flip processes. A single step in these processes is given by a local change on a randomly chosen fixed-sized tuple of the domain. We use the theory of permutons to describe the typical evolution of any such flip process $\pi_0,\pi_1,\pi_2,\ldots$ started from any initial permutation $\pi_0\in\mathrm{Sym}(n)$. More specifically, we construct trajectories $\Phi:\mathfrak{P}\times [0,\infty)\rightarrow\mathfrak{P}$ in the space of permutons with the property that if $\pi_0$ is close to a permuton $\gamma$ then for any $T>0$ with high probability $\pi_{Tn}$ is close to $\Phi^{T}(\gamma)$. This view allows to study various questions inspired by dynamical systems.

Pages:
587–594
References

P. Araújo, J. Hladký, E. K. Hng, and M. Šileikis. Prominent examples of flip processes. arXiv:2206.03884.

F. Garbe, J. Hladký, M. Šileikis, and F. Skerman. From flip processes to dynamical systems on graphons. arxiv.org:2201.12272.

F. Garbe, J. Hladký, G. Kun, and K. Pekárková. On pattern-avoiding permutons. arXiv.org:2208.12712.

C. Hoppen, Y. Kohayakawa, C. G. T. de A. Moreira, B. Ráth, and R. M. Sampaio. Limits of permutation sequences. J. Comb. Theory, Ser. B, 103(1):93-113, 2013.
https://doi.org/10.1016/j.jctb.2012.09.003

D. Král' and O. Pikhurko. Quasirandom permutations are characterized by 4-point densities. Geometric and Functional Analysis, 23, 2013.
https://doi.org/10.1007/s00039-013-0216-9

N. C. Wormald. Differential equations for random processes and random graphs. Ann. Appl. Probab., 5(4):1217-1235, 1995.
https://doi.org/10.1214/aoap/1177004612

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Jan Hladký, Hanka Řada

PDF