Minimum boundary touching tilings of polyominoes

We study the problem of tiling a polyomino P with as few squares as possible such that every square in the tiling has a non‐empty intersection with the boundary of P . Our main result is an algorithm which given a simply connected polyomino P computes such a tiling of P . We indicate how one can improve the running time of this algorithm for the more restricted row‐column‐convex polyominoes. Finally we show that a related decision problem is in NP for rectangular polyominoes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Irregular polyomino tiling via integer programming with application in phased array antenna design

A polyomino is a generalization of the domino and is created by connecting a fixed number of unit squares along edges. Tiling a region with a given set of polyominoes is a hard combinatorial optimization problem. This paper is motivated by a recent application of irregular polyomino tilings in the design of phased array antennas. Specifically, we formulate the irregular polyomino tiling problem as a nonlinear exact set covering model, where irregularity is incorporated into the objective function using the information-theoretic entropy concept. An exact solution method based on a branch-and-price framework along with novel branching and lower-bounding schemes is proposed. The developed method is shown to be effective for small- and medium-size instances of the problem. For large-size instances, efficient heuristics and approximation algorithms are provided. Encouraging computational results including phased array antenna simulations are reported.     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

Many L-Shaped Polyominoes Have Odd Rectangular Packings

A polyomino is called odd if it can tile a rectangle using an odd number of copies. We give a very general family of odd polyominoes. Specifically, consider an L-shaped polyomino, i.e., a rectangle that has a rectangular piece removed from one corner. For some of these polyominoes, two copies tile a rectangle, called a basic rectangle. We prove that such a polyomino is odd if its basic rectangle has relatively prime side lengths. This general family encompasses several previously known families of odd polyominoes, as well as many individual examples. We prove a stronger result for a narrower family of polyominoes. Let L _n denote the polyomino formed by removing a 1 ×  (n?2) corner from a 2 ×  (n?1) rectangle. We show that when n is odd, L _n tiles all rectangles both of whose sides are at least 8n ³, and whose area is a multiple of n. If we only allow L _n to be rotated, but not reflected, then the same is true, provided that both sides of the rectangle are at least 16n ⁴. We also give several isolated examples of odd polyominoes.     

Helly Numbers of Polyominoes

We define the Helly number of a polyomino P as the smallest number h such that the h-Helly property holds for the family of symmetric and translated copies of P on the integer grid. We prove the following: (i) the only polyominoes with Helly number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number k for any k ≠ 1, 3.     

Avoiding Monotone Chains in Fillings of Layer Polyominoes

In this paper we give simple bijective proofs that the number of fillings of layer polyominoes with no northeast chains is the same as the number with no southeast chains. We consider 01-fillings and \({{\mathbb{N}}}\)-fillings and prove the results for both strong chains where the smallest rectangle containing the chain is also in the polyomino, and for regular chains where only the corners of the smallest rectangle containing the chain are required to be in the polyomino.     

Packing polyominoes clumsily

For a set D of polyominoes, a packing of the plane with D is a maximal set of copies of polyominoes from D that are not overlapping. A packing with smallest density is called a clumsy packing. We give an example of a set D such that any clumsy packing is aperiodic. In addition, we compute the smallest possible density of a clumsy packing when D consists of a single polyomino of a given size and show that one can always construct a periodic packing arbitrarily close in density to the clumsy packing.     

Gröbner bases of balanced polyominoes

We introduce balanced polyominoes and show that their ideal of inner minors is a prime ideal and has a squarefree Gröbner basis with respect to any monomial order, and we show that any row or column convex and any tree‐like polyomino is simple and balanced.     

Major index for 01-fillings of moon polyominoes

We propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M,s;A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.     

A characterization of intersection graphs of the maximal rectangles of a polyomino

The interior of an orthogonal polygon drawn on a regular grid of the plane defines a set of cells (or squares) called a polyomino. We prove that the intersection graph of the maximal rectangles contained in a polyomino is slightly triangulated or has a star cutset.     

Extremal polyomino chains with respect to Zagreb indices

For a molecular graph, the first Zagreb index M₁ is equal to the sum of squares of the vertex degrees and second Zagreb index M₂ is equal to the sum of products of degree of pairs of adjacent vertices. In this paper, Zagreb indices of polyomino chains are computed. Also the extremal polyomino chains with respect to Zagreb indices are determined.     

Perfect Matchings of Polyomino Graphs

This paper gives necessary and sufficient conditions for a polyomino graph to have a perfect matching and to be elementary, respectively. As an application, we can decompose a non-elementary polyomino with perfect matchings into a number of elementary subpolyominoes so that the number of perfect matchings of the original non-elementary polyomino is equal to the product of those of the elementary subpolyominoes.     

Several constants arising in statistical mechanics

This is a brief survey of certain constants associated with random lattice models, including self-avoiding walks, polyominoes, the Lenz-Ising model, monomers and dimers, ice models, hard squares and hexagons, and percolation models.     

Restricted words by adjacencies

A recurrence, a determinant formula, and generating functions are presented for enumerating words with restricted letters by adjacencies. The main theorem leads to refinements (with up to two additional parameters) of known results on compositions, polyominoes, and permutations. Among the examples considered are (1) the introduction of the ascent variation on compositions, (2) the enumeration of directed vertically convex polyominoes by upper descents, area, perimeter, relative height, and column number, (3) a tri-variate extension of MacMahon's determinant formula for permutations with prescribed descent set, and (4) a combinatorial setting for an entire sequence of bibasic Bessel functions.     

A Geometric Bijection for xy-Convex Curves and Convex Polyominoes

A connected subset of ${\mathbb{R}}^2$ consisting of unit squares with integral vertices is called a convex polyomino or is simply said to be xy-convex if it intersects any horizontal or vertical line exactly in one closed interval. In this paper, a geometric representation for xy-convex sets is described, allowing us to obtain, by elementary combinatorial methods, known formulas for the number of convex polyominoes contained in a rectangle of given size.     

Hinged dissection of polyominoes and polyforms

A hinged dissection of a set of polygons S is a collection of polygonal pieces hinged together at vertices that can be rotated into any member of S. We present a hinged dissection of all edge-to-edge gluings of n congruent copies of a polygon P that join corresponding edges of P. This construction uses kn pieces, where k is the number of vertices of P. When P is a regular polygon, we show how to reduce the number of pieces to k/2(n−1). In particular, we consider polyominoes (made up of unit squares), polyiamonds (made up of equilateral triangles), and polyhexes (made up of regular hexagons). We also give a hinged dissection of all polyabolos (made up of right isosceles triangles), which do not fall under the general result mentioned above. Finally, we show that if P can be hinged into Q, then any edge-to-edge gluing of n congruent copies of P can be hinged into any edge-to-edge gluing of n congruent copies of Q.     

Isohedral Polyomino Tiling of the Plane

A polynomial time algorithm is given for deciding, for a given polyomino P , whether there exists an isohedral tiling of the Euclidean plane by isometric copies of P . The decidability question for general tilings by copies of a single polyomino, or even periodic tilings by copies of a single polyomino, remains open. Received June 23, 1997, and in revised form April 6, 1998.     

On translating one polyomino to tile the plane

Given a polyomino, we prove that we can decide whether translated copies of the polyomino can tile the plane. Copies that are rotated, for example, are not allowed in the tilings we consider. If such a tiling exists the polyomino is called anexact polyomino. Further, every such tiling of the plane by translated copies of the polyomino is half-periodic. Moreover, all the possible surroundings of an exact polyomino are described in a simple way.     

An alternative method for q-counting directed column-convex polyominoes

The area+perimeter generating function of directed column-convex polyominoes will be written as a quotient of two expressions, each of which involves powers of q of all kinds: positive, zero and negative. The method used in the proof applies to some other classes of column-convex polyominoes as well. At least occasionally, that method can do the case q=1 too.