Why are some tilings introduced as geometrical objects, not graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T04:55:48Z http://mathoverflow.net/feeds/question/12019 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12019/why-are-some-tilings-introduced-as-geometrical-objects-not-graphs Why are some tilings introduced as geometrical objects, not graphs? Pontus Rehula 2010-01-16T21:21:46Z 2010-01-17T12:19:02Z <p>Let's say you have a planar tiling. Quite often these tilings are introduced as geometrical objects with metrics; each tile having coordinates assigned to its vertices.</p> <p>The tiling has an associated graph: the nodes of the graph are the vertices of the tiles, etc.</p> <p>What kind of additional value is in general provided by insisting the tile vertices to have coordinates? Does not discussing the properties of the tiling graph topology give enough information?</p> <p>I understand that the answer depends on the type of the tiling in question.</p> <p>If one takes graphs as the starting point, then what would be some natural ways to define infinite planar graph periodicity so that there would exist periodic planar tilings corresponding to a given graph?</p> <p>Can Penrose tiling be defined by its graph topology and can some of its general properties, like aperiodicity, be described purely by its tiling graph without relying on the angles and edge length of the tiles?</p> <p>(If You find this post fuzzy or ignorant, that would be because the poster is not a professional mathematician.)</p> <p>Pontus</p> http://mathoverflow.net/questions/12019/why-are-some-tilings-introduced-as-geometrical-objects-not-graphs/12026#12026 Answer by David Eppstein for Why are some tilings introduced as geometrical objects, not graphs? David Eppstein 2010-01-16T21:52:04Z 2010-01-16T21:52:04Z <p>To answer a tiny part of your question: for the Penrose tiling (I prefer the version with two kinds of rhombs), the geometry can be completely recovered from the graph structure. The graph is an infinite planar graph with a unique embedding in which every face is a quadrilateral. Any planar drawing of its dual graph forms a system of points (the dual vertices) and bounded curves (the dual edges) such that four curves meet at each vertex, and we can group these bounded curves into infinite curves by connecting the four curves at each vertex into two opposite pairs. When connected in this way, this system of infinite curves forms a <a href="http://en.wikipedia.org/wiki/Arrangement%5Fof%5Flines" rel="nofollow">pseudoline arrangement</a> in which there are five parallel families of pseudolines, and one can determine whether a rhomb should be fat or thin according to which pair of families its dual vertex forms a crossing point of. I think in this case at least the aperiocity of the Penrose tiling is reflected in the fact that its graph has at most finitely many automorphisms, because an infinite automorphism group of the graph would by this construction lead to an infinite automorphism group of the geometric tiling.</p> http://mathoverflow.net/questions/12019/why-are-some-tilings-introduced-as-geometrical-objects-not-graphs/12042#12042 Answer by Joel David Hamkins for Why are some tilings introduced as geometrical objects, not graphs? Joel David Hamkins 2010-01-16T23:21:09Z 2010-01-17T00:26:47Z <p>Some very interesting types of tiling problems have a trivial graph. For example, the <a href="http://en.wikipedia.org/wiki/Wang%5Ftile" rel="nofollow">Wang tiling problem</a> uses square tiles, which are labeled on the sides, and the rule for the tiling is that the labels must match. (So the graph is just the integer lattice.) One of the most interesting things about this type of tiling is that the question of whether a given finite set of tile types admits a tiling is <em>undecidable</em>. That is, there can in principal be no computational algorithm that will correctly determine whether a given finite set of tiles admits a tiling. The reason for this is that the operation of Turing machines is encodable into these tiling problems: for any Turing machine program p, one can uniformly construct a finite set of tiles that admits a tiling if and only if this program halts (on input 0, say). Basically, the patttern of tiling can continue to tile the plane as long as the Turing computation doesn't halt, but a halting computation messes up the existence of a tiling.</p> <p>However, one can encode many or most of the usual geometric tile problems into these wang tiles, by dividing each geometric figure into square pixels, which must be matches together. So in a strong sense, any geometric tiling problem reduces to an instance of a Wang tiling problem. Thus, the general geometric tiling problem is also undecidable.</p> http://mathoverflow.net/questions/12019/why-are-some-tilings-introduced-as-geometrical-objects-not-graphs/12094#12094 Answer by Douglas Zare for Why are some tilings introduced as geometrical objects, not graphs? Douglas Zare 2010-01-17T12:19:02Z 2010-01-17T12:19:02Z <p>We keep the geometric structure on tilings mainly because the tilings are generated with that structure, often from lattices or geometric group actions. </p> <p>It's quite nontrivial that if you take some types of nice tilings, and forget the geometric structure, then you can indeed recover important information about the tiling from the graph alone. You can recover whether the tiling is periodic by looking at the group of symmetries of the graph. You can also recover information about the space, not just the tiling. You can recover whether the tiling is of the Euclidean or hyperbolic plane by looking at the growth rate of the perimeter of a ball. You can recover whether the tiling was on a topological cylinder vs. the plane, as you can still define the "end" of a graph, and see that a tiling of the cylinder will have two ways to go off to infinity rather than 1 in the plane. </p> <p>This is a start of what is knwon as <em><a href="http://en.wikipedia.org/wiki/Geometric%5Fgroup%5Ftheory" rel="nofollow">geometric group theory</a></em>. Given a group and some finite set of generators for that group, you can construct a Cayley whose vertices are the elements of that group, whose edges connect an element $g$ with $gg_i$ and $gg_i^{-1}$ for each generator $g_i$. Then you can try to recover information about the group from the geometric properties of the graph.</p> <p>There is a natural metric $d$ on the Cayley graph, so that each edge has length 1. From one perspective, it's bad that we are getting different graphs from different sets of generators. To identify these as essentially the same, we consider <em>quasi-isometries,</em> maps $f$ from one space to another such that there are constants $C_0$ and $C_1$ so that for every $x,y$, $\frac1{C_1} d(x,y) - C_0 \le d(f(x),f(y)) \le C_1 d(x,y) + C_0$. Changing from one set of generators to another is a quasi-isometry, since we can express each generator as a finite word in the other set of generators. Thus, many people study finitely generated groups up to quasi-isometry. </p> <p>Choices for sets of relations may correspond to tilings. You can attach a 2-cell to the graph along the word of a relation. Topological and geometric properties of this complex have meaning in group theory. </p> <p>Anyway, back to tilings of the plane. There are more reasons to keep the geometry. This picks out a few graphs among the many which embed in the plane. We also get convenient ways to compare tilings. For example, we can look at the vertices of a second tiling which are near a vertex in the first tiling. We can more easily consider entire families of tilings to try to classify all tilings of a type.</p> <p>For the Penrose tilings in particular, I would hate to ignore the nice lift from number theory of a tiling to a map from the plane to $\mathbb R^4$. If you consider a tiling by rhombuses so that each edge is $\pm \zeta_5^i$, where $\zeta_5$ is a 5th root of unity, then you see that you can give each vertex a 5-dimensional set of coordinates as an integer linear combination of the 5th roots of unity. Of course, since the sum of the 5th roots of unity and 1 is 0, you can drop the dimension to 4 by considering sums of fifths of integers which add up to 0. There are nice ways to generate Penrose tilings by 2-dimensional planes in that 4-dimensional space. I don't know the classification of Penrose tilings, but I bet it has something to do with that lift, which is not obvious from the graph.</p>