On the connectedness of self-affine attractors

Let T = T(A, D) be a self-affine attractor in defined by an integral expanding matrix A and a digit set D. In the first part of this paper, in connection with canonical number systems, we study connectedness of T when D corresponds to the set of consecutive integers . It is shown that in and , for any integral expanding matrix A, T(A, D) is connected. In the second part, we study connectedness of Pisot dual tiles, which play an important role in the study of -expansions, substitutions and symbolic dynamical systems. It is shown that each tile of the dual tiling generated by a Pisot unit of degree 3 is arcwise connected. This is naturally expected since the digit set consists of consecutive integers as above. However surprisingly, we found families of disconnected Pisot dual tiles of degree 4. We even give a simple necessary and sufficient condition of connectedness of the Pisot dual tiles of degree 4. Detailed proofs will be given in [4]. Received: 2 March 2003     

Atomic surfaces, tilings and coincidence I. irreducible case

An irreducible Pisot substitution defines a graph-directed iterated function system. The invariant sets of this iterated function system are called the atomic surfaces. In this paper, a new tiling of atomic surfaces, which contains Thurston’sβ-tiling as a subclass, is constructed. Related tiling and dynamical properties are studied. Based on the coincidence condition defined by Dekking [Dek], we introduce thesuper-coincidence condition. It is shown that the super-coincidence condition governs the tiling and dynamical properties of atomic surfaces. We conjecture that every Pisot substitution satisfies the super-coincidence condition. The second author is supported by a JSPS Postdoc Fellowship.     

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     

Algorithm for determining pure pointedness of self-affine tilings

Overlap coincidence in a self-affine tiling in Rd is equivalent to pure point dynamical spectrum of the tiling dynamical system. We interpret the overlap coincidence in the setting of substitution Delone set in Rd and find an efficient algorithm to check the pure point dynamical spectrum. This algorithm is easy to implement into a computer program. We give the program and apply it to several examples. In the course of the proof of the algorithm, we show a variant of the conjecture of Urbański (Solomyak (2006) [40]) on the Hausdorff dimension of the boundaries of fractal tiles.     

Expanding Polynomials and Connectedness of Self-Affine Tiles

Little is known about the connectedness of self-affine tiles in ${\Bbb R}^n$. In this note we consider this property on the self-affine tiles that are generated by consecutive collinear digit sets. By using an algebraic criterion, we call it the {\it height reducing property}, on expanding polynomials (i.e., all the roots have moduli $ > 1$), we show that all such tiles in ${\Bbb R}^n, n \leq 3$, are connected. The problem is still unsolved for higher dimensions. For this we make another investigation on this algebraic criterion. We improve a result of Garsia concerning the heights of expanding polynomials. The new result has its own interest from an algebraic point of view and also gives further insight to the connectedness problem.     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

Spaces of domino tilings

We consider the set of all tilings by dominoes (2×1 rectangles) of a surface, possibly with boundary, consisting of unit squares. Convert this set into a graph by joining two tilings by an edge if they differ by aflip, i.e., a 90° rotation of a pair of side-by-side dominoes. We give a criterion to decide if two tilings are in the same connected component, a simple formula for distances, and a method to construct geodesics in this graph. For simply connected surfaces, the graph is connected. By naturally adjoining to this graph higher-dimensional cells, we obtain a CW-complex whose connected components are homotopically equivalent to points or circles. As a consequence, for any region different from a torus or Klein bottle, all geodesics with common endpoints are equivalent in the following sense. Build a graph whose vertices are these geodesics, adjacent if they differ only by the order of two flips on disjoint squares: this graph is connected. The first two authors received support from SCT and CNPq, Brazil. The other two were supported by a grant for undergraduates by CNPq.     

Fractal tiles associated with shift radix systems

Shift radix systems form a collection of dynamical systems depending on a parameter r which varies in the d-dimensional real vector space. They generalize well-known numeration systems such as beta-expansions, expansions with respect to rational bases, and canonical number systems. Beta-numeration and canonical number systems are known to be intimately related to fractal shapes, such as the classical Rauzy fractal and the twin dragon. These fractals turned out to be important for studying properties of expansions in several settings.In the present paper we associate a collection of fractal tiles with shift radix systems. We show that for certain classes of parameters r these tiles coincide with affine copies of the well-known tiles associated with beta-expansions and canonical number systems. On the other hand, these tiles provide natural families of tiles for beta-expansions with (non-unit) Pisot numbers as well as canonical number systems with (non-monic) expanding polynomials.We also prove basic properties for tiles associated with shift radix systems. Indeed, we prove that under some algebraic conditions on the parameter r of the shift radix system, these tiles provide multiple tilings and even tilings of the d-dimensional real vector space. These tilings turn out to have a more complicated structure than the tilings arising from the known number systems mentioned above. Such a tiling may consist of tiles having infinitely many different shapes. Moreover, the tiles need not be self-affine (or graph directed self-affine).     

Structure of planar integral self‐affine tilings

For a self‐affine tile in $\mathbf {R}^2$ generated by an expanding matrix $A\in M_2(\mathbf {Z})$ and an integral consecutive collinear digit set ${\mathcal D}$, Leung and Lau [Trans. Amer. Math. Soc. 359 , 3337–3355 (2007).] provided a necessary and sufficient algebraic condition for it to be disklike. They also characterized the neighborhood structure of all disklike tiles in terms of the algebraic data A and ${\mathcal D}$. In this paper, we completely characterize the neighborhood structure of those non‐disklike tiles. While disklike tiles can only have either six or eight edge or vertex neighbors, non‐disklike tiles have much richer neighborhood structure. In particular, other than a finite set, a Cantor set, or a set containing a nontrivial continuum, neighbors can intersect in a union of a Cantor set and a countable set.     

Substitution tilings and separated nets with similarities to the integer lattice

We show that any primitive substitution tiling of ℝ² creates a separated net which is biLipschitz to ℤ². Then we show that if H is a primitive Pisot substitution in ℝ ^d , for every separated net Y, that corresponds to some tiling τ ∈ X _H , there exists a bijection Φ between Y and the integer lattice such that sup _y∈Y ∥Φ(y) − y∥ < ∞. As a corollary, we get that we have such a Φ for any separated net that corresponds to a Penrose Tiling. The proofs rely on results of Laczkovich, and Burago and Kleiner.     

Remainders of arcwise connected compactifications of the plane

A. Lelek asked which continua are remainders of locally connected compactifications of the plane. In this paper we study a similar problem with local connectedness replaced by arcwise connectedness. (Each locally connected continuum is arcwise connected.) We give the following characterization: a continuum X is pointed 1-movable if and only if there is an arcwise connected compactification of the plane with X as the remainder.     

Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs

A graph G is 1‐Hamilton‐connected if G?x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X?E⁺(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012     

On characterizations of spectra and tilings

In a recent paper, Lagarias, Reeds and Wang established a characterization of spectra and tilings that can be used to prove a conjecture of Jorgensen and Pedersen by Keller's criterion. Different techniques to prove these facts have also been developed by Kolountzakis, Iosevich and Pedersen. The primary aim of this paper is to present an elementary method of describing certain characterizations of spectra and tilings. To illustrate this method, we first give a simple proof of this characterization. We then use the method to derive some characteristic results connected with the dual Fuglede's spectral-set conjecture. The results here extend several known conclusions in a simple manner.     

The classification of 2-isohedral tilings of the plane

Two different methods for enumerating k-isohedral tilings are discussed. One is geometric: by splitting and gluing tiles. The other is combinatorial: by enumerating the appropriate Delaney—Dress symbols. Both methods yield 1270 types of proper 2-isohedral tilings of the plane.     

Connectedness of a class of planar self-affine tiles

We consider a class of planar self-affine tiles T that are generated by the lower triangular expanding matrices and the product-form digit sets. We give necessary and sufficient conditions for T to be connected and disk-like. Also for the disconnect case, we give a condition that enumerates the number of connected components of T.     

Connected components of sets of finite perimeter and applications to image processing

This paper contains a systematic analysis of a natural measure theoretic notion of connectedness for sets of finite perimeter in ℝ ^N , introduced by H. Federer in the more general framework of the theory of currents. We provide a new and simpler proof of the existence and uniqueness of the decomposition into the so-called M-connected components. Moreover, we study carefully the structure of the essential boundary of these components and give in particular a reconstruction formula of a set of finite perimeter from the family of the boundaries of its components. In the two dimensional case we show that this notion of connectedness is comparable with the topological one, modulo the choice of a suitable representative in the equivalence class. Our strong motivation for this study is a mathematical justification of all those operations in image processing that involve connectedness and boundaries. As an application, we use this weak notion of connectedness to provide a rigorous mathematical basis to a large class of denoising filters acting on connected components of level sets. We introduce a natural domain for these filters, the space WBV(Ω) of functions of weakly bounded variation in Ω, and show that these filters are also well behaved in the classical Sobolev and BV spaces. Received July 27, 1999 / final version received June 8, 2000?Published online November 8, 2000     

Classification of disordered tilings

A tilingT is a disordered realization of a periodic tilingP with symmetry group Γ if we can map the complement of a compact set ofT onto the quotientP/Γ in such a way that this map respects the features of the tilingT andP. We show that the global type of a 2-dimensional tilingT is determined by the periodic tilingP it is a disordered realization of, a conjugacy class of Γ which can be associated toT and a winding number. In some cases, we need in addition some kind of orientation. For higher-dimensional tilings of spaces which are simply connected at infinity, e.g. ℝ ⁿ withn≥3, the associated periodic tiling alone is sufficient.     

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)     

Dual systems of algebraic iterated function systems

We study a class of graph-directed iterated function systems on R$\mathbb{R}$ with algebraic parameters, which we call algebraic GIFS. We construct a dual IFS of an algebraic GIFS, and study the relations between the two systems. We determine when a dual system satisfies the open set condition, which is fundamental. For feasible Pisot systems, we construct the left and right Rauzy–Thurston tilings, and study their multiplicities and decompositions. We also investigate their relation with codings space, domain-exchange transformation, and the Pisot spectrum conjecture. The dual IFS provides a unified and simple framework for Rauzy fractals, β-tilings and related studies, and allows us gain better understanding.