Narrow Results

We study the properties of the rook complex ${ℛ}$ of a polyomino ${𝒫}$ seen as independence complex of a graph $G$, and the associated Stanley–Reisner ideal $I_{{ℛ}}$. In particular, we characterize the polyominoes ${𝒫}$ having a pure rook complex, and the ones whose Stanley–Reisner ideal has linear resolution. Furthermore, we prove that for a class of polyominoes the Castelnuovo–Mumford regularity of $I_{{ℛ}}$ coincides with the induced matching number of $G$.

We consider paths in the square lattice and use a valuation called the winding number in order to exhibit some combinatorial properties on these paths. As a corollary, we obtain a characteristic property of non-crossing closed paths, generalizing in this way a result of Daurat and Nivat (2003) on the boundary properties of polyominoes concerning salient and reentrant points. Moreover we obtain a similar result for hexagonal lattices and show that there is no other regular lattice having that property.

We study the problem of folding a polyomino $P$ into a polycube $Q$, allowing faces of $Q$ to be covered multiple times. First, we define a variety of folding models according to whether the folds (a) must be along grid lines of $P$ or can divide squares in half (diagonally and/or orthogonally), (b) must be mountain or can be both mountain and valley, (c) can remain flat (forming an angle of $180^{\circ }$), and (d) must lie on just the polycube surface or can have interior faces as well. Second, we give all the inclusion relations among all models that fold on the grid lines of $P$. Third, we characterize all polyominoes that can fold into a unit cube, in some models. Fourth, we give a linear-time dynamic programming algorithm to fold a tree-shaped polyomino into a constant-size polycube, in some models. Finally, we consider the triangular version of the problem, characterizing which polyiamonds fold into a regular tetrahedron.

There exists a linear algorithm to decide whether a polyomino tessellates the plane by translation only. On the other hand, the problem of deciding whether a set of $11$ or more polyominoes can tile the plane by translation is undecidable. We narrow the gap between decidable and undecidable by showing that it remains undecidable for a set of $10$ polyominoes, which partially solves a conjecture posed by Ollinger.

In this paper, we introduce a new class of polyominoes, called closed paths, and we study the primality of their associated ideal. Inspired by an existing conjecture that characterizes the primality of a polyomino ideal by nonexistence of zig-zag walks, we classify all closed paths which do not contain zig-zag walks, and we give opportune toric representations of the associated ideals. To support the conjecture, we prove that having no zig-zag walks is a necessary and sufficient condition for the primality of the associated ideal of a closed path. Finally, we present some classes of prime polyominoes viewed as generalizations of closed paths.

Self-assembly is ubiquitous in physics, chemistry and biology, and has many applications in materials science and engineering. Here we present a general approach for finding the simplest set of building blocks that will assemble into a given physical structure. Our procedure can be adapted to any given geometry, and thus to any given type of physical system. The amount of information required to describe this simplest set of building blocks provides a quantitative measure of the structure's physical complexity, which is capable of detecting any symmetry or modularity in the underlying structure.We also introduce the notions of joint, mutual and conditional complexity for self-assembling structures. We illustrate our approach using self-assembling polyominoes, and demonstrate the breadth of its potential applications by using it to quantify the physical complexity of protein complexes.