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)     

2-extendability of toroidal polyhexes and Klein-bottle polyhexes

A toroidal polyhex (resp. Klein-bottle polyhex) described by a string (p,q,t) arises from a p×q-parallelogram of a hexagonal lattice by a usual torus (resp. Klein bottle) boundary identification with a torsion t. A connected graph G admitting a perfect matching is k-extendable if |V(G)|≥2k+2 and any k independent edges can be extended to a perfect matching of G. In this paper, we characterize 2-extendable toroidal polyhexes and 2-extendable Klein-bottle polyhexes.     

Inversion relations, reciprocity and polyominoes

We derive self-reciprocity properties for a number of polyomino generating functions, including several families of column-convex polygons, three-choice polygons, and staircase polygons with a staircase hole. In so doing, we establish a connection between the reciprocity results known to combinatorialists and the inversion relations used by physicists to solve models in statistical mechanics. For several classes of convex polygons, the inversion (reciprocity) relation, augmented by certain symmetry and analyticity properties, completely determines the anisotropic perimeter generating function.     

Dimers, tilings and trees

Generalizing results of Temperley (London Mathematical Society Lecture Notes Series 13 (1974) 202), Brooks et al. (Duke Math. J. 7 (1940) 312) and others (Electron. J. Combin. 7 (2000); Israel J. Math. 105 (1998) 61) we describe a natural equivalence between three planar objects: weighted bipartite planar graphs; planar Markov chains; and tilings with convex polygons. This equivalence provides a measure-preserving bijection between dimer coverings of a weighted bipartite planar graph and spanning trees of the corresponding Markov chain. The tilings correspond to harmonic functions on the Markov chain and to “discrete analytic functions” on the bipartite graph.The equivalence is extended to infinite periodic graphs, and we classify the resulting “almost periodic” tilings and harmonic functions.     

Translational tilings by a polytope, with multiplicity

We study the problem of covering ? ^d by overlapping translates of a convex polytope, such that almost every point of ? ^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov [5] and Minkowski [15], and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile ? ^d . By contrast, for k ≥2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles ? ^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational polytope, is centrally symmetric, and has centrally symmetric facets, then P must k-tile ? ^d for some positive integer k.     

Q-grammars and wall polyominoes

We use a variant of theq-grammar method to write functional equations for the generating functions of a subclass of vertically convex polyominoes and directed walks, according to specified parameters, which include the area. The form of these equations, and some simple singularity computations, are used to prove that the area of wall polyominoes of perimeter 2n has the Airy distribution as a limit law.     

Two-dimensional groups, orbifolds and tilings

Given the triangulation of a 2-dimensional orbifold in terms of the Delaney-Dress symbol of a periodic tiling, we discuss how to compute its orbifold symbol, as defined by J. Conway. It is shown that the number of types of equivariant tilings depends only on the form of the corresponding orbifold symbols. The method is applied to obtain a refined classification of equivariant tilings for certain hyperbolic symmetry groups.Supported by the Deutsche Forschungsgemeinschaft.     

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.     

Orbits of edge-to-edge tilings by equilateral triangles,squares and regular hexagons

An edge-to-edge tiling of the Euclidian plane by equilateral triangles, squares and regular hexagons is said to be of type (t,s,h) if there are exactly t orbits of triangles, s orbits of squares and h orbits of hexagons under the symmetry group of the tiling. We prove that there exist tilings of type (t,s,h) for every t 92, s 2, h 43. We completely determine the values of t and h for which tilings of type (t,1,h) exist.     

Non-intersecting paths, random tilings and random matrices

 We investigate certain measures induced by families of non-intersecting paths in domino tilings of the Aztec diamond, rhombus tilings of an abc-hexagon, a dimer model on a cylindrical brick lattice and a growth model. The measures obtained, e.g. the Krawtchouk and Hahn ensembles, have the same structure as the eigenvalue measures in random matrix theory like GUE, which can in fact can be obtained from non-intersecting Brownian motions. The derivations of the measures are based on the Karlin-McGregor or Lindstr?m-Gessel-Viennot method. We use the measures to show some asymptotic results for the models. Received: 1 December 2000 / Revised version: 20 May 2001 / Published online: 17 May 2002     

Klarner systems and tiling boxes with polyominoes

Let T be a protoset of d-dimensional polyominoes. Which boxes (rectangular parallelepipeds) can be tiled by T? A nice result of Klarner and Göbel asserts that the answer to this question can always be given in a particularly simple form, namely, by giving a finite list of “prime” boxes. All other boxes that can be tiled can be deduced from these prime boxes. We give a new, simpler proof of this fundamental result. We also show that there is no upper bound to the number of prime boxes, even when restricting attention to singleton protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.     

Quasiperiodic tilings and quasicrystals

One gets quasiperiodic tilings by projecting a periodic lattice from a space of a larger number of dimensions. One can choose a fundamental domain of the lattice in various ways — this leads to different quasi-periodic tilings. Thus, one can generalize Penrose's nonperiodic tiling of the plane and the same for space filling.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 155, pp. 116–135, 1986.Finally, I would like to express my gratitude to M. M. Skriganov for discussions.     

Wavelets and self-affine tilings

Given a self-affine periodic tiling ofR ⁿ we construct an associatedr-regular multiresolution analysis and wavelet basis with the same lattice of translations and scaling matrix as the tiling.     

Quaquaversal tilings and rotations

We construct a hierarchical tiling of 3 dimensional Euclidean space based on a triangular prism, using repeated rotations, about orthogonal axes, by angles 2π/m and 2π/n. To analyze the structure of the tiling we are led to determine the group G(m,n) generated by such a pair of rotations, for m=n=3 and for m=3, n=4. Oblatum X-1995 & 14-V-1997     

Equitransitive edge-to-edge tilings by regular convex polygons

In their article Tilings by regular polygons, B. Grünbaum and G. C. Shephard [1] conjecture that there are 19 equitransitive edge-to-edge tilings by regular convex polygons. We prove that there are 22 equitransitive edge-to-edge tilings by regular convex polygons, and it turns out that 3 of them are 1-equitransitive, 13 are 2-equitransitive, 5 are 3-equitransitive and 1 is 4-equitransitive.     

Space tilings and substitutions

We generalize the study of symbolic dynamical systems of finite type and ² action, and the associated use of symbolic substitution dynamical systems, to dynamical systems with ² action. The new systems are associated with tilings of the plane. We generalize the classical technique of the matrix of a substitution to include the geometrical information needed to study tilings, and we utilize rotation invariance to eliminate discrete spectrum. As an example we prove that the pinwheel tilings have no discrete spectrum.Research supported in part by NSF Grant No. DMS-9304269 and Texas ARP Grant 003658-113     

Connectedness of number theoretical tilings (dual tilings generated by Pisot units of degree 3 and 4)

We study the connectedness of Pisot dual tilings. It is shown that each tile generated by a Pisot unit of degree 3 is arcwise connected. However surprisingly, we found families of disconnected Pisot dual tiles of degree 4 which have infinitely many connected components. Also we give a simple necessary and sufficient condition for the connectedness of the Pisot dual tiles of degree 4. As a byproduct, we give a complete classification of the β expansion of 1 for quartic Pisot units. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)