Ordering and Convex Polyominoes

Abstract

We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q ≼ P are polyominoes. In the second part of the paper we investigate whether the partial orderings introduced are well-orderings. Since our order extends the subword ordering, which is a well-ordering (Higman’s theorem), the problem is whether there exists some extension of Higman’s theorem to two dimensions. A negative answer is given in the general case, and also if we restrict ourselves to polyominoes and even to convex polyominoes. However we prove that the restriction to the family of L-convex polyominoes is a well-ordering. This is a further result that shows the interest of the notion of L-convex polyomino