<p>Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this thesis we investigate two models from statistical mechanics which have received attention in recent years.</p><p>The first is the fully packed loop model. A conjecture from 2001 by Razumov and Stroganov opened the field for a large ongoing investigation of the O(1) loop model and its connections to a refinement of the fully packed loop model. We apply a combinatorial bijection originally found by de Gier to an older conjecture made by Propp.</p><p>The second model is the hard particle model. Recent discoveries by Fendley et al. and results by Jonsson suggests that the hard square model with cylindrical boundary conditions possess some beautiful combinatorial properties. We apply both topological and purely combinatorial methods to related independence complexes to try and gain a better understanding of this model.</p>

Thesis (Ph.D.)--Mathematics, Georgia Institute of Technology, 2008. / Committee Chair: Prof. Jean Bellissard; Committee Member: Prof. Claude Schochet; Committee Member: Prof. Michael Loss; Committee Member: Prof. Stavros Garoufalidis; Committee Member: Prof. Thang Le.

Nous considérons le problème d’un électron sur des pavages quasipériodiques en une et deux dimensions. Nous introduisons tout d’abord les pavages quasipériodiques d’un point de vue géométrique, et défendons en particulier l’idée que ces pavages sont les pavages apériodiques les plus proches de la périodicité. Nous concentrant plus particulièrement sur l’un des pavages quasipériodiques les plus simples, la chaîne de Fibonacci, nous montrons à l’aide d’un groupe de renormalisation que la multifractalité des états électroniques découle directement de l’invariance d’échelle de la chaîne. Élargissant ensuite notre champ d’étude à un ensemble de chaînes quasipériodiques, nous nous intéressons au théorème de label des gaps, qui décrit comment la géométrie d’une chaîne donnée contraint les valeurs que peut prendre la densité d’états intégrée dans les gaps du spectre électronique. Plus précisément, nous nous intéressons à la façon dont l’énoncé de ce théorème est modifié lorsque l’on considère une séquence d’approximants périodiques approchant une chaîne quasipériodique. Enfin, nous montrons comment des champs de hauteurs géométriques peuvent être utilisés pour construire des états électroniques exacts sur des pavages en une et deux dimensions. Ces états sont robustes aux perturbations du hamiltonien, sous réserve que ces dernières respectent les symétries du pavage sous-jacent. Nous relions les dimensions fractales de ces états à la distribution de probabilités des hauteurs, que nous calculons de façon exacte. Dans le cas des chaînes quasipériodiques, nous montrons que la conductivité suit une loi d’échelle de la taille de l’échantillon, dont l’exposant est relié à cette même distribution de probabilités. / We consider the problem of a single electron on one and two-dimensional quasiperiodic tilings. We first introduce quasiperiodic tilings from a geometrical point of view, and point out that among aperiodic tilings, they are the closest to being periodic. Focusing on one of the simplest one-dimensional quasiperiodic tilings, the Fibonacci chain, we show, with the help of a renormalization group analysis, that the multifractality of the electronic states is a direct consequence of the scale invariance of the chain. Considering now a broader class of quasiperiodic chains, we study the gap labeling theorem, which relates the geometry of a given chain to the set of values the integrated density of states can take in the gaps of the electronic spectrum. More precisely, we study how this theorem is modified when considering a sequence of approximant chains approaching a quasiperiodic one. Finally, we show how geometrical height fields can be used to construct exact eigenstates on one and two-dimensional quasiperiodic tilings. These states are robust to perturbations of the Hamiltonian, provided that they respect the symmetries of the underlying tiling. These states are critical, and we relate their fractal dimensions to the probability distribution of the height field, which we compute exactly. In the case of quasiperiodic chains, we show that the conductivity follows a scaling law, with an exponent given by the same probability distribution.

"Dynamics" is very roughly the study of how objects change in time; for instance whether an electrical circuit goes to equilibrium, due to thermal dissipation. By "information", we mean how helpful it is to observe an object in order to know it better, for instance how many binary digits we can acquire on the value of a voltage by an appropriate measure. A "computation" is a physical process, e.g. the flow of current into a complex set of transistors, that after some time eventually gives us the solution of a mathematical problem (such as "Is 13 prime?"). We are interested to various relations between these concepts. In a first chapter, we unify some arguments in the literature to show that a whole class of quantities of dynamical systems are uncomputable. For instance the topological entropy of tilings and Turing machines. Then we propose a precise meaning to the statement "This dynamical system is a computer", at least for symbolic systems, such as cellular automata. We also show, for instance, that a "computer" must be dynamically unstable, and can even be chaotic. In a third chapter, we compare how complicated it is to control a system according whether we can acquire information on it ("feedback") or not ("open loop"). We are specifically interested in finite-state systems. In last chapter we show how to control a scalar linear system when only a finite amount of information can be acquired at every step of time.

We review the construction of three Smale spaces associated to a unimodular Pisot substitution on d letters: a subshift of finite type (SFT), a substitution tiling space, and a hyperbolic toral automorphism on the Euclidean d-torus. By considering an SFT whose elements are biinfinite, rather than infinite, paths in the graph associated to the substitution, we modify a well-known map to obtain a factor map between our SFT and the hyperbolic toral automorphism on the d-torus given by the incidence matrix of the substitution. We prove that if the tiling substitution forces its border, then this factor map is the composition of an s-resolving factor map from the SFT to a one-dimensional substitution tiling space and a u-resolving factor map from the tiling space to the d-torus.

We review the construction of three Smale spaces associated to a unimodular Pisot substitution on d letters: a subshift of finite type (SFT), a substitution tiling space, and a hyperbolic toral automorphism on the Euclidean d-torus. By considering an SFT whose elements are biinfinite, rather than infinite, paths in the graph associated to the substitution, we modify a well-known map to obtain a factor map between our SFT and the hyperbolic toral automorphism on the d-torus given by the incidence matrix of the substitution. We prove that if the tiling substitution forces its border, then this factor map is the composition of an s-resolving factor map from the SFT to a one-dimensional substitution tiling space and a u-resolving factor map from the tiling space to the d-torus.

[pt] Coberturas de um disco quadriculado com buracos D são contados de acordo com volume (na variável formal q) e fluxo (em p1, p2, ..., pN). Consideramos propriedades algébricas dos resultados gerados pela função F (p1, p2, ..., pN, q). Para números fixos p2, ..., pN, q > 0 o polinômio f(p1) = F(p1, p2, ..., pN, q) tem todas as raízes reais (e negativas). / [en] Tilings of a quadriculated disk with holes D are counted according to vol- ume (in the formal variabel q) and flux (in p1; p2;... pN). We consider algebraic properties of the resulting generating function D (p1; p2; ...; pk; q). For p1; p2; ...; bpi; ...; pn; q > 0 the polynomial f(pi) = D (p1; p2; ... ; pi; ...; pn; q) has all roots real numbers (and negative).

Ce travail de thèse porte sur l'étude de systèmes dynamiques substitutifs. Les substitutions ont historiquement été introduites pour décrire la suite des sommes des chiffres modulo 2 en base 2 . On étudie des propriétés de la suite somme des chiffres et notamment les propriétés des densités asymptotiques d'ensembles liés aux autocorrélations de fonctions arithmétiques définies par les fonctions somme des chiffres. On démontre notamment un théorème de la limite centrale pour ces densités. On étudie également les propriétés de régularité de la fonction de pression dans le cadre du formalisme thermodynamique, introduit par Bowen, Ruelle et Sinaï, pour une famille de potentiels définis en terme de distance à l'attracteur de la substitution de k-bonacci. On démontre la convergence des itérés de l'opérateur de renormalisation introduit par Baraviera, Leplaideur et Lopes vers un point fixe pour cette même famille de potentiels. Enfin, on étudie des propriétés de régularité de certaines mesures spectrales associées à des pavages auto-similaires en s'appuyant sur des travaux de Bufetov et Solomyak portant sur les déviations des sommes ergodiques dans le cas de l'action par translation de \R^d sur les pavages auto-similaires de R^d. On démontre qu'après renormalisation, ces mesures spectrales se comportent comme des mesures de Radon autour de zér / In the present work we study substitutive dynamical systems. Historically, substitutions have been introduced in order to describe the sequence of the sum-of-digits mod 2 in base 2. We study some properties of densities of sets defined by sum-of-digits functions, sets which are linked with autocorrelations of some arithmétic functions. We prove that these densities are usually normally distributed. We also study the regularity of the pressure function in the framework of the thermodynamics formalism, introduced by Bowen, Ruelle and Sinaï, for a family of potentials defined in terms of distance to the attractor of the k-bonacci substitution. We also show that the iterations of the renormalisation operator defined by Baraviera, Leplaideur and Lopes converges towards a fixed point of this operator. Finally we study the regularity of some spectral measures associated to self-similar tilings using mostly works from Bufetov and Solomyak on the deviations of ergodic sums for the action of translations by vectors in R^d on self-similar tilings of R^d. We prove that, afeter renormalisation, these spectral measures behave like Radon measures around

Le modèle de dimères, également connu sous le nom de modèle de couplage parfait, est un modèle probabiliste introduit à l'origine dans la mécanique statistique. Une configuration de dimères d'un graphe est un sous-ensemble des arêtes tel que chaque sommet est incident à exactement une arête. Un poids est attribué à chaque arête et la probabilité d'une configuration est proportionnelle au produit des poids des arêtes présentes. Dans cette thèse, nous étudions principalement deux modèles qui sont liés au modèle de dimères, et plus particulièrement leur comportements limites. Le premier est le modèle des forêts couvrantes enracinées sur des cycles (CRSF) sur le tore, qui sont en bijection avec les configurations de dimères via la bijection de Temperley. Dans la limite quand la taille du tore tend vers l'infini, la mesure sur les CRSF converge vers une mesure de Gibbs ergodique sur le plan tout entier. Nous étudions la connectivité de l'objet limite, prouvons qu'elle est déterminée par le changement de hauteur moyen de la mesure de Gibbs ergodique et donnons un diagramme de phase. Le second est le modèle de perles, un processus ponctuel sur $\mathbb{Z}\times\mathbb{R}$ qui peut être considéré comme une limite à l'échelle du modèle de dimères sur un réseau hexagonal. Nous formulons et prouvons un principe variationnel similaire à celui du modèle dimère \cite{CKP01}, qui indique qu'à la limite de l'échelle, la fonction de hauteur normalisée d'une configuration de perles converge en probabilité vers une surface $h_0$ qui maximise une certaine fonctionnelle qui s'appelle "entropie". Nous prouvons également que la forme limite $h_0$ est une limite de l'échelle des formes limites de modèles de dimères. Il existe une correspondance entre configurations de perles et (skew) tableaux de Young standard, qui préserve la mesure uniforme sur les deux ensembles. Le principe variationnel du modèle de perles implique une forme limite d'un tableau de Young standard aléatoire. Ce résultat généralise celui de \cite{PR}. Nous dérivons également l'existence d'une courbe arctique d'un processus ponctuel discret qui encode les tableaux standard, defini dans \cite{Rom}. / The dimer model, also known as the perfect matching model, is a probabilistic model originally introduced in statistical mechanics. A dimer configuration of a graph is a subset of the edges such that every vertex is incident to exactly one edge of the subset. A weight is assigned to every edge, and the probability of a configuration is proportional to the product of the weights of the edges present. In this thesis we mainly study two related models and in particular their limiting behavior. The first one is the model of cycle-rooted-spanning-forests (CRSF) on tori, which is in bijection with toroidal dimer configurations via Temperley's bijection. This gives rise to a measure on CRSF. In the limit that the size of torus tends to infinity, the CRSF measure tends to an ergodic Gibbs measure on the whole plane. We study the connectivity property of the limiting object, prove that it is determined by the average height change of the limiting ergodic Gibbs measure and give a phase diagram. The second one is the bead model, a random point field on $\mathbb{Z}\times\mathbb{R}$ which can be viewed as a scaling limit of dimer model on a hexagon lattice. We formulate and prove a variational principle similar to that of the dimer model \cite{CKP01}, which states that in the scaling limit, the normalized height function of a uniformly chosen random bead configuration lies in an arbitrarily small neighborhood of a surface $h_0$ that maximizes some functional which we call as entropy. We also prove that the limit shape $h_0$ is a scaling limit of the limit shapes of a properly chosen sequence of dimer models. There is a map form bead configurations to standard tableaux of a (skew) Young diagram, and the map is measure preserving if both sides take uniform measures. The variational principle of the bead model yields the existence of the limit shape of a random standard Young tableau, which generalizes the result of \cite{PR}. We derive also the existence of an arctic curve of a discrete point process that encodes the standard tableaux, raised in \cite{Rom}.

[pt] Nessa dissertação estudamos coberturas por dominós de regiões tridimensionais. Em particular, consideramos o problema de conectividade por flips de cilindros, ou seja, regiões da forma D ×[0,N]. Um flip é um movimento local: dois dominós adjacentes são removidos e recolocados em outra posição. Em duas dimensões, duas coberturas de uma mesma região contrátil podem ser conectadas por flips. Em dimensão 3, o problema é mais sutil. Apresentamos o twist, um invariante por flips que associa uma cobertura a um número inteiro. Para muitas regiões 3D, existem exemplos de coberturas com o mesmo twist que não podem ser ligadas por uma sequência de flips. Artigos recentes mostram que para muitos discos D, chamados regulares, duas coberturas do cilindro D × [0,N] com o mesmo twist podem ser ligadas por flips uma vez que adicionamos espaço vertical ao cilindro. Esses resultados são apresentados e discutidos. Nós então demonstramos a regularidade ou irregularidade de vários discos. Verificamos que um gargalo muitas vezes implica na irregularidade. / [en] In this dissertation we study domino tilings of three-dimensional regions. In particular, we consider the flip connectivity problem for cylinders, i.e, regions of the form D×[0,N]. A flip is a local move: two adjacent dominoes are removed and placed back in a different position. In two dimensions, two domino tilings of the same contractible region are connected by flips. In dimension 3, the problem is subtler. We present the twist, a flip invariant that associatean integer number with a tiling. For many 3D regions, there exist examples of tilings with the same twist which can not be joined by a sequence of flips. Recent papers prove that for certain disks D, called regular, two tilings of the cylinder D × [0,N] with the same twist can be joined by a sequence of flips once we add vertical space to the cylinder. These results are presented and discussed. We then prove regularity or irregularity for new families of quadriculated disks. It turns out that a bottleneck often implies irregularity.