Ammann bars and quasicrystals

In 1988 Danzer [3] constructed a family of four tetrahedra which allows—with certain matching conditions—only aperiodic tilings. By analogy with the Ammann bars of planar Penrose tilings we define Ammann bars in space in the form of planar Penrose tilings we define Ammann bars in space in the form of plane sections of the four tetrahedra. If we require that the plane sections continue as planes across the faces of the tilings, we obtain an alternative matching condition, thus answering a question of Danzer.     

Chaotic attractors near forbidden symmetry

We explore chaotic attractors with symmetries that are close to forbidden symmetries. In particular, attractors with planar crystallographic symmetry that contain an imperfect, but apparent, rotation that does not preserve the lattice of translations are constructed. This gives us a visual representation of patterns which have low symmetry type, but which contain additional, provocative structure. Like Penrose tilings and diffraction patterns of quasicrystals, our constructions include local rotations that are forbidden from being global by classical crystallographic theory.     

Inapplicability of Asymptotic Results on the Minimal Spanning Tree in Statistical Testing

Penrose has given asymptotic results for the distribution of the longest edge of the minimal spanning tree and nearest neighbour graph for sets of multivariate uniformly or normally distributed points. We investigate the applicability of these results to samples of up to 100 points, in up to 10 dimensions. We conclude that the asymptotic results provide an acceptable approximation only in the uniform case. Their inaccuracy for the multivariate normal case means that they cannot be applied to improve Rohlf's gap test for an outlier in a set of multivariate data points, which depends on the longest edge of the minimal spanning tree of the set.     

Bond percolation on isoradial graphs: criticality and universality

In an investigation of percolation on isoradial graphs, we prove the criticality of canonical bond percolation on isoradial embeddings of planar graphs, thus extending celebrated earlier results for homogeneous and inhomogeneous square, triangular, and other lattices. This is achieved via the star–triangle transformation, by transporting the box-crossing property across the family of isoradial graphs. As a consequence, we obtain the universality of these models at the critical point, in the sense that the one-arm and $2j$ -alternating-arm critical exponents (and therefore also the connectivity and volume exponents) are constant across the family of such percolation processes. The isoradial graphs in question are those that satisfy certain weak conditions on their embedding and on their track system. This class of graphs includes, for example, isoradial embeddings of periodic graphs, and graphs derived from rhombic Penrose tilings.     

Quasicrystals—The impact of N.G. de Bruijn

In this paper we put the work of Professor N.G. de Bruijn on quasicrystals in historical context. After briefly discussing what went before, we shall review de Bruijn’s work together with recent related theoretical and experimental developments. We conclude with a discussion of Yang–Baxter integrable models on Penrose tilings, for which essential use of de Bruijn’s work has been made.     

THE SCENERY FLOW FOR GEOMETRIC STRUCTURES ON THE TORUS： THE LINEAR SETTING

50. IntroductionWe begin by recalling some wellknown relationshiPs. First, ther is the one-to-one corre-spondence between closed orbits of the g6odesic fiow on the modular surfaCe and conjugacyclasses of hyperbolic toral automorphisms. (This can be seen directly from the definitions(see Remaxk 1.3 in 51 below).) Secondly one knows that it is possible to code this geodesicflow using coatinued fractions and via circle rotations (cf [9, 42, 2, 7J). Thirdly, there is astrong relation between hyp…     

Local rules for pentagonal quasi-crystals

The existence of different kinds of local rules is established for many sets of pentagonal quasi-crystal tilings. For eacht∈ℝ there is a set of pentagonal tilings of the same local isomorphism class; the caset=0 corresponds to the Penrose tilings. It is proved that the set admits a local rule which does not involve any colorings (or markings, decorations) if and only ift=m+nτ. In other words, this set of tilings is totally characterized by patches of some finite radius, orr-maps. When the set admits a local rule which involvescolorings. For the set of Penrose tilings the construction here leads exactly to the Penrose matching rules. Local rules for the caset=1/2 are presented.     

Crystallography and Riemann surfaces

The level set of an elliptic function is a doubly periodic point set in ℂ. To obtain a wider spectrum of point sets, we consider, more generally, a Riemann surface S immersed in ℂ² and its sections (“cuts”) by ℂ More specifically, we consider surfaces S defined in terms of a fundamental surface element obtained as a conformai map of triangular domains in ℂ. The discrete group of isometries of ℂ² generated by reflections in the triangle edges leaves S invariant and generalizes double-periodicity. Our main result concerns the special case of maps of right triangles, with the right angle being a regular point of the map. For this class of maps we show that only seven Riemann surfaces, when cut, form point sets that are discrete in ℂ. Their isometry groups all have a rank 4 lattice subgroup, but only three of the corresponding point sets are doubly periodic in ℂ. The remaining surfaces form quasiperiodic point sets closely related to the vertex sets of quasiperiodic tilings. In fact, vertex sets of familiar tilings are recovered in all cases by applying the construction to a piecewise flat approximation of the corresponding Riemann surface. The geometry of point sets formed by cuts of Riemann surfaces is no less “rigid” than the geometry determined by a tiling, and has the distinct advantage in having a regular behavior with respect to the complex parameter which specifies the cut.     

THE SCENERY FLOWFOR GEOMETRIC STRUCTURES ON THE TORUS: THE LINEAR SETTING

The authors define the scenery flow of the torus. The flow space is the union of all flat 2-dimensional tori of area $1$ with a marked direction (or equivalently, the union of all tori with a quadratic differential of norm 1). This is a $5$-dimensional space, and the flow acts by following individual points under an extremal deformation of the quadratic differential. The authors define associated horocycle and translation flows; the latter preserve each torus and are the horizontal and vertical flows of the corresponding quadratic differential. The scenery flow projects to the geodesic flow on the modular surface, and admits, for each orientation preserving hyperbolic toral automorphism, an invariant $3$-dimensional subset on which it is the suspension flow of that map. The authors first give a simple algebraic definition in terms of the group of affine maps of the plane, and prove that the flow is Anosov. They give an explicit formula for the first-return map of the flow on convenient cross-sections. Then, in the main part of the paper, the authors give several different models for the flow and its cross-sections, in terms of: \item{$\bullet$} stacking and rescaling periodic tilings of the plane; \item{$\bullet$} symbolic dynamics: the natural extension of the recoding of Sturmian sequences, or the $S$-adic system generated by two substitutions; \item{$\bullet$} zooming and subdividing quasi-periodic tilings of the real line, or aperiodic quasicrystals of minimal complexity; \item{$\bullet$} the natural extension of two-dimensional continued fractions; \item{$\bullet$} induction on exchanges of three intervals; \item{$\bullet$} rescaling on pairs of transverse measure foliations on the torus, or the Teichm\"uller flow on the twice-punctured torus.     

Fusion: a general framework for hierarchical tilings of \mathbb{R }^d

We introduce a formalism for handling general spaces of hierarchical tilings, a category that includes substitution tilings, Bratteli–Vershik systems, S-adic transformations, and multi-dimensional cut-and-stack transformations. We explore ergodic, spectral and topological properties of these spaces. We show that familiar properties of substitution tilings carry over under appropriate assumptions, and give counter-examples where these assumptions are not met. For instance, we exhibit a minimal tiling space that is not uniquely ergodic, with one ergodic measure having pure point spectrum and another ergodic measure having mixed spectrum. We also exhibit a 2-dimensional tiling space that has pure point measure-theoretic spectrum but is topologically weakly mixing.     

On the Order Dimension of Convex Geometries

We study the order dimension of the lattice of closed sets for a convex geometry. We show that the lattice of closed subsets of the planar point set of Erd?s and Szekeres from 1961, which is a set of 2 ^n???2 points and contains no vertex set of a convex n-gon, has order dimension n???1 and any larger set of points has order dimension at least n.     

Quasicrystals and the Wulff-Shape

Infinite sphere packings give information about the structure but not about the shape of large dense sphere packings. For periodic sphere packings a new method was introduced in [W2], [W3], [Sc], and [BB], which gave a direct relation between dense periodic sphere packings and the Wulff-shape, which describes the shape of ideal crystals. In this paper we show for the classical Penrose tiling that dense finite quasiperiodic circle packings also lead to a Wulff-shape. This indicates that the shape of quasicrystals might be explained in terms of a finite packing density. Here we prove an isoperimetric inequality for unions of Penrose rhombs, which shows that the regular decagon is, in a sense, optimal among these sets. Motivated by the analysis of linear densities in the Penrose plane we introduce a surface energy for a class of polygons, which is analogous to the Gibbs—Curie surface energy for periodic crystals. This energy is minimized by the Wulff-shape, which is always a polygon and in certain cases it is the regular decagon, in accordance with the fivefold symmetry of quasicrystals. Received June 1, 1997, and in revised form November 3, 1997.     

Shedding vertices of vertex decomposable well-covered graphs

We focus our attention on well-covered graphs that are vertex decomposable. We show that for many known families of these vertex decomposable graphs, the set of shedding vertices forms a dominating set. We then construct three new infinite families of well-covered graphs, none of which have this property. We use these results to provide a minimal counterexample to a conjecture of Villarreal regarding Cohen–Macaulay graphs.     

Aperiodic tiles

A set of tiles (closed topological disks) is calledaperiodic if there exist tilings of the plane by tiles congruent to those in the set, but no such tiling has any translational symmetry. Several aperiodic sets have been discussed in the literature. We consider a number of aperiodic sets which were briefly described in the recent bookTilings and Patterns, but for which no proofs of their aperiodic character were given. These proofs are presented here in detail, using a technique with goes back to R. M. Robinson and Roger Penrose. The research of Branko Grünbaum was supported in part by NSF Grants MCS8301971 and DMS-8620181.     

Triangular Dissections, Aperiodic Tilings, and Jones Algebras

The Brattelli diagram associated with a given bicolored Dynkin-Coxeter graph of type A_n determines planar fractal sets obtained by infinite dissections of a given triangle. All triangles appearing in the dissection process have angles that are multiples of π/(n + 1). There are usually several possible infinite dissections compatible with a given n but a given one makes use of n/2 triangle types if n is even. Jones algebra with index [4 cos²(π/(n + 1))]⁻¹ (values of the discrete range) act naturally on vector spaces associated with those fractal sets. Triangles of a given type are always congruent at each step of the dissection process. In the particular case n = 4, there are isometric and the whole structure lead, after proper inflation, to aperiodic Penrose tilings. The "tilings" associated with other values of the index are discussed and shown to be encoded by equivalence classes of infinite sequences (with appropriate constraints), using n/2 digits (if- n is even) and generalizing the Fibonacci numbers.     

Minimal separating sets of maximum size

A connected graph G can be disconnected or reduced to a single vertex by removing an appropriate subset of the vertex set V(G), and can be disconnected by removing a suitable subset of the edge set E(G). Attention has usually been centered on separating sets having minimum cardinality, and parameters called the vertex connectivity and the edge connectivity defined. These classical concepts are generalized by using separating sets which are minimal. By considering the maximum as well as the minimum cardinality of such sets, one defines vertex and edge connectivity parameters. Sharp upper bounds are established for these numbers and their values computed for certain classes of graphs. An analogue of Whitney's theorem on connectivity is obtained. Parameters are also defined for minimal separating sets consisting of a mixture of vertices and edges, and these are shown to depend on the maximum and minimum values of the vertex and edge connectivity parameters.     

A Note on Shelling

The radial distribution function is a characteristic geometric quantity of a point set in Euclidean space that reflects itself in the corresponding diffraction spectrum and related objects of physical interest. The underlying combinatorial and algebraic structure is well understood for crystals, but less so for non-periodic arrangements such as mathematical quasicrystals or model sets. In this note we summarise several aspects of central versus averaged shelling, illustrate the difference with explicit examples and discuss the obstacles that emerge with aperiodic order.     

A primer of substitution tilings of the Euclidean plane

This paper is intended to provide an introduction to the theory of substitution tilings. For our purposes, tiling substitution rules are divided into two broad classes: geometric and combinatorial. Geometric substitution tilings include self-similar tilings such as the well-known Penrose tilings; for this class there is a substantial body of research in the literature. Combinatorial substitutions are just beginning to be examined, and some of what we present here is new. We give numerous examples, mention selected major results, discuss connections between the two classes of substitutions, include current research perspectives and questions, and provide an extensive bibliography. Although the author attempts to represent the field as a whole, the paper is not an exhaustive survey, and she apologizes for any important omissions.     

Greedy maximal independent sets via local limits

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree.     

An Algebraic Invariant for Substitution Tiling Systems

We consider tilings of Euclidean spaces by polygons or polyhedra, in particular, tilings made by a substitution process, such as the Penrose tilings of the plane. We define an isomorphism invariant related to a subgroup of rotations and compute it for various examples. We also extend our analysis to more general dynamical systems.