We present a combinatorial interpretation of Chebyshev polynomials. The nth Chebyshev polynomial of the first kind, Tn(x), counts the sum of all weights of n-tilings using light and dark squares of weight x and dominoes of weight −1, and the first tile, if a square must be light. If we relax the condition that the first square must be light, the sum of all weights is the nth Chebyshev polynomial of the second kind, Un(x). In this paper we prove many of the beautiful Chebyshev identities using the tiling interpretation.

The classical Riemann Mapping Theorem has many discrete analogues. One of these, the Finite Riemann Mapping Theorem of Cannon, Floyd, Parry, and others, describes finite tilings of quadrilaterals and annuli. It relates to several combinatorial moduli, similar in nature to the classical modulus. The first chapter surveys some of these discrete analogues. The next chapter considers appropriate extensions to infinite tilings of half-open quadrilaterals and annuli. In this chapter we prove some results about combinatorial moduli for such tilings. The final chapter considers triangulations of open topological disks. It has been shown that one can classify such triangulations as either parabolic or hyperbolic, depending on whether an associated combinatorial modulus is infinite or finite. We obtain a criterion for parabolicity in terms of the degrees of vertices that lie within a specified distance of a given base vertex. / Ph. D.

The goal of this thesis is to examine the actions of finite symmetry groups on aperiodic tilings. To an aperiodic tiling with finite local complexity arising from a primitive substitution rule one can associate a metric space, transformation groupoids, and C*-algebras. Finite symmetry groups of the tiling act on each of these objects and we investigate appropriate constructions on each, namely the orbit space, semidirect product groupoids, and crossed product C*-algebras respectively. Of particular interest are the crossed product C*-algebras; we derive important structure results about them and compute their K-theory.

The goal of this thesis is to examine the actions of finite symmetry groups on aperiodic tilings. To an aperiodic tiling with finite local complexity arising from a primitive substitution rule one can associate a metric space, transformation groupoids, and C*-algebras. Finite symmetry groups of the tiling act on each of these objects and we investigate appropriate constructions on each, namely the orbit space, semidirect product groupoids, and crossed product C*-algebras respectively. Of particular interest are the crossed product C*-algebras; we derive important structure results about them and compute their K-theory.

The Kari-Culik tilings are formed from a set of 13 Wang tiles that tile the plane only aperiodically. They are the smallest known set of Wang tiles to do so and are not as well understood as other examples of aperiodic Wang tiles. We show that a certain subset of the Kari-Culik tilings, namely those whose rows can be interpreted as Sturmian sequences (rotation sequences), is minimal with respect to the Z^2 action of translation. We give a characterization of this space as a skew product as well as explicit bounds on the waiting time between occurrences of m × n configurations. / Graduate / 0405

The goal of this thesis is to examine the actions of finite symmetry groups on aperiodic tilings. To an aperiodic tiling with finite local complexity arising from a primitive substitution rule one can associate a metric space, transformation groupoids, and C*-algebras. Finite symmetry groups of the tiling act on each of these objects and we investigate appropriate constructions on each, namely the orbit space, semidirect product groupoids, and crossed product C*-algebras respectively. Of particular interest are the crossed product C*-algebras; we derive important structure results about them and compute their K-theory.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Desde los inicios de la la teoría ergódica la teoría espectral ha representado una herramienta potente para entender distintos aspectos de la dinámica de un sistema. La relación entre estas teorías se establece a través del operador de Koopman definido a partir de un sistema diná- mico en distintos espacios funcionales. Entre los resultados notables que se han demostrado utilizando ésta idea se pueden mencionar dos atribuídos a John von Neumann: un teorema ergódico y una caracterización de los sistemas de espectro discreto (ver [29]). Los operadores de Koopman se pueden estudiar a partir de las medidas espectrales, debido al teorema de representación espectral. Si bien ésta es una manera útil de caracterizar esos operadores, calcular las medidas espectrales es un problema difícil en el contexto general. Por esta razón es que se busca obtener información sobre ellas de forma indirecta, por ejemplo, a través de sus decaimientos asintóticos. Los sistemas dinámicos en donde ha sido posible describir las medidas espectrales son muy pocos y una categoría muy explorada es la de aquellos provenientes de substituciones y en particular de substituciones de largo constante [29]. Más recientemente, inspirados en [17], Bufetov y Solomyak prueban en [7] módulos de continuidad para las medidas espectrales asociadas a sistemas de tilings substitutivos uni- dimensionales. En [11] se generaliza uno de los resultados de [7] al contexto de sistemas de tilings susbtitutivos del espacio euclideano R d . Más precisamente se dan cotas del decaimiento de las medidas espectrales en torno al orígen. En el presente trabajo de tesis se generalizan las ideas de [7] encontrando un módulo de continuidad de tipo log-Hölder para las medidas espectrales en sistemas substitutivos de tilings de R d , pero para puntos alejados del orígen. Entre las técnicas esenciales que se usan para la demostración están la de representar las medidas espectrales como productos de Riesz matriciales, estimaciones del crecimiento de sumas torcidas de Birkhoff y su relación con los decaimientos de las medidas espectrales, la descomposición en sistemas de torres del sistema substitutivo de tilings y argumentos de teoría de números de Pisot. El resultado principal permite entender la parte continua del espectro de un sistema di- námico de tiling substitutivo. Los decaimientos de las medidas espectrales entregan tasas de débil mezcla como se hace en [23], las que son invariantes de conjugación topológica. Ésto podría ser una herramienta útil para distinguir sistemas dinámicos de espectro continuo. / Este trabajo ha sido parcialmente financiado por el Centro de Modelamiento Matemático

The goal of this thesis is to examine the actions of finite symmetry groups on aperiodic tilings. To an aperiodic tiling with finite local complexity arising from a primitive substitution rule one can associate a metric space, transformation groupoids, and C*-algebras. Finite symmetry groups of the tiling act on each of these objects and we investigate appropriate constructions on each, namely the orbit space, semidirect product groupoids, and crossed product C*-algebras respectively. Of particular interest are the crossed product C*-algebras; we derive important structure results about them and compute their K-theory.

In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of $\mathbb{Z}^n$. In this setting a tile $T$ is just a finite subset of $\mathbb{Z}^n$. We say that $T$ tiles $\mathbb{Z}^n$ if the latter set admits a partition into isometric copies of $T$. Chalcraft observed that there exist $T$ that do not tile $\mathbb{Z}^n$ but tile $\mathbb{Z}^{d}$ for some $d > n$. He conjectured that such $d$ exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset $P$ of size a power of $2$, if $P$ has a greatest and a least element, then there is a positive integer $k$ such that $[2]^k$ can be partitioned into copies of $P$. The third tiling problem is about vertex-partitions of the hypercube graph $Q_n$. Offner asked: if $G$ is a subgraph of $Q_n$ such $|G|$ is a power of $2$, must $V(Q_d)$, for some $d$, admit a partition into isomorphic copies of $G$? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set $P$ is a maximal collinear subset of $P$. P\'or and Wood considered colourings of finite $P$ without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that $|P|$ is large. They conjectured that for all $k,l \ge 2$ there exists an $n \ge 2$ such that if $|P| \ge n$ and $P$ does not contain a line of cardinality larger than $l$, then every colouring of $P$ with $k$ colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case $k=l=3$. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with $n$ vertices and $m$ edges? For sufficiently large $n$ we prove a conjecture of F\"uredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an $r$-uniform graph $H$ is to assign for each of its edges one of the $r!$ possible orderings of its elements. Then, for any $p$-set of vertices $A$ and any $p$-set of indices $I \subset [r]$, we define the $I$-degree of $A$ to be the number of edges containing vertices $A$ in precisely the positions labelled by $I$. Caro and Hansberg were interested in determining whether a given $r$-uniform hypergraph admits an orientation where every set of $p$ vertices has some $I$-degree equal to $0$. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for $r$ large, but false in general.

This thesis consists of three articles all relatedin some way to eigenvalues of random matrices and theirprincipal minors and also to tilings of various planar regions with dominoes or rhombuses.Consider an $N\times N$ matrix $H_N=[h_{ij}]_{i,j=1}^N$ from the Gaussian unitary ensemble (GUE). Denote its principal minors (submatrices in the upper left corner) by $H_n=[h_{ij}]_{i,j=1}^n$ for  $n=1$, \dots, $N$. We show in paper A that  all the $N(N+1)/2$ eigenvaluesof $H_1$, \dots, $H_N$ form a determinantal process on $N$ copies of the real line $\mathbb{R}$. We also show that this distribution arises as a scaling limit in tilings of an Aztec diamond with dominoes.We discuss a corresponding result for rhombus tilings of a hexagonwhich was later proved by Okounkov and Reshtikhin. We give a new proof of that statement in the introductionto this thesis.In paper B we perform a similar analysis for the Anti-symmetric Gaussian unitary ensemble (A-GUE). We show that the positive eigenvalues of an $N\times N$ A-GUE matrix andits principal minors form a determinantal processon $N$ copies of the positive real line $\mathbb{R}^+$.We also show that this distribution of all these eigenvalues appears as a scaling limit of tilings of half a hexagon with rhombuses. In paper C we study the shuffling algorithm for tilings of an Aztec diamond. This leads to the study of an interacting set of interlacedparticles that evolve in time. We conjecture that the diffusion limit of thisprocess is a process studied by Warrenand establish some results in this direction. / QC 20100804