This project is concerned with the notion of square permutations, whose algorithmic aspects have recently been studied by one of the applicants [2, 3]. Our goal here is to study in more depth the following questions: what makes a permutation square?

• how many square roots can a permutation contain?
• what is the length of a maximum-size square root in a permutation?

These questions will be tackled both under combinatorial and algorithmic viewpoints.

Creative Commons BY 4.0

Mathilde Bouvel, Guillaume Fertin, and Stéphane Vialette