Tiling the plane with permutations

A permutomino is a polyomino uniquely determined by a pair of permutations. Recently permutominoes, and in particular convex permutominoes have been studied by several authors concerning their analytical and bijective enumeration, tomographical reconstruction, and the algebraic characterization of the associated permutations. On the other side, Beauquier and Nivat introduced and gave a characterization of the class of pseudo-square polyominoes, i.e. polyominoes that tile the plane by translation. In this paper we consider the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects. Some conjectures obtained through exhaustive search are also presented and discussed in the final section.