Geometric and algebraic properties of polyomino tilings
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/16628 |
| _version_ | 1811076210600443904 |
|---|---|
| author | Korn, Michael Robert, 1978- |
| author2 | Igor Pak. |
| author_facet | Igor Pak. Korn, Michael Robert, 1978- |
| author_sort | Korn, Michael Robert, 1978- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. |
| first_indexed | 2024-09-23T10:18:01Z |
| format | Thesis |
| id | mit-1721.1/16628 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:18:01Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/166282019-04-11T06:29:49Z Geometric and algebraic properties of polyomino tilings Korn, Michael Robert, 1978- Igor Pak. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. Includes bibliographical references (p. 165-167). This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. In this thesis we study tilings of regions on the square grid by polyominoes. A polyomino is any connected shape formed from a union of grid cells, and a tiling of a region is a collection of polyominoes lying in the region such that each square is covered exactly once. In particular, we focus on two main themes: local connectivity and tile invariants. Given a set of tiles T and a finite set L of local replacement moves, we say that a region [Delta] has local connectivity with respect to T and L if it is possible to convert any tiling of [Delta] into any other by means of these moves. If R is a set of regions (such as the set of all simply connected regions), then we say there is a local move property for T and R if there exists a finite set of moves L such that every r in R has local connectivity with respect to T and L. We use height function techniques to prove local move properties for several new tile sets. In addition, we provide explicit counterexamples to show the absence of a local move property for a number of tile sets where local move properties were conjectured to hold. We also provide several new results concerning tile invariants. If we let ai(t) denote the number of occurrences of the tile ti in a tiling t of a region [Delta], then a tile invariant is a linear combination of the ai's whose value depends only on t and not on r. (cont.) We modify the boundary-word technique of Conway and Lagarias to prove tile invariants for several new sets of tiles and provide specific examples to show that the invariants we obtain are the best possible. In addition, we prove some new enumerative results, relating certain tiling problems to Baxter permutations, the Tutte polynomial, and alternating-sign matrices. by Michael Robert Korn. Ph.D. 2005-05-17T14:43:31Z 2005-05-17T14:43:31Z 2004 2004 Thesis http://hdl.handle.net/1721.1/16628 56018440 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 167 p. 888224 bytes 913600 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Korn, Michael Robert, 1978- Geometric and algebraic properties of polyomino tilings |
| title | Geometric and algebraic properties of polyomino tilings |
| title_full | Geometric and algebraic properties of polyomino tilings |
| title_fullStr | Geometric and algebraic properties of polyomino tilings |
| title_full_unstemmed | Geometric and algebraic properties of polyomino tilings |
| title_short | Geometric and algebraic properties of polyomino tilings |
| title_sort | geometric and algebraic properties of polyomino tilings |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/16628 |
| work_keys_str_mv | AT kornmichaelrobert1978 geometricandalgebraicpropertiesofpolyominotilings |