Ribbon tilings and multidimensional height functions

DOI10.1090/S0002-9947-02-02981-1MaRDI QIDQ3151254zbMATH OpenFDO

Authors Scott Sheffield

Publication date 7 October 2002

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0107095

zbMATH Keywords

polyomino tiling problemsribbon tile

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Combinatorics in computer science (68R05)

Abstract: We fix $n$ and say a square in the two-dimensional grid indexed by $(x,y)$ has color $c$ if $x+yequivcpmodn$. A {it ribbon tile} of order $n$ is a connected polyomino containing exactly one square of each color. We show that the set of order-$n$ ribbon tilings of a simply connected region $R$ is in one-to-one correspondence with a set of {it height functions} from the vertices of $R$ to $mathbb{Z}^n$ satisfying certain difference restrictions. It is also in one-to-one correspondence with the set of acyclic orientations of a certain partially oriented graph. Using these facts, we describe a linear (in the area of $R$) algorithm for determining whether $R$ can be tiled with ribbon tiles of order $n$ and producing such a tiling when one exists. We also resolve a conjecture of Pak by showing that any pair of order-$n$ ribbon tilings of $R$ can be connected by a sequence of local replacement moves. Some of our results are generalizations of known results for order-2 ribbon tilings (a.k.a. domino tilings). We also discuss applications of multidimensional height functions to a broader class of polyomino tiling problems.

Recommendations

• Ribbon tile invariants
• Ribbon tile invariants from the signed area
• An optimal algorithm to generate tilings
• Tiling pictures of the plane with dominoes
• On enumeration and entropy of ribbon tilings

Cites work

• A note on tiling with integer-sided rectangles
• A Partial Order on the Regions of R n Dissected by Hyperplanes
• A Pedestrian Approach to a Method of Conway, or, A Tale of Two Cities
• A Schensted algorithm for rim hook tableaux
• A variational principle for domino tilings
• Acyclic orientations of graphs
• Analyzing Glauber dynamics by comparison of Markov chains
• Conformal invariance of domino tiling.
• Conway's Tiling Groups
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• scientific article; zbMATH DE number 3166255 (Why is no real title available?)
• scientific article; zbMATH DE number 3771876 (Why is no real title available?)
• scientific article; zbMATH DE number 1256699 (Why is no real title available?)
• scientific article; zbMATH DE number 1261817 (Why is no real title available?)
• scientific article; zbMATH DE number 1168037 (Why is no real title available?)
• Local statistics for random domino tilings of the Aztec diamond
• Longest increasing subsequences of random colored permutations
• On tilings by ribbon tetrominoes
• Quantum gravity and inventory accumulation
• Ribbon tile invariants
• Ribbon tile invariants from the signed area
• The connectivity of acyclic orientation graphs
• The projective fundamental group of a ℤ²-shift
• Tile invariants: New horizons.
• Tiling with polyominoes and combinatorial group theory
• Tilings, fundamental cocycles and fundamental groups of symbolic ${\Bbb Z}^{d}$-actions

Cited in

(14)

• Ribbon tile invariants from the signed area
• Functions tiling with several lattices
• Deducing a variational principle with minimal \textit{a priori} assumptions
• Covering rectangles by few monotonous polyominoes
• Four-cycle free graphs, height functions, the pivot property and entropy minimality
• scientific article; zbMATH DE number 871912 (Why is no real title available?)
• Cuspidal ribbon tableaux in affine type A
• On enumeration and entropy of ribbon tilings
• The number of ribbon tilings for strips
• Character theory and categorification. Abstracts from the workshop held August 28 -- September 3, 2022
• Tile invariants for tackling tiling questions
• Lattice structure for orientations of graphs
• A variational principle for a non-integrable model
• Local move connectedness of domino tilings with diagonal impurities

This page was built for publication: Ribbon tilings and multidimensional height functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3151254)