An aperiodic hexagonal tile

We show that a single prototile can fill space uniformly but not admit a periodic tiling. A two-dimensional, hexagonal prototile with markings that enforce local matching rules is proven to be aperiodic by two independent methods. The space-filling tiling that can be built from copies of the prototile has the structure of a union of honeycombs with lattice constants of n²a, where a sets the scale of the most dense lattice and n takes all positive integer values. There are two local isomorphism classes consistent with the matching rules and there is a nontrivial relation between these tilings and a previous construction by Penrose. Alternative forms of the prototile enforce the local matching rules by shape alone, one using a prototile that is not a connected region and the other using a three-dimensional prototile.     

Approximation algorithms for MAX–MIN tiling

The MAX–MIN tiling problem is as follows. We are given A[1,…,n][1,…,n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[ℓ,…,r][t,…,b] of A, the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A[i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX–MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at least W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX–MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.     

Equivalence of Self-similar and Pseudo-self-similar Tiling Spaces in ℝ<Superscript>2</Superscript>

Given a tiling T, one may form a related tiling, called the derived Voronoi tiling of T, based on a patch of tiles in T. Similarly, for a tiling space X, one can identify a patch which appears regularly in all tilings in X, and form a derived Voronoi space of tilings, based on that patch.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Domino tilings of Aztec diamonds and squares

An Aztec diamond of rank n is a rhombus of side length n on the square grid. We give several new combinatorial proofs of known theorems about the numbers of domino tilings of diamonds and squares. We also prove generalizations of these theorems for the generating polynomials of some statistics of tilings. Some results here are new. For example, we describe how to calculate the rank of a tiling using special weights of edges on the square grid. Bibliography: 17 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 180–230.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Four-vertex model

An exactly solvable four-vertex model on a square grid with different boundary conditions is considered. The application of the Algebraic Bethe Ansatz method allows us to calculate the partition function of the model. For fixed boundary conditions, we establish a relation between the scalar product of state vectors with the generating function of column-and row-strict boxed plane partitions. A tiling model on a periodic grid is discussed. Bibliography: 33 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 347, 2007, pp. 34–55.     

First Hitting Times for Some Random Walks on Finite Groups

We consider a random walk on a finite group G based on a generating set that is a union of conjugacy classes. Let the nonnegative integer valued random variable T denote the first time the walk arrives at the identity element of G, if the starting point of the walk is uniformly distributed on G. Under suitable hypotheses, we show that the distribution function F of T is almost exponential, and we give an error term.     

Tiling bijections between paths and Brauer diagrams

There is a natural bijection between Dyck paths and basis diagrams of the Temperley–Lieb algebra defined via tiling. Overhang paths are certain generalisations of Dyck paths allowing more general steps but restricted to a rectangle in the two-dimensional integer lattice. We show that there is a natural bijection, extending the above tiling construction, between overhang paths and basis diagrams of the Brauer algebra.     

Tube Formulas and Complex Dimensions of Self-Similar Tilings

We use the self-similar tilings constructed in (Pearse in Indiana Univ. Math J. 56(6):3151–3169, 2007) to define a generating function for the geometry of a self-similar set in Euclidean space. This tubularzeta function encodes scaling and curvature properties related to the complement of the fractal set, and the associated system of mappings. This allows one to obtain the complex dimensions of the self-similar tiling as the poles of the tubularzeta function and hence develop a tube formula for self-similar tilings in ℝ^d. The resulting power series in εis a fractal extension of Steiner’s classical tube formula for convex bodies K⊆ℝ ^d . Our sum has coefficients related to the curvatures of the tiling, and contains terms for each integer i=0,1,…,d−1, just as Steiner’s does. However, our formula also contains a term for each complex dimension. This provides further justification for the term “complex dimension”. It also extends several aspects of the theory of fractal strings to higher dimensions and sheds new light on the tube formula for fractals strings obtained in (Lapidus and van Frankenhuijsen in Fractal Geometry, Complex Dimensions and Zeta Functions: Geometry and Spectra of Fractal Strings, 2006).     

On the K-theory of the stable C-algebras from substitution tilings

We describe a method to compute the K-theory of the C^?-algebra arising from the stable equivalence relation in the Smale space associated to a substitution tiling, and give detailed computations for one- and two-dimensional examples. We prove that for one-dimensional tilings the group K₀ is always torsion free and give an example of a two-dimensional tiling such that K₀ has torsion.     

Generating Functions for Permutations Avoiding a Consecutive Pattern

Given a permutation τ of length j, we say that a permutation σ has a τ-match starting at position i, if the elements in positions i, i+1, . . . , i+j−1 in σ have the same relative order as the elements of τ. We have been able to take advantage of the results of Mendes and Remmel [1] to obtain a generating function for the number of permutations with no τ-matches for several new classes of permutations. These new classes include a large class of permutations which are shuffles of an increasing sequence 1 2 · · · n with an arbitrary permutation σ of the integers {n + 1, . . . , n + m}. Finally we give a formula for the generating function for the number of permutations which have no 1 3 2 4-matches.     

Alternating-Sign Matrices and Domino Tilings (Part II)

We continue the study of the family of planar regions dubbed Aztec diamonds in our earlier article and study the ways in which these regions can be tiled by dominoes. Two more proofs of the main formula are given. The first uses the representation theory of GL(n). The second is more combinatorial and produces a generating function that gives not only the number of domino tilings of the Aztec diamond of order n but also information about the orientation of the dominoes (vertical versus horizontal) and the accessibility of one tiling from another by means of local modifications. Lastly, we explore a connection between the combinatorial objects studied in this paper and the square-ice model studied by Lieb.     

Rectangular Tiling in Multidimensional Arrays

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of nonnegative numbers and an integer p, partition the array into at most p rectangular subarrays so that the maximum weight of any subarray is minimized; the weight of a subarray is the sum of its elements. The rectangular tiling problem is motivated by applications in data mining, data partitioning, and video compression. Recently, Khanna, Muthukrishnan, and Paterson [SODA '98], showed that the tiling problem is NP-complete and gave a 2.5-approximation algorithm for d = 2.In this paper, we extend their result to multidimensional arrays and give an algorithm with approximation ratio , for d ≥ 2. The algorithm can be implemented to run in worst-case time O(N + p log N) time, where N is the size of the array, and the constant is of the order d!. We also obtain a similar algorithm for the dual tiling problem, where the goal is to compute a tiling of weight at most W using as few tiles as possible. Our algorithm yields an approximation factor (2d + 1).We implemented our algorithm and ran simulation tests on multidimensional arrays with random data. In our limited experiments, the algorithm always produced approximations that were no worse than factor two from the optimal.     

Rigidity of planar tilings

Summary Aperturbation of a tiling of a region inR ⁿ is a set of isometries, one applied to each tile, so that the images of the tiles tile the same region.We show that a locally finite tiling of an open region inR ² with tiles which are closures of their interiors isrigid in the following sense: any sufficiently small perturbation of the tiling must have only earthquake-type discontinuities, that is, the discontinuity set consists of straight lines and arcs of circles, and the perturbation near such a curve shifts points along the direction of that curve.We give an example to show that this type of rigidity does not hold inR ⁿ , forn>2.Using rigidity in the plane we show that any tiling problem with a finite number of tile shapes (which are topological disks) is equivalent to a polygonal tiling problem, i.e. there is a set of polygonal shapes with equivalent tiling combinatorics.Oblatum 19-III-1991     

Minimally Supported Frequency Composite Dilation Parseval Frame Wavelets

A composite dilation Parseval frame wavelet is a collection of functions generating a Parseval frame for L ²(ℝ ⁿ ) under the actions of translations from a full rank lattice and dilations by products of elements of groups A and B. A minimally supported frequency composite dilation Parseval frame wavelet has generating functions whose Fourier transforms are characteristic functions of sets contained in a lattice tiling set. Constructive proofs are used to establish the existence of minimally supported frequency composite dilation Parseval frame wavelets in arbitrary dimension using any finite group B, any full rank lattice, and an expanding matrix generating the group A and normalizing the group B. Moreover, every such system is derived from a Parseval frame multiresolution analysis. Multiple examples are provided including examples that capture directional information.      

On the Characterization of Expansion Maps for Self-Affine Tilings

We consider self-affine tilings in ℝ ⁿ with expansion matrix φ and address the question which matrices φ can arise this way. In one dimension, λ is an expansion factor of a self-affine tiling if and only if |λ| is a Perron number, by a result of Lind. In two dimensions, when φ is a similarity, we can speak of a complex expansion factor, and there is an analogous necessary condition, due to Thurston: if a complex λ is an expansion factor of a self-similar tiling, then it is a complex Perron number. We establish a necessary condition for φ to be an expansion matrix for any n, assuming only that φ is diagonalizable over ℂ. We conjecture that this condition on φ is also sufficient for the existence of a self-affine tiling.     

A Characterization of the Tutte Polynomial via Combinatorial Embeddings

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte’s notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities. This generating function is, in fact, independent of the embedding. Received March 15, 2006