Affiliations: Dipartimento di Sistemi e Informatica, Universitá di Firenze, Viale Morgagni 65, 50134, Firenze, Italy | Dipartimento di Ingegneria Informatica e Scienze Matematiche, Universitá di Siena, Via Roma 56, 53100, Siena, Italy. rinaldi@unisi.it | Dipartimento di Ingegneria Informatica e Scienze Matematiche, Universitá di Siena, Via Roma 56, 53100, Siena, Italy
Note: [] Address for corespondence: Dipartimento di Ingegneria Informatica e Scienze Matematiche, Universitá di Siena, Via Roma 56, 53100, Siena, Italy
Abstract: In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π1, π2). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1(P) = π or π2(P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications $\cal{F}(\pi)$ on the points of π, and prove that there exists a column-convex permutomino P such that π1(P) = π if and only if $\cal{F}(\pi)$ is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1(P) = π.
