"Science, Faculty of"@en .
"Physics and Astronomy, Department of"@en .
"DSpace"@en .
"UBCV"@en .
"Chen, Si"@en .
"2013-08-27T18:06:47Z"@en .
"2013"@en .
"Doctor of Philosophy - PhD"@en .
"University of British Columbia"@en .
"This thesis is divided into three chapters. Chapter 1 is a study of statistical models of graphs, in order to explore possible realizations of emergent manifolds. Graphs with given numbers of vertices and edges are considered, governed by a Hamiltonian that favors graphs with near-constant valency and local rotational symmetry. The model is simulated numerically in the canonical ensemble. It is found that the model exhibits a first-order phase transition, and that the low energy states are almost triangulations of two dimensional manifolds. The resulting manifold shows topological \"handles\" and surface intersections in a higher embedding space as well as non-trivial fractal dimension. The model exhibits a phase transition temperature of zero in the bulk limit. We explore the effects of adding long-range interactions to the model, which restore a finite transition temperature in the bulk limit.\nIn Chapter 2, aspects of Chern-Simons theory are studied. The relations between Chern-Simons theory, a model known as BF theory named after the fields that appear in the actions, and 3D gravity, are explored and generalized to the case of non-orientable spacetime manifolds. U(1) Chern-Simons theory is quantized canonically on orientable manifolds, and U(1) BF theory is similarly quantized on non-orientable manifolds. By requiring the quantum states to form a representation of the deformed holonomy group and the deformed large gauge transformation group, we find that the mapping class group of the spacetime manifold can be consistently represented, provided the prefactor k of the Chern-Simon action satisfies quantization conditions which in general are non-trivial. We also find a k <--> 1/k duality for the representations. \nMotivated by open questions about interpreting the finite size results from Chapter 1, models of finite size scaling for systems with a first-order phase transition are discussed in Chapter 3. Three physics models -- the Potts model, the Go model for protein folding, and the graph model in Chapter 1 -- are simulated. Several finite size scaling models, including three functional forms to fit the energy distributions, and a capillarity model, are compared with simulations of the corresponding physics models."@en .
"https://circle.library.ubc.ca/rest/handle/2429/44920?expand=metadata"@en .
"Emergence of Riemannian manifoldsfrom graphs and aspects ofChern-Simons theorybySi ChenB.Sc., Peking University, 2006A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Physics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2013c? Si Chen 2013AbstractThis thesis is divided into three chapters. Chapter 1 is a study of statistical modelsof graphs, in order to explore possible realizations of emergent manifolds. Graphs withgiven numbers of vertices and edges are considered, governed by a Hamiltonian that favorsgraphs with near-constant valency and local rotational symmetry. The model is simulatednumerically in the canonical ensemble. It is found that the model exhibits a first-orderphase transition,and that the low energy states are almost triangulations of two dimensionalmanifolds. The resulting manifold shows topological ?handles? and surface intersectionsin a higher embedding space as well as non-trivial fractal dimension. The model exhibitsa phase transition temperature of zero in the bulk limit. We explore the effects of addinglong-range interactions to the model, which restore a finite transition temperature in thebulk limit.In Chapter 2, aspects of Chern-Simons theory are studied. The relations between Chern-Simons theory, a model known as BF theory named after the fields that appear in theactions, and 3D gravity, are explored and generalized to the case of non-orientable spacetimemanifolds. U(1) Chern-Simons theory is quantized canonically on orientable manifolds,and U(1) BF theory is similarly quantized on non-orientable manifolds. By requiring thequantum states to form a representation of the deformed holonomy group and the deformedlarge gauge transformation group, we find that the mapping class group of the spacetimemanifold can be consistently represented, provided the prefactor k of the Chern-Simonaction satisfies quantization conditions which in general are non-trivial. We also find ak ? 1/k duality for the representations.Motivated by open questions about interpreting the finite size results from Chapter 1,iiAbstractmodels of finite size scaling for systems with a first-order phase transition are discussed inChapter 3. Three physics models ? the Potts model, the Go? model for protein folding, andthe graph model in Chapter 1 ? are simulated. Several finite size scaling models, includingthree functional forms to fit the energy distributions, and a capillarity model, are comparedwith simulations of the corresponding physics models.iiiPrefaceA version of Chapter 2 has been published in S. Chen and S. S. Plotkin, Phys. Rev.D87 (2013) 084011, arXiv:1210.3372 [gr-qc] [1]. The model was constructed by mysupervisor Dr. Steven S. Plotkin and me together, the simulation was performed by me,and the result analysis and interpretation were conducted by Dr. S. S. Plotkin and me incollaboration.A version of Section 2.5 has been published in S. Chen, Mod. Phys. Lett. A27 (2012)1250087, arXiv:1103.2820 [hep-th] [2]. All the related work was carried out by me, inconsultation with Dr. Gordon Semenoff, Dr. Donald Witt and Dr. Kristin Schleich.A manuscript in preparation contains material from Section 2.3 and Section 2.6. An-other manuscript containing material from Chapter 3 is also in preparation.The material contained in this thesis is the result of two studentships. From Septem-ber 2007 to August 2011, S. Chen was supervised by Dr. G. Semenoff, Dr. D. Witt andDr. K. Schleich. In 2011, S. Chen switched supervisors to Dr. S. S. Plotkin.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Statistical mechanics of graph models and their implications for emergentmanifolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Graph theory preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 The model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Numerical simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.4.1 Rendering graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.4.2 Topology of the manifold in the presence of defects . . . . . . . . . 151.4.3 Phase transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.4.4 Geometric properties . . . . . . . . . . . . . . . . . . . . . . . . . . 251.4.5 Correlation functions . . . . . . . . . . . . . . . . . . . . . . . . . . 31vTable of Contents1.5 Addition of a Coulomb potential . . . . . . . . . . . . . . . . . . . . . . . . 341.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381.7 Appendix: The weighted histogram analysis method . . . . . . . . . . . . . 461.8 Appendix: The Floyd-Warshall algorithm . . . . . . . . . . . . . . . . . . . 471.9 Appendix: The number of random graphs and random semi-regular graphs 482 Aspects of Chern-Simons theory in 2 + 1 dimensions . . . . . . . . . . . 502.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502.2 Fundamentals of Chern-Simons theory . . . . . . . . . . . . . . . . . . . . . 522.3 Relation with the BF theory and 3D gravity . . . . . . . . . . . . . . . . . 552.3.1 p-form densities and integration . . . . . . . . . . . . . . . . . . . . 572.3.2 The relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622.4 The mapping class group . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672.4.1 MCG on orientable manifolds . . . . . . . . . . . . . . . . . . . . . 672.4.2 MCG on non-orientable manifolds . . . . . . . . . . . . . . . . . . . 702.5 Quantization of U(1) CST on orientable manifolds . . . . . . . . . . . . . . 712.5.1 General formalism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732.5.2 Quantization on ?1 = T 2 . . . . . . . . . . . . . . . . . . . . . . . . 762.5.3 Quantization on ?2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 822.5.4 Quantization on ?g, g ? 3 . . . . . . . . . . . . . . . . . . . . . . . 862.5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892.6 Quantization of U(1) BF theory on non-orientable manifolds . . . . . . . . 912.6.1 General formalism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922.6.2 N1, Klein bottle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 942.6.3 N2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952.6.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973 Future directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993.1 Introduction: finite size scaling of systems with first-order phase transition 99viTable of Contents3.2 Physics models and numerical results . . . . . . . . . . . . . . . . . . . . . 1003.2.1 The Potts model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1003.2.2 Structure-based model for protein folding . . . . . . . . . . . . . . . 1013.2.3 The graph model of emergent manifold . . . . . . . . . . . . . . . . 1033.3 Finite size scaling models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1063.3.1 Sum of two Gaussian functions . . . . . . . . . . . . . . . . . . . . . 1063.3.2 Exponential of degree-4 polynomial . . . . . . . . . . . . . . . . . . 1073.3.3 A distribution concentrated near its lower bound . . . . . . . . . . . 1103.3.4 A capillarity model . . . . . . . . . . . . . . . . . . . . . . . . . . . 1123.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119viiList of Figures1.1 Examples for the graph theory concepts . . . . . . . . . . . . . . . . . . . . 41.2 Examples of neighborhood subgraphs . . . . . . . . . . . . . . . . . . . . . . 71.3 A neighborhood in the face-centered cubic lattice graph . . . . . . . . . . . 91.4 A 6-regular graph which is not similar to any manifold . . . . . . . . . . . . 111.5 An example of the Monte Carlo trial moves . . . . . . . . . . . . . . . . . . 131.6 Snapshots from the simulations . . . . . . . . . . . . . . . . . . . . . . . . . 161.7 Examples of some common defects . . . . . . . . . . . . . . . . . . . . . . . 171.8 The average energy density ?E? /NV as a function of inverse temperature ?for for several NV ?s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.9 The rescaled heat capacity C/N2V as a function of inverse temperature ? forseveral NV ?s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.10 Log-log plot of the inverse transition temperature ?c as a function of NV ,and the best fit line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.11 The probability density of the intensive energy E/NV for the systems of sizeNV = 1000, 1500 and 2000, at each system?s transition temperature . . . . 211.12 The acceptance ratio as a function of inverse temperature ? . . . . . . . . . 221.13 The entropy density difference across the transition ?S/NV as a function ofNV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.14 Distribution of edge valencies as a function of inverse temperature ?c forNV = 1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.15 Average distance?d??between pairs of vertices as a function of ? for NV = 1000 26viiiList of Figures1.16 The average distance?d??between pairs of vertices as a function of NV , andthe best fit lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281.17 Log-log plot of?N?r?, the thermally averaged number of vertices within adistance r, as a function of r . . . . . . . . . . . . . . . . . . . . . . . . . . 291.18 Radial correlation functions of valency-7 vertices and of valency-3 edges . . 321.19 Sample configurations for the model with a repulsive Coulomb potential . . 351.20 Transition temperatures ?c as a function of system size NV , with and withoutthe Coulomb potential in (1.11) . . . . . . . . . . . . . . . . . . . . . . . . . 361.21 Sample configurations for the model with an attractive Coulomb potential . 391.22 A 3D tessellation and its dual graph . . . . . . . . . . . . . . . . . . . . . . 412.1 The Dehn twist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682.2 The effect of a Dehn twist on a closed curve . . . . . . . . . . . . . . . . . . 692.3 The Y -homeomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702.4 Fundamental group generators and MCG generators for ?1 . . . . . . . . . 772.5 Fundamental group generators and MCG generators for ?2 . . . . . . . . . 832.6 MCG generators for ?g, g ? 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 873.1 Simulation results of the Potts model . . . . . . . . . . . . . . . . . . . . . . 1023.2 Simulation results for the protein folding model . . . . . . . . . . . . . . . . 1043.3 Simulation results of the graph model . . . . . . . . . . . . . . . . . . . . . 1053.4 Fitting results to the Potts model, using the two-Gaussian model . . . . . . 1083.5 Fitting results to the protein folding model, using the two-Gaussian model . 1093.6 Fitting results to the Potts model, using the distribution (3.11) . . . . . . . 1113.7 Fitting results to the graph model, using the distribution (3.13) . . . . . . . 1133.8 A typical phase-coexisting state of the Potts model . . . . . . . . . . . . . . 1143.9 Fitting result and prediction to the Potts model, using the capillarity model 1163.10 The average interface length as a function of the area of largest component 117ixList of SymbolsFrequently used symbols in Chapter 2 are listed as follows:Symbol Standing for First appearance? wedge product operator eq.(2.1)? tensor product eq.(2.11)A one-form field eq.(2.1)B one-form density field eq.(2.15)Diff(M) diffeomorphism group of M p.68d exterior derivative eq.(2.1)e a? local frame of a Riemannian manifold eq.(2.19)F F = dA+A ?A, curvature of a connection A eq.(2.2)f? pullback of f p.57G depending on the context, Lie group, or eq.(2.3)gravitational constant eq.(2.7)g Lie algebra eq.(2.1)g depending on the context, Lie group valued field, or eq.(2.3)genus of a surface p.68g?? metric tensor eq.(2.2)Hp de Rham cohomology group of degree p eq.(2.12)Id identity matrix of degree d eq.(2.60)J?? Jacobian of transition function p.58k coupling constant in CST and in BF theory p.72xList of SymbolsSymbol Standing for First appearance[M ] orientation on the manifold M p.57M? orientable double cover of M p.58?M boundary of M eq.(2.4)Ng non-orientable surface whose orientable double cover is ?g p.92O orientation bundle p.58p numerator of k p.72q denominator of k p.72sl(2,R) Lie algebra of the special linear group of degree 2 on R p.65SL(2,Z) special linear group of degree 2 on Z p.76U(1) unitary group of degree 1 p.iiu(1) Lie algebra of U(1) p.93Z2 multiplicative group composed of 1 and -1 p.58? 0 or 1 depending on the parities of p and q eq.(2.51)? cosmological constant eq.(2.7)pi1 fundamental group eq.(2.6)? compact two-dimensional manifold without boundary p.54?g orientable surface of genus g p.68? an involution defined on an orientable double cover p.59?p bundle of smooth p-forms p.58? exp(i2pik)p.77? a? b spin connection of a Riemannian manifold eq.(2.20)xiList of SymbolsThe notation conventions employed in Section 2.5 and Section 2.6 are listed as follows:Notation Standing forA,B, . . . u(1)-valued fields, or closed curves corresponding to MCG generatorsa, b, . . . U(1)-valued numbers??, ??, . . . closed curves corresponding to homotopy group generators?, ?, . . . homotopy group generators?, ?, . . . LGT group generators??, ??, . . . irreducible blocks of homotopy group generatorsA,B,Y, . . . MCG generatorsA?, B?, . . . irreducible blocks of MCG generatorsi, j, k indices within an irreducible blockm,n indices of irreducible blocksxiiList of AbbreviationsThe following abbreviations are used in this thesis:Abbreviation Complete phrase First appearanceWHAM weighted histogram analysis method p.19CST Chern-Simons theory p.50MCG mapping class group p.51LGT large group transformation p.72FSS finite size scaling p.99xiiiAcknowledgementsFirst and foremost, I would like to thank my supervisor Dr. Steven S. Plotkin, for hisconstant guidance and support, ever since I joined his research group. I am grateful to myPhD committee members Dr. Mark Van Raamsdonk, Dr. Moshe Rozali and Dr. Colin Gay,for their helpful suggestions in and after the committee meetings, and their support whenI was going through the process of changing supervisor.I wish to thank other group members in the Plotkin Group. Eric Mills, Ali R. Mohazaband Atanu Das have raised interesting questions, and offered insights about my projects.Atanu Das also helped me with the numerical work involved in the protein folding model.Finally, I like to thank the professors of the courses that I have taken and learned somuch from, and thank my officemates for all the enjoyable discussions throughout the years.xivChapter 1Statistical mechanics of graphmodels and their implications foremergent manifolds1.1 IntroductionSince the first systematic studies of random graph models by Erdo?s and Re?nyi [3],the relation between graph theory models and physics models, in particular statisticalphysics models, has attracted much interest. Concepts and tools in graph theory havebeen applied to problems in physics, computer science, and biology to produce remarkableresults. For example, Feynman diagrams that are planar have special roles in the large NQCD model [4]; in causal dynamical triangulation, four-dimensional triangulated manifoldswith fixed edge lengths, which can be viewed as a class of graphs, are used to constructspacetime on the Planck scale to regularize the quantum gravitational path integral [5, 6];statistical mechanical models of network growth can explain the connectivity of systemssuch as the Internet [7]; structures of amorphous solids can be quantified using graphtheory properties [8]; intracellular signalling networks can exhibit emergent behavior storedwithin biochemical reactions, including integration of signals across multiple time scales andself-sustaining feedback loops [9]; neural networks can collectively and robustly producecontent-addressable memories from partial cues [10], indicating capacity for generalization,familiarity recognition, and categorization. Added to these discoveries, a new collection of11.1. Introductiongraph models has been proposed as candidates for emergent spacetime, as described below.A manifold can be approximated by a triangulation, which in turn can be viewed as agraph filled with simplices. From this observation, one can consider how a graph may giverise to a manifold; i.e. from a family of graphs, following some constraints and obeyingsome set of rules for dynamical processes, is it possible that a manifold-like structure canemerge? To be more precise, consider the possibility that a graph G gives rise to a smoothmanifold M . A vertex in G corresponds to a point in M ; when a pair of vertices in Gare connected by an edge, the corresponding pair of points in M have a certain distance \u000F.When the length scale under consideration is much larger than \u000F, G resembles the smoothmanifold M . In such cases, one can say that the manifold M , including its dimensionality,topology, and metric, emerges from the graph G in the continuous limit.From this general idea, in references [11, 12], a graph model was constructed from agiven graph Hamiltonian, where it was proposed that the low-energy phase of the modelmay be interpreted as an emergent spacetime. In addition, it was found that when theedges of the graph possess a spin degree of freedom, the model could give rise to a U(1)gauge theory [12]. In [13], Konopka has analytically and numerically studied the abovegraph model as a statistical model. A phase transition was found, where it was arguedthat the low-temperature phase can be related to spacetime only if the graph can interactwith some matter degrees of freedom. In [14, 15], a related model, which in addition tographs corresponding to spacetimes, also incorporates a matter field that resides on thevertices, was proposed to study the role of matter in the emergence of spacetime fromgraphs. In [16], Conrady has constructed a Hamiltonian favoring low-temperature, two-dimensional manifolds through terms that explicitly favor two-dimensional triangulations;for example, each vertex is favored to have 6 edges as in a triangular lattice, and tetrahedraare penalized. The model was simulated for small system sizes (N ? 180 edges), whichshowed a heat capacity peak, and a transition temperature that decreased with system size.In this chapter, we also investigate a statistical model of graphs, in that the objectsunder consideration are merely abstract graphs, without any information on the positions21.1. Introductionof the vertices, or the lengths of the edges. A graph can randomly transform into anothergraph according to a set of transformation rules. Graphs with given numbers of vertices andedges are considered, and they are governed by a Hamiltonian that favors graphs with a setof local symmetries. If these local symmetries are preserved, the resulting graphs should benearly triangulations of manifolds with a certain dimensionality, where the dimensionalityis controlled by the ratio of vertices to edges. We are interested in whether any globalstructure of the graphs arises as a consequence.Because every edge in this model corresponds to a positive length \u000F, only real positivedistances can arise, so this model can only be used to describe Riemannian manifolds (i.e.,with positive definite metric). The metric of a Riemannian manifold can be alternativelyviewed as a distance function between any pair of points, which satisfies the triangle in-equality. On a graph, there is also a natural notion of distance, namely the length of theshortest path between a pair of vertices. This distance is also positive-definite and satisfiesthe triangle inequality. Thus on any graph, there is a well-defined distance function, aswell as a corresponding geodesic. Graph geodesics between two vertices are often highlydegenerate, however, unlike the case for manifolds. If a manifold is to emerge from a graph,one expects that in the continuous limit all degenerate geodesics are close by, and the dif-ferences of their paths are only of order \u000F. After establishing this distance function betweenvertices, mapping the graph to a Riemannian manifold is still a non-trivial problem. Ifwe enforce that every edge is identical in that they have the same length when mappedto the Riemannian manifold, then only for certain graph configurations will a Riemannianmanifold emerge from the graph. Otherwise the system will be frustrated and unable tomeet the condition of constant edge length, without increasing the dimension above thatof the manifold that would emerge from the graph.In this chapter, after reviewing the relevant graph theory preliminaries, we introducea graph Hamiltonian based only upon local symmetries. We evolve the graph under theMonte Carlo rules obeying statistical mechanical equilibrium, and we investigate whether alow-temperature manifold state emerges. We investigate the sharpness of the phase transi-31.2. Graph theory preliminariesa b cd e f gh i j k lm n o pq r sFigure 1.1: Examples for the graph theory concepts.tion using energy as an order parameter for different size systems, and we discuss the likelyfirst-order nature of the transition. We construct heat capacity curves as a function oftemperature and investigate the transition temperature as a function of system size, whichpoints toward a zero-temperature phase transition in the bulk limit. The Haussdorf dimen-sionality of the emergent manifold is investigated and found to be an increasing functionof system size, and approximately 3 for the largest system sizes we investigated (2000 ver-tices). Correlation functions between defect-carrying vertices and edges are investigated todetermine whether the effective potential between defects is attractive or repulsive. Finally,we argue in analogy to condensed-matter systems that a nonzero phase transition tempera-ture requires long-range interactions, and shows that a Coulombic-like term between graphvertices yields an apparently finite-phase transition temperature, but with a highly ramifiedmanifold.1.2 Graph theory preliminariesBefore motivating for details of the model, we shall remind the reader about some graphtheory concepts, which will be needed later in constructing the model.A graph G is composed of a set of vertices V (G) and a set of edges E(G), where everyedge is a subset of V (G) with two elements. Note that by this definition, the two verticesin an edge set cannot be the same vertex, and two edges cannot connect the same two41.2. Graph theory preliminariesvertices. Such graphs are sometimes called ?simple graphs,? as opposed to ?multigraphs.?Because we will only consider graphs of this definition, they will be simply referred to as?graphs.?A vertex v is incident with an edge e if v ? e. We denote an edge e by its vertices,or ends, say u and v, as e = {u, v}, or simply e = uv. A vertex u is a neighbor of, or isadjacent to, a vertex v if uv is an edge. The valency or degree of a vertex is the numberof edges incident to that vertex.A graph in which every vertex has the same valency is regular. It is k-regular if everyvertex has valency k.A graph in which every pair of vertices is connected by an edge is complete. It isdenoted by Kn if it has n vertices.G? is a subgraph of a graph G, if G? itself is a graph, V (G?) ? V (G) and E(G?) ? E(G),and this is denoted by G? ? G.If U ? V (G), the subgraph G? induced by U is the graph for which V (G?) = U ,and E(G?) contains an edge xy if and only if x, y ? U and xy ? E(G). This is denotedby G? = G[U ], and G? is called an induced subgraph of G. (For example, in Figure1.1, the vertices k, o, p, s, and the five thick edges, compose an induced subgraph; thevertices i,m, n, q, and the four thick dotted edges, compose a subgraph, but not an inducedsubgraph.) In particular, in a graph G, the subgraph induced by the set of neighbors of avertex v is called the neighborhood of v, and is denoted by GN (v).A path is an alternating sequence of vertices and edges, beginning with a vertex andending with a vertex, where each vertex is incident to both the edge that precedes it andthe edge that follows it in the sequence, and where the vertices that precede and follow anedge are the end vertices of that edge. The length of a path is the number of edges in thepath. (For example, in Figure 1.1, (a, ab, b, bf, f, fg, g) is a path with length 3, in which theedges are denoted by dotted lines, and is also one of several paths between a and g havingthe minimal distance.) The distance between two vertices is the length of shortest pathbetween them. In a graph G, the distance between vertices u, v is denoted by dG(u, v).51.3. The modelA graph is connected if any two vertices are linked by a path.The eccentricity \u000FG(v) of a vertex v in a graph G is the maximum distance from v toany other vertex, i.e.,\u000FG(v) = maxu?V (G)dG(v, u),where dG(v, u) is the distance between v and u in the graph G.The diameter diam(G) of a graph G is the maximum eccentricity over all vertices ina graph, and the radius rad(G) is the minimum,diam(G) = maxv?V (G)\u000FG(v), rad(G) = minv?V (G)\u000FG(v).When G is not connected, diam(G) and rad(G) are defined to be infinite. Some examplesof neighborhood subgraphs are shown in Figure 1.2. For every vertex in Figure 1.1, theneighborhood subgraph is Figure 1.2(a); for every vertex in Figure 1.4, the neighborhoodsubgraph is Figure 1.2(f). Figures 1.2(b)-1.2(e) are examples of neighborhood subgraphsthat appear commonly in the simulation.Given a lattice, the corresponding lattice graph is the graph whose vertices are thepoints in the lattice, and whose edges are the pairs of nearest points in the lattice. (Forexample, the whole graph in Figure 1.1 is an equilateral triangular lattice graph.)1.3 The modelTo gain intuition on the form of constraints and Hamiltonians that may induce mani-folds, let us construct some graphs resembling some manifolds, starting with the exampleof a flat two-dimensional plane R2. Intuitively, any two-dimensional lattice graph as de-fined above forms a ?two-dimensional? manifold, and a coordinate system of the manifoldnaturally inherits from the coordinates of the lattice graph. This is directly analogous toa Bravais lattice in crystallography. A priori there seems no decisive reason to choose anyparticular Bravais lattice as the preferred graph configuration; however, we shall choose theequilateral triangular lattice graph (Figure 1.1), using the following argument. On R2, forany point p and any distance ?, let B?(p) denote the geodesic ball centered at p with radius61.3. The model33333 3? = 0(a)3333 333? = 0(b)543 345? = 2(c)32232 2? = 1(d)33333 33? = 0(e)????? ?? =?(f)Figure 1.2: Some examples of neighborhood subgraphs. The eccentricity is labeled for eachvertex, and the difference of diameter and radius of these subgraphs, which is denoted by ?,is labeled below each graph. (a) is the neighborhood subgraph of vertices in the triangularlattice graph (Figure 1.1); (b), (c), (d) and (e) appear commonly in simulations, as partsof the defects; (f) is the neighborhood subgraph of vertices in the graph in Figure 1.4.71.3. The model?, and B?(p) ? p has the topology of a circle S1. For graphs, we can define the notion of?geodesic ball? similarly with that in Riemannian geometry. Let Bn(v) be the set of thevertices that have distance from vertex v no greater than n, including v itself. For anytwo-dimensional lattice, if we denote the corresponding graph by G, for sufficiently largen, the induced subgraph G[Bn(v)? v] also looks like S1 topologically. However, for n = 1,namely the neighborhood subgraph GN (v) = G[B1(v)? v], this property is no longer truefor all lattices. For example, on the square lattice, GN (v) is composed of 4 disconnectedvertices. Only for the equilateral triangular lattice, GN (v) looks topologically like S1. Thusin this sense, the equilateral triangular lattice graph is the closest analog to R2 among allthe two-dimensional lattice graphs, on all distance scales down to \u000F.A graph can form a two-dimensional lattice for the correct ratio of edges to vertices.While a thermalized lattice in two dimensions is isotropic [17?19], the connectivity of sucha lattice is still well-defined at low temperature. We thus choose to add defects in the formof extra edges or bonds, which will evolve under some Hamiltonian. This allows bondedvertices to be permuted, so that the low-temperature phase is still a ?quasi-fluid? thatretains a symmetry corresponding to randomized graph connectivities. The extra edgesinduce defects in the lattice, which may be mobile. The exact shape of the defects andthe reason why the defects are unstable or meta-stable depend sensitively on the Hamil-tonian. We shall construct a candidate Hamiltonian, and test the stability of the defectsby numerical simulation. This construction generalizes to Rn straightforwardly: We cansee that the defect-free lattice is the n-dimensional lattice as arising from a regular tilingof n-dimensional tetrahedra. The defect is a (n ? 1)-dimensional ?foam? that divides thespace into many patches of lattices with random orientations.We seek the simplest Hamiltonian that can give rise to manifold-like triangulation graphsas classical solutions, which contain defects that facilitate graph permutation symmetry.We assume that the action is local, in the sense that it should be a sum over the verticesand/or edges, such that each term involves a finite number of vertices and/or edges withinsome cutoff distance. This condition is imposed because almost all physics models for which81.3. The modelFigure 1.3: A neighborhood in the face-centered cubic lattice graph. This is the subgraphgenerated by a vertex in the lattice and all its neighbors.the Hamiltonian or Lagrangian is an integral of the corresponding density are local in thesame sense.A defect manifests itself as a local structure containing vertices with anomalous valency.One obvious local property of manifold-like graphs is that all vertices not in any defectswould have the same valency. Moreover it is likely that vertices in the defects have just onemore or one less neighbor. These properties can be enforced by a Hamiltonian quadraticin the valency:H1 = c1?v?V (G)n2v, (1.1)where nv is the valency of vertex v, and c1 is a positive constant (which will be taken to beinfinite as described below). The average valency of the vertices is given by? =2NENV(1.2)where NE is the total number of edges and NV the total number of vertices. Note that, forexample, ? = 6 is compatible with a regular equilateral triangular lattice, which in turnimplies that the emergent manifold is two dimensional, while ? = 12 is compatible withthe face-centered cubic lattice (see Figure 1.3), which implies a three-dimensional emergentmanifold. Thus without changing the form of the Hamiltonian, we should be able to findmanifolds with different dimensionalities by adopting different a priori values of ?. Inthe simulations described below, we choose ? to be a non-integer, so that there exists an91.3. The model?excess? number of edges, which contribute to the presence of defects. Because the totalnumber of vertices and edges are fixed, the term in (1.1) is minimized when every vertex hasvalency either b?c or d?e. In our simulations, c1 is taken to be infinite and so is no longeran adjustable parameter of the model, and the corresponding term in (1.1) is enforced tobe minimal.To obtain manifold-like solutions consisting of patches of close-packed lattices inter-spersed with defects, it is not sufficient to impose only the condition that each vertex hasapproximately the same number of neighbors. Many regular graphs do not look like anymanifold at all (see, for example, Figure 1.4). Additional terms in the Hamiltonian are thusrequired for manifold-like solutions.One candidate for such a term consists of particular subgraphs that can be embeddedinto the graph. From this viewpoint, nv is the number of K2 subgraphs (two vertices con-nected by an edge) that go through the vertex v. It is likely however that choosing moreterms of this type will affect the dimensionality of the resulting spacetime. For example,if we incorporate terms that favor more K3 subgraphs (triangles) and fewer K4 subgraphs(tetrahedra), then it can be expected that these terms would favor two-dimensional mani-folds [16]. As we hope to find a model that does not select the dimensionality at the levelof the Hamiltonian, we will not use any other term of this type besides H1.Another property of manifold-like graphs is that around most vertices, the graph has alocal discrete rotational symmetry that reflects the local isotropy of the emergent manifold.This can be restated as for each vertex v, the subgraphs G[Bn(v) ? v] for most v shouldhave a discrete rotational symmetry. To reduce the number of possible Hamiltonian terms,we impose this condition only on G[B1(v)?v], which is also GN (v). We introduce the termH2 = c2?v?V (G)?(v), (1.3)where c2 is a positive constant, and?(v) = diam(GN (v))? rad(GN (v)), (1.4)in which diam(GN (v)) is the diameter of the subgraph GN (v), and rad(GN (v)) is the101.3. The modelFigure 1.4: A 6-regular graph that is not similar to any manifold. This graph can beviewed as an infinite rooted ?tree? graph, in which each node has three children (exceptthe root node has four children), and every node of the ?tree? is actually a tetrahedron.radius of the subgraph GN (v). By the definitions of diameter and radius of graphs, if thesubgraph GN (v) is not connected, they are both infinite. Here, we additionally define thattheir difference diam(GN (v)) ? rad(GN (v)) is also infinite when GN (v) is not connected.The term H2 then enforces that all neighborhood subgraphs are always connected. WhenGN (v) is connected, the difference between its diameter and its radius is a measure of itsasymmetry. Figure 1.2 shows several examples of neighborhood subgraphs. The eccentricityof every vertex in the subgraphs is labeled, along with the value of ?(v) for each subgraph.For Figures 1.2(a) and (b), theGN (v)?s have a rotation symmetry of D6 and D7, respectively,while Figures 1.2(c)-(e) are not rotationally symmetric.In two dimensions, a graph forms a triangulation of a surface if and only if all theneighborhood subgraphs are cycles [20]. When the degrees of the subgraphs are either 6or 7, which is imposed by the H1 term, one can see from the examples in Figure 1.2 thatthe H2 term indeed favors cyclic neighborhood subgraphs, with only one exception shownin Figure 1.2(e). We thus expect that, in this model, a graph with low energy is almost atriangulation of a surface.Because metrics in General Relativity are covariant, the coordinates of a spacetime pointhave no absolute meaning. Analogously, in the graph model, the labeling of vertices should111.3. The modelalso be irrelevant, and isomorphic configurations with different labeling should be consideredthe same. The numerical implementation of the graph model described in the next sectioncontains a labeling of vertices. The relation between labeled graphs and unlabeled graphsis the following. Given an unlabeled graph, there are NV ! ways to label it. However, if thisunlabeled graph has some symmetry, some of the labeled graphs can still be isomorphicwhen the labels are considered. For example, consider the line graph with three vertices.The labeled graph 1-2-3 is different from the labeled graph 1-3-2, but it is still isomorphicto the labeled graph 3-2-1: Due to the two-fold reflection symmetry of the line graph,graphs 1-2-3 and 3-2-1 have the same edge-set. Thus for a given labeled graph G, itscontribution to the partition function should be re-weighted by the factor S(G)/NV !, whereS(G) is the symmetry factor of the unlabeled graph corresponding to G. (For the linegraph with three vertices, S(G) = 2 for configurations 1-2-3 and 3-2-1.) The factor NV !can be ignored because it is the same for all samples in a simulation, while the factor S(G)depends on the graph G, and could in principle be calculated. However, calculating S(G)is a computationally difficult problem. We choose to ignore this factor in the numericalsimulations, and expect to find qualitatively the same result as the more realistic modelwith unlabeled vertices. A systematic calculation of S(G) is an interesting topic for futurework.Thus we propose the following model: Consider a simple graph with NV vertices andNE edges. The vertices are labeled, while the edges are not labeled. The Hamiltonian iscomposed of two terms, as motivated previously:H = H1 +H2. (1.5)Because the Hamiltonian is prohibitive to analytical solution, we implement a numericalsimulation, as described in the next section, to study the equilibrium states of this modelin the canonical ensemble, i.e. at a given temperature. In particular, we will be interestedin the structures of the states with low energies, and the nature of the phase transition, ifone exists, to these low-energy states.121.4. Numerical simulationuv uv?Figure 1.5: An example of the Monte Carlo trial moves. The blue edge can from uv to uv?or vice versa in a trial move.1.4 Numerical simulationWe sample equilibrium states in the model using a Monte Carlo simulation [21]. Theparameter ? defined in (1.2) as giving the mean number of edges per vertex is taken to beslightly larger than 6, which we expect will induce two-dimensional structures dictated bytriangulations as described above. There is no fixed boundary on the graphs. The size ofthe graphs is specified by the number of vertices NV , and the number of edges NE . Forconvenience, in the following we use NV and the number of extra edges X ? NE ? 3NV ,to specify the size of the graphs. Given the graph size, the initial configuration is taken tobe a randomly generated, connected graph.The graph is evolved in the canonical ensemble with temperature 1/?. In each MonteCarlo step, one end of an edge can jump from one vertex to another. We randomly pick anedge, and randomly label its ends by u and v. To find the new location of the edge uv, weperform a random walk starting from v as the origin, which does not pass through the edgeuv (this condition guarantees that a connected graph remains connected after such a move).The number of steps ` of the walk is a random positive integer chosen from the probabilitydistribution P (`) = ?`?1 ? ?`, where ? is a parameter between 0 and 1 (we take ? = 0.5below). Denote the ending vertex of the random walk as v?. The edge is then moved fromuv to uv?. See Figure 1.5 for a schematic example of possible Monte Carlo trial moves. If thenew graph is still simple, its energy is compared with that of the old graph, and this move131.4. Numerical simulationis accepted or rejected according to the Metropolis algorithm [21]. See Appendix 1.8 for thealgorithm used in calculating the radius and diameter of the neighborhood subgraphs. Each?sweep? through the system contains NE Monte Carlo steps, so on average each edge hasone chance to jump in one sweep. Such a method is ergodic; moreover with this jumpingscheme, the energy of only a few vertices is affected after each Monte Carlo step, and theenergy of only these vertices needs to be updated.Simulations are performed with c1 = ?, c2 = 1.0, ? = 0.5, and various values of NV ,X and ?. Before showing the thermodynamics results from the simulations, let us firstdescribe the method that we used to render a graph from the simulations, in order tointerpret its evolution.1.4.1 Rendering graphsTo render a graph such that its structure can be best visualized, we need to devise anappropriate drawing scheme. A drawing of a graph maps vertices to points in Rn with linesegments connecting adjacent points. The following method is used to generate drawingsin R3. For any drawing of a graph G, we seek to minimize the functionHdraw =?e?E(G)(a1l2e +a2l2e)+?i,j?V (G), i 6=j,i,j not adjacenta3l2ij, (1.6)where le is the length of the drawing of edge e, lij is the distance of the drawing betweenvertices i, j, and a1 = 1.0, a2 = 1.0, a3 = 5.0. The first term gives a preferred length forevery edge, and the second term gives a repelling force to every non-adjacent pair of vertices.The function Hdraw is chosen this way in order to make every edge have approximately thesame length in the drawing, and as well, to make the drawing as expanded as possible. Inpractice, even for moderate-sized graphs, Hdraw has numerous local minima and is difficultto minimize. We thus use another Monte Carlo calculation to search for its near-optimalvalues. Initially, all the vertices are located at the origin of R3. In each Monte Carlostep, a randomly-chosen vertex is randomly moved to another position within the ballof radius ? = 2.5, centered at the original position, and the new position has uniform141.4. Numerical simulationprobability distribution within the ball. After the Monte Carlo calculation, because thelow-temperature configurations in the model are conjectured to be similar to triangulationsof surfaces, we also search for all the K3 subgraphs (triangles) in the graph, and render(flat, solid) triangles to fill the interior of the K3?s.Figure 1.6 shows some snapshots taken from the simulations. Figures 1.6(a)-(c) are forthe system of size NV = 200 and X = 20. Figure 1.6(a) shows the initial configuration,1.6(b) shows a typical configuration at high temperature (? = 1.0), and 1.6(c) shows atypical configuration at low temperature (? = 2.0). Figure 1.6(d) is for the system of sizeNV = 1000 and X = 100, and it is a typical configuration at low temperature (? = 2.0).In the sample drawings in Figure 1.6, different colors are used to denote different typesof vertices. The color-code is as follows:Degree= 6 Degree= 7Zero contribution to H2 black greenNonzero contribution to H2 red blueAlso, yellow lines are drawn at places where two triangles intersect, i.e., this identifies wherethe triangulated surface intersects with itself.1.4.2 Topology of the manifold in the presence of defectsFor the low-temperature graphs, several examples of common local defects are shownin Figure 1.7. They are called local in the sense that in the vicinities of these defects,the graph is similar to some triangulation of surfaces with trivial topology. Among theseexamples, the ?bubble-wrap? defects (a)-(c) do not increase the total energy, and aroundsuch defects the ratio between the number of edges and vertices is larger than 3. In otherwords, these defects can ?absorb? the extra edges without energy cost. Also note that (a)and (b) do not change the long range order of the lattice orientation, while (c) does alterthe long range order. Taken together, these defects induce configurational degeneracies inall the energy levels, including the ground state energy level, and at the same time inducegraph permutation symmetry by randomly breaking the lattice?s long range order, at least151.4. Numerical simulationFigure 1.6: Some snapshots from the simulations, drawn in three dimensions. Panels (a)-(c)are for the system with number of vertices NV = 200 and number of extra edges X = 20,where (a) is the initial configuration, (b) is a typical configuration at high temperature(? = 1.0), and (c) is a typical configuration at low temperature (? = 2.0). Compared withthe sphere, the drawing (c) has three more handles, and the surface intersects with itselfin three places, so it has a non-trivial, non-orientable topology. Panel (d) is for the systemof size NV = 1000 and X = 100, and shows a typical configuration at low temperature(? = 2.0). In these drawings, if a vertex has valency 6, it is black if its ? value is zero, andis red if its ? value is nonzero; if a vertex has valency 7, it is green if its ? value is zero,and is blue if its ? value is nonzero (see text). As well, yellow lines are drawn at placeswhere two triangles intersect, and the manifold thus passes through itself.161.4. Numerical simulationFigure 1.7: Examples of some common defects. Once the graph is triangulated to constructa surface, defects (a-d) have ?bubble-wrap? morphology, while defect (e) has ?frenulum?morphology. The figures in the first row are the schematic drawing of the defects, in whicha vertex is marked with a square if its valency is 7, a vertex is marked with an open circleif it contributes positive energy to H2, and otherwise a vertex is marked with a filled circle.The figures in the second row are the corresponding drawings of the defects using themethod described in subsection 1.4.1. Compared with the equilateral triangular lattice,examples (a), (b), (c), (d) and (e) have 2, 3, 2, 0, 0 extra edges, respectively.171.4. Numerical simulationin the rendering scheme of the manifold described above. The bubble wrap defect (d)and ?frenulum? defect (e) increase the total energy, and alter the lattice orientation moredrastically.As discussed above, low-temperature graphs in the model are similar to two-dimensionaltriangulated surfaces. However, they contain local defects, and there are overall topologicalfeatures of the surfaces that emerge from the graphs. For example, in the drawing Figure1.6(c), one can see that the emergent surface contains several handles, and the surfaceintersects itself in several places. In the drawing Figure 1.6(d), the topology of the emergentsurface is too intricate to easily identify. The Hamiltonian does not constrain the topologyin any way, so in general, emergent surfaces of low-temperature graphs in the model havecomplicated topologies. The emergent surfaces have potentially many handles, and are ingeneral non-orientable, in that there is no separation between interior and exterior sides ofthe surface. In our simulations, we also observe that the topology of the graphs? emergentsurfaces can dynamically change, even at a low energy.We note, however, that the choice of NV and NE can constrain the topology. At lowtemperatures, the graphs are nearly triangulations, albeit with potentially complicatedtopologies. If a graph is strictly a triangulation, and we denote the number of triangles asNF , then the Euler characteristic ? of the surface is given by ? = NV ? NE + NF . Fora triangulation, 3NF = 2NE ; and we previously defined NE = 3NV + X. Putting thesethree equations together, we find ? = ?X/3. As we showed above, defects on the graphscan absorb edges, so the relation for the nearly-triangulated graphs becomes an inequality? ? ?X/3. In addition, for any surface, ? ? 2, with ? = 2 corresponding to the topologyof a sphere. Thus the Euler characteristic ? of the emergent surface can take any integervalue between ?X/3 and 2. The X values used in our simulations are not very small, sothis constraint still allows for many possible different topologies for the emergent surface.181.4. Numerical simulation1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 200.20.40.60.811.21.41.61.8??E?/N V NV=100 NV=200 NV=300 NV=500 NV=1000 NV=1500 NV=2000Figure 1.8: The average energy density ?E? /NV as a function of inverse temperature ? forfor several NV ?s indicated in the legend.1.4.3 Phase transitionIn this sub-section we study the transition between the low-/high- temperature phases.For system sizes NV = 100, 200, 300, 500, 1000, 1500, 2000, and number of excess edges X =0.1NV , the expectation value of energy ?E?, and the heat capacity C = ?2(?E2? ? ?E?2)arecomputed for various inverse temperatures ?, where the angle bracket here means averagingover all the samples in a simulation.The results are shown in Figure 1.8 and Figure 1.9. For the three largest systems withNV = 1000, NV = 1500, and NV = 2000, we also employ the weighted histogram analysismethod (WHAM)? [22] to improve the sampling quality. The inverse transition tempera-ture ?c is defined as the inverse temperature where the heat capacity is maximal. It can beseen that ?c increases as NV increases, an effect also seen previously in other graph mod-?See Appendix 1.7 for the details of our implementation of WHAM.191.4. Numerical simulation1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 200.10.20.30.40.50.60.70.80.91?C/N2 V NV=100 NV=200 NV=300 NV=500 NV=1000 NV=1500 NV=2000Figure 1.9: The rescaled heat capacity C/N2V = ?2(?E2?? ?E?2)/N2V as a function ofinverse temperature ? for several NV ?s indicated in the legend.101 102 103 1041.21.31.41.51.61.71.8NV? cln?c = 0.0804 lnNV ? 0.122Figure 1.10: Log-log plot of the inverse transition temperature ?c in the model as a functionof system size NV , and the best fit line. The straight line fit indicates that as NV ? ?,the transition temperature Tc ? 0.201.4. Numerical simulation0 0.5 1 1.500.511.522.533.544.55E/NVp(E/NV) NV=1000 NV=1500 NV=2000Figure 1.11: The probability density of the intensive energy E/NV for the systems of sizeNV = 1000, 1500 and 2000, at each system?s transition temperature. The error of p(E/NV )for E/NV ? 0.5 is small (?p ? 0.1), the error for 0.01 < E/NV < 0.5 is ?p ? 0.6, and theerror for the smallest values of energy E/NV ? 0.01 is ?p ? 2.5.211.4. Numerical simulation1 1.2 1.4 1.6 1.8 210?410?310?210?1?acceptance ratioFigure 1.12: For the system of size NV = 1000, the acceptance ratio of Monte Carlo movesin the simulations as a function of inverse temperature ?.els [13, 16] Near the transition temperature ?c, |d ?E? /d?| also increases as NV increases,and thus the widths of the heat capacity peaks decrease as NV increases, indicating thetransition becomes more cooperative. Figure 1.10 shows a log-log plot of the inverse tran-sition temperature as a function of NV . The linear relation in the plot indicates that asNV goes to infinity, the transition temperature would go to zero. In addition, Figure 1.11shows the probability density distribution of E/NV , for the systems of size NV = 1000,1500, and 2000, at each system?s transition temperature. As NV increases, the energydistribution of the two phases become more bimodal, and the temperature-dependence ofthe heat capacity in Figure 1.8 becomes sharper, indicating a more cooperative transitionwith increasing system size [23, 24]. Together this implies that the transition is first orderin the bulk limit, with a corresponding nucleation barrier [25]. That is, a Landau func-tional using system energy as an effective order parameter has a double-well structure withcorresponding barrier separating the low- and high-energy phases [26].The acceptance ratio as a function of ? for NV = 1000 is plotted in Figure 1.12. Thelow energy phase occupied at large values of ? has a much lower acceptance ratio than221.4. Numerical simulationthe high energy phase, both because of the lower temperature and because the low energygraphs have much more structural constraints, and thus have more rigidity with respectto the local moves. However, because some the local defects cost little or no energy, lowenergy graphs still have non-zero acceptance ratio, and so are able to undergo dynamicsduring the simulations.A transition temperature of zero for infinitely large graphs is actually not very surpris-ing on entropic grounds. Consider a first order phase transition of an extended physicsmodel. Denote the size of the system by N , and denote the number of states in the high-and low-temperature phases by ?H and ?L, respectively. Because the energy difference be-tween these two phases is proportional to N , the phase transition temperature Tc is givenapproximately by ?He??N/Tc = ?L, where ? is a positive number. As N increases, fora ?typical? physics system with short-ranged interactions, the ratio between ?H and ?Lincreases as e?N , where ? is a positive number. This behavior results in a finite, non-zerotransition temperature in the infinite size limit. On the other hand, the number of inequiv-alent graphs with NV vertices is typically N??NVV , (see, e.g., [3,13,27], also see Appendix 1.9for more examples) where ?? is a positive number that depends on the constraints of theallowed graphs. In our case, the allowed graphs should have every vertex valency equal tosix or seven, and every vertex neighborhood should be connected. While we do not have analgorithm to count the exact number of allowed graphs, it is reasonable to assume for oursystem that the ratio between ?H and ?L has the typical asymptotic behavior of graphs,which explains a transition temperature of zero, i.e., the transition temperature Tc is givenby N??NVV e??NV /Tc ? 1.To validate the above argument, we can calculate the entropy difference across thetransition as given by?S =? T1T2C(T )TdT =? ?2?1C(?)?d?, (1.7)where C is the heat capacity, and ?1 and ?2 are typical inverse temperatures in the high-temperature phase and low-temperature phase, respectively, which are taken to be ?1 =?c ? 100/NV , ?2 = ?c + 100/NV , i.e., we ensure that the window defining the transition231.4. Numerical simulation101 102 103 1041.91.9522.052.12.152.22.25?S/NV = 0.066 lnNV +1.7NV?S/N V0 100 200 3000.911.11.21.3NV?S/NVFigure 1.13: The entropy density difference across the transition ?S/NV as a function ofNV . The best fit line using a logarithmic function is also shown. The inset shows ?S/NVas a function of NV for a model including a Coulomb potential between valency-7 vertices(see section 1.5). Including long-range interactions can remove super-extensivity of theentropy.241.4. Numerical simulation1 1.2 1.4 1.6 1.8 20500100015002000250030003500?number of edges with a certain Ve Ve=1 Ve=2 Ve=3 Ve=4 Ve=5Figure 1.14: Distribution of edge valencies as a function of inverse temperature ?c, for thesystem of size NV = 1000. There are no edges in the simulation with edge valency lessthan one or larger than five.narrows as the width of the heat capacity peak narrows. Fig 1.13 shows the difference inentropy density ?S/NV as a function of NV , which, rather than remaining constant, is amonotonically increasing function. Thus the entropy of the system is super-extensive. Ifthe ratio ?H/?L of the model scales like N??NVV as argued above, ?S/NV will have theform ?S/NV = ?? lnNV + b. The best fit line using this logarithmic function is also shownin Fig 1.13, which is consistent with a super-extensive entropy, with ?? ' 0.065.1.4.4 Geometric propertiesIn this sub-section, we analyze some geometric properties of the two phases: if a geo-metric property is distinct in the two phases, it can serve as an order parameter that signalsthe phase transition.As was mentioned before, because the low-energy graphs are nearly triangulations forour Hamiltonian, it is useful to introduce an order parameter that measures how similargraphs are to triangulations. For this purpose we can study the distribution of edge valen-251.4. Numerical simulation1 1.2 1.4 1.6 1.8 25.566.577.588.5?averagedistance?d??Figure 1.15: Average distance?d??between pairs of vertices, plotted as a function of inversetemperature ?, for the system of size NV = 1000.?d??is first averaged over all pairs ofvertices in a given snapshot, and then averaged over all snapshots at a given temperature.The vertical bars at each data point indicate the standard deviation between snapshots:??d?2???d??2.cies, where the edge valency is defined as the number of triangles that an edge is part of.In a perfect triangulation of a surface without boundaries, the edge valencies are alwaystwo, so we expect that at low temperatures, the distribution of edge valency should ap-proximate a delta function around two. The distribution of edge valencies for the systemof size NV = 1000, X = 100 is shown in Figure 1.14 as a function of temperature. Indeed,almost all edges have edge valency two at temperatures below the transition temperature.Near the transition temperature however, there is a sudden change in the distribution ofedge valencies: above the transition temperature, edge valencies both above and less thantwo appear.Another quantity that is useful as an order parameter is the average distance between allpairs of vertices, denoted by?d??, where the bar means averaging over all pairs of vertices ina graph, and the angle bracket means averaging over samples of an equilibrium simulation.261.4. Numerical simulationWe expect that above the phase transition temperature, graphs will exhibit ?small world?topologies and thus?d??will be relativity small. The quantity?d??gives the characteristiclinear size of the graphs. Figure 1.15 plots?d??vs. inverse temperature ?, for NV =1000. Indeed, the low-temperature phase has a larger?d??than the high-temperature phase;low-temperature graphs tend to have much more structure than high-temperature graphs,resulting in larger values of?d??.In Figure 1.16, the average distance?d??is shown as a function of the system size NV , at? = 1.0 (above the transition) and at ? = 2.0 (below the transition). The best fit lines usinga logarithmic function and using a power function are also shown in Figure 1.16. The p-valuefor each best fit line is calculated for the null hypothesis that the residues (dfit??d??)/?d comefrom a normal distribution with variance smaller than 1, so that a higher p-value indicatesa better model. These relations between?d??and NV can be understood by comparing withrandom graphs, which generally display ?small-world? connectivity, with average distancesgrowing logarithmically with the number of vertices [3]. In our model, the Hamiltonianonly constrains the graphs locally, so these graphs satisfy small-world behavior in the hightemperature phase accurately, as shown by the logarithmic best fit line in Figure 1.16(a).For the low temperature phase, we can define an effective scaling dimension (see, e.g., [28])Ds =d lnNVd ln?d?? . (1.8)On a non-fractal surface,?d??? N1/2v , i.e., Ds = 2. However, it is seen from Figure 1.16(b)that the residuals with the square root function are too large. If we take Ds as a parameterin the fitting, a power-law function with Ds ' 3.5 is a much better fit to the empiricalscaling. Perhaps surprisingly however, the logarithmic function is still the best fit function,indicating that the low-temperature graphs still display small-world connectivity. Enforc-ing a power-law fit at every system size, i.e.,?d??? N1/Ds(Nv)v , would induce a variabledimensionality in the exponent.Another related definition of dimensionality measures the increase in number of verticeswith distance from a given vertex. On a graph, one can pick an arbitrary central vertex,271.4. Numerical simulation0 500 1000 1500 2000 250012345678NV?d??? = 1.0?d??1/2 = 0.16N 1/2V , p = 0?d??power = 1.72N 1/5.7V , p = 0.013?d??ln = 0.978 lnNV ? 0.87, p = 0.996(a)0 500 1000 1500 2000 2500024681012NV?d??? = 2.0?d??1/2 = 0.23N 1/2V , p = 0?d??power = 1.07N 1/3.5V , p = 0.0045?d??ln = 1.99 lnNV ? 5.6, p = 0.605(b)Figure 1.16: The average distance?d??between pairs of vertices as a function of the systemsize NV (discrete points), and the best fit lines using a square root function (green dashedlines), using a power function (red solid lines), and using a logarithmic function (blacksolid lines). Plots are shown both above the transition (? = 1.0) in panel (a), and belowthe transition (? = 2.0) in panel (b). For each best fit line, its expression and p-valueare also shown, where the p-values are calculated for the null hypothesis that the residues(dfit ??d??)/?d come from a normal distribution with variance smaller than 1. For bothtemperatures, the logarithmic function gives the best fit to the measured data.281.4. Numerical simulation100 101100101102103104r?N?r? ?=1.0?=2.0100 101012345rDfFigure 1.17: Log-log plot of?N?r?, the thermally averaged number of vertices within adistance r, as a function of r; the slope gives the dimensionality of the system, which inthis case is distance-dependent. The plot shown is for the system with size NV = 2000, at? = 1.0 (blue line) and at ? = 2.0 (red line), which bracket the transition. For the samesystem, the inset shows the fractal dimension as a function of r.291.4. Numerical simulationand count how many vertices Nr have distance no greater than r from that center. Wecan then average both over all central vertices and over all equilibrium configurations at agiven temperature, denoting the doubly averaged volume by?N?r?. If?N?r?increases withr polynomially, the fractal (Haussdorf) dimension can be defined asDf =d ln?N?r?d ln r. (1.9)In practice the dimension of the graph may itself depend on the radius r, so it makes senseto talk rigorously about the dimensionality of a graph only if Df is essentially constantover some range of r. A log-log plot of?N?r?vs. r is shown in Figure 1.17, for NV = 2000at ? = 1.0 and ? = 2.0, where the slope thus gives the dimensionality and is shown inthe inset. One can see that the effective dimension Df is smaller below the transition.Consistent with the previous analysis using (1.8), there is no well-defined dimension forthe graphs, which are small-world-like. Instead there is an increasing dimensionality withincreasing length scale, until boundary effects of the system are felt. The dimensionalityhas values around 2 for small values of r, because of the local lattice-like structure; it is alsosmall for very large values of r, because a finite-sized graph must eventually be bounded,at which point?N?r?will no longer increase polynomially at large r. Table 1.1 lists themaximal value of Df (r) for systems with different sizes, at inverse temperatures ? = 1.0and ? = 2.0. As the table shows, Df,max increases with NV , which indicates that as NVincreases, there is no universal fractal dimensionality that can be approached by the graphs.Instead, the graphs are still small-world.The small-worldness of the low temperature graphs in the bulk limit can be viewedas a consequence of the graph Hamiltonian in (1.5), which is a sum of local terms. Thedefects in the manifold are also local ? in the bulk these have no effect on the large-scalestructure of the resulting graphs. This is manifested for finite-size graphs by the fact thatas NV increases, the topologies of graphs become progressively more complicated, see e.g.Figure 1.6(c) and Figure 1.6(d). The manifolds contain numerous handles and surfaceintersections, so that a planar dimensionality does not adequately describe the system. Inthis sense there is already the signature in the low-temperature phase of the finite system301.4. Numerical simulation? = 1.0 ? = 2.0NV = 1000 3.62 2.72NV = 1500 3.99 3.11NV = 2000 4.26 3.20Table 1.1: The maximal value of the fractal dimension Df as defined in (1.9) for systemswith NV = 1000, NV = 1500 and NV = 2000, at inverse temperatures ? = 1.0 above thetransition and ? = 2.0 below the transition.that the bulk system is always disordered.1.4.5 Correlation functionsDefects in this model such as those shown in Figure 1.7 contain irregularities that makethem differ from part of a regular lattice. However, regions far away from them may notbe affected by their existence; i.e., there may be no long-range correlation between suchdefects. In this subsection, we define and calculate correlation functions between defectpairs.Because valency-7 vertices induce defects, we first measure the radial correlation func-tion of valency-7 vertices. In general, the correlation between two random variables X,Ywith expected values ?X , ?Y and standard deviations ?X , ?Y is defined ascorr(X,Y ) =E[(X ? ?X)(Y ? ?Y )]?X?Y, (1.10)where E is the expectation value operator. In our case, we take all pairs of vertices withdistance d in a graph; X is 1 if the first vertex in a pair has valency 7, and 0 otherwise, andY is defined similarly for the second vertex. Then the correlation function is averaged overall equilibrium samples. The result for NV = 2000, taken at inverse temperatures ? = 1.62and ? = 1.65, which are marginally below and above ?c respectively, is shown in Figure1.18(a). When the distance d is very small (d = 1 or 2), the correlation function deviatesfrom zero, because of the local structure of of the defects (see Figure 1.7), which in this case311.4. Numerical simulation0 5 10 15 20?0.1?0.08?0.06?0.04?0.0200.02dradial correlation of valency?7 vertices (a)?=1.62?=1.650 5 10 15 20 25?1?0.8?0.6?0.4?0.200.20.4dradial correlation of valency?3 edges (b)?=1.62?=1.65Figure 1.18: Radial correlation function defined through (1.10) of (a) valency-7 verticesand (b) valency-3 edges. Correlations are calculated for the system with size NV = 2000at ? = 1.62, which is in the high-temperature phase, and at ? = 1.65, which is the low-temperature phase.321.4. Numerical simulationinduces anti-correlation. For intermediate values of d (3 ? d ? 10), the correlation is verysmall, indicating the defects are uncoupled. However, for large values of d, the correlationfunction becomes negative. This is because the valency of a vertex, and the distance fromthis vertex to other vertices, are not independent: compared with the valency-6 vertices,the valency-7 vertices tend to have smaller distances to other vertices. For example, forNV = 2000, ? = 1.62, the mean distance to valency 6 vertices is 7.18, while the meandistance to valency 7 vertices is 7.04. Thus it is less probable to find two valency-7 verticeswith a large distance, and hence they anti-correlate at large distances. The correlationfunction is quite small over a range of d as one might anticipate, but the above global effectmakes it difficult to quantitatively confirm that defects are decoupled at large distance.As another measure of the correlation between defects, we can measure the radial cor-relation function of valency-3 edges, since their existence indicates deviation of the graphfrom a triangulation of surface. For example, every defect in Figure 1.7 contains valency-3edges. The distance between two edges is defined by taking the 4 vertices defining the twoedges, and finding the pair of vertices with the minimum distance between them. Since apair of edges having a common vertex would then have a distance of zero, we add one tothe above definition of edge distance. The results for NV = 2000, at ? = 1.62 and ? = 1.65,are shown in Figure 1.18(b). At small distances (d ? 3), there exists short range positivecorrelation between the valency-3 edges ? the mean force between them is attractive, dueagain to the particular structure within a given low energy local defect. At large distances(d ? 14 for ? = 1.62, d ? 17 for ? = 1.65), the correlation function becomes negative,because valency-3 edges correlate with valency-7 vertices, which in turn anti-correlate atlarge distances for the reasons described above. However for a wide range of intermedi-ate distances, this correlation function is also nearly zero, indicating again that the defectattraction is short-ranged.331.5. Addition of a Coulomb potential1.5 Addition of a Coulomb potentialWe found above that as the graph size NV increased to infinity, the transition temper-ature Tc approached zero (Figure 1.10). This is apparently a universal property of modelsbased on graphs, due to the super-extensive entropy of the high-temperature random phase.Similar arguments appear in the theory of phase transitions of low dimensional systems [29],wherein the non-extensive energy cost of defect formation is outweighed at any non-zerotemperature by the (extensive) free energy due to translational entropic gain, so long asinteractions are sufficiently short-ranged. This analogy motivated us to introduce a modelwith long-ranged interactions between defects, anticipating that in such a defect-filled sys-tem incurs super-extensive energetic cost, which may in turn result in a non-zero transitiontemperature.Thus, in addition to the original two terms in the Hamiltonian (1.5), we introduce anonlocal Coulomb potential term to the Hamiltonian, which gives a repulsive force betweenany pair of degree-7 vertices,H3 = c3?v,u?V (G),v 6=u?nv ,7?nu,7d(v, u). (1.11)This is one of the simplest non-local Hamiltonian terms that one can add to the originalHamiltonian. The Coulomb force is chosen to be repulsive, because most of the high-temperature states are ?small world?, in that they have smaller average distances thanthose of low temperature states, so such a Coulomb potential can suppress the appearanceof these ?small world? graphs.We test the effect of addition of this Coulomb term by another set of simulations, inwhich c3 = 1.0. Figure 1.19 shows the sample drawings of graphs withNV = 200, X = 20 (a)at high temperature (? = 1.0) and (b) at low temperature (? = 2.0). These temperaturesbracket the heat capacity peak for the system so that the system is in the disordered andordered phases respectively (Fig. 1.20). Because of the non-locality of H3, simulations aremuch slower in practice than before and smaller systems are thus employed: simulationsare performed for NV = 80, 100, 120, 150, 200 and 250, and X = 0.1NV . The inset of341.5. Addition of a Coulomb potentialFigure 1.19: Sample configurations for the model with Coulomb potential in (1.11) withc3 = 1.0, for the system with number of vertices NV = 200 and number of extra edgesX = 20, drawn in three dimensions. Panel (a) shows a typical configuration in the high-temperature phase with ? = 1.0; panel (b) shows a typical configuration in the low-temperature phase with ? = 2.0.351.5. Addition of a Coulomb potential50 100 150 200 250 3001.21.251.31.351.41.45NV? c 1 1.2 1.4 1.6 1.8 202468?C/NV NV=80 NV=100 NV=120 NV=150 NV=200 NV=250Figure 1.20: Log-log plot of transition temperatures ?c as a function of system size NV ,for the model with local Hamiltonian in (1.5) (drawn as circles, with best fit drawn as solidline), and for the model with Coulomb potential in (1.11) with c3 = 1.0 added to the localHamiltonian (discrete points with error bars). The inset shows the rescaled heat capacityC/NV as a function of inverse temperature ? for systems with the Coulomb potentialadded, and from which the values and uncertainties of ?c values are determined.361.5. Addition of a Coulomb potentialFigure 1.20 shows the rescaled heat capacity C/NV as a function of ?, for several systemsizes. The rescaling factor is now chosen differently than in Figure 1.9, because the systemswith the Coulomb potential have maximal heat capacity approximately proportional toNV . From the maximal heat capacity, the inverse transition temperature ?c is determined,and is shown in Figure 1.20 (main panel), in comparison with the ?c values without theCoulomb potential.From the graph drawings in Figure 1.19, we can see that because of the repulsiveCoulomb force, both the high-temperature and low-temperature manifold configurationsbecome rather extended to achieve longer average distances between defects. The charac-teristic linear size of the systems is much larger when the repulsive Coulomb potential ispresent, which penalizes the increase in complexity that was observed for a local Hamil-tonian as NV increased. This may also explain why the transition temperature does notchange very much with NV : The order of a neighborhood of a graph is not affected by aregion far away from this neighborhood, regardless of whether or not the Coulomb potentialis included. We can take this neighborhood to be a geodesic ball of radius r. For the modelwithout the Coulomb potential, near the transition temperature, the fractal dimension (1.9)increases with NV , which indicates that within a geodesic ball of radius r, the entropy ofthe disordered phase increases with NV faster than that of the ordered phase, resultingin a decreasing transition temperature as NV increases. For the model with the Coulombpotential, for graphs of size up to NV = 250, the fractal dimension is nearly one, (seeFigure 1.19,) so the entropies of both the disordered phase and the ordered phase within ageodesic ball of radius r remain nearly constant as NV increases. This results in a nearlyconstant transition temperature.We thus suspect that the entropy would be approximately extensive for the long-rangedinteraction model. To quantify this, as a final check we plot the entropy change betweendisordered and ordered phases as a function of NV in the inset of Figure 1.13, where ?S iscalculated by Equation (1.7), and ?1 = 1.0, ?2 = 2.0. As opposed to the entropy differencein the original model, ?S/NV of this model is approximately constant as NV increases, i.e.371.6. Discussionthe entropy difference is no longer super-extensive, rather it is extensive or sub-extensive. Itshould be noted that the approximate extensivity of ?S is a phenomenological result fromthe numerical simulations with limited graph sizes. We find no reason that the ?S willcontinue to be extensive as NV increases further. As indicated by the inset of Figure 1.13,?S may become sub-extensive when NV increases beyond 250, which is the largest sizethat we have simulated. It is a subtle problem to find the appropriate form of the non-localinteraction in the Hamiltonian that yields a model of graphs with finite, nonzero transitiontemperature in the large NV limit.We also simulate the model with an attractive Coulomb potential, in which c3 = ?1.0.Figure 1.21 shows sample drawings of graphs with NV = 200, X = 20 (a) at high tempera-ture (? = 1.0) and (b) at low temperature (? = 2.0). The effect of the attractive potentialcan be observed in these samples, in that the valency-7 vertices (green and blue dots) areusually located close together. In addition, because a local move must involve a valency-7vertex, the configuration cannot evolve in the regions composed of purely valency-6 ver-tices, and thus the simulation is inefficient. As can be seen in Figure 1.21(b), in the regionof valency-6 vertices, the configuration does not minimize the Hamiltonian (red dots havepositive contribution to H2), and is not a triangulation. Thus Figure 1.21(b) depicts along-lived meta-stable state on an energy landscape of states characteristic of a frustratedsystem [23, 24]. Such a model has numerous local minima with large reconfigurationalbarriers between them, and consequently glassy relaxation dynamics.1.6 DiscussionIn this chapter we have constructed a graph model with a local Hamiltonian that simplyenforces minimal valency subject to a given total number of graph links, along with a graphsymmetry between the local graph radius and diameter. The above minimal conditionalong with fixed total link number gives rise to near constant valency for all vertices. ThisHamiltonian gives rise to an emergent manifold at low temperature. The one free parameterin the model does not appear in the Hamiltonian but as an initial condition of the system.381.6. DiscussionFigure 1.21: Sample configurations for the model with Coulomb potential in (1.11) withc3 = ?1.0, for the system of size NV = 200, X = 20 drawn in three dimensions. Panel (a)shows a typical configuration in the high-temperature phase with ? = 1.0; panel (b) showsa typical configuration in the low-temperature phase with ? = 2.0.391.6. DiscussionThis parameter ? determines the edge to vertex ratio, which is conserved for the systemand determines the dimensionality of the emergent manifold. When ? is slightly larger than6, the low temperature solutions have structural properties consistent with triangulationsof two-dimensional surfaces. We obtained a representation of the emergent manifold by anoptimization scheme, wherein adjacent vertices are brought as close as possible to a certainlink distance, non-adjacent vertices are repelled from each other, and every triangularsubgraph is assumed to be filled to render the manifold.The spacetime manifold has historically been treated as a triangulation in several previ-ous approaches, in order to regularize the partition function by constructing discrete analogsto the continuum manifold [30?34]. For example, in dynamical triangulation theory a givenspacetime manifold is triangulated by simplices to calculate a discretized gravitational ac-tion [6,35,36]. In matrix models of gravity, graphs may be constructed as dual to Feynmandiagrams arising from the limit of large internal symmetry group; by construction the graphconstitutes a manifold. The partition function for 2-dimensional quantum gravity can beexpressed as a sum over topologies of triangulated 2D surfaces, for actions of various formsdescribing the coupling between matter fields and spacetime [37]; this problem has connec-tions to string theory via the Polyakov action [38]. The formalism may be extended to studyhigher dimensional generalizations of quantum gravity by group field theory models [39]. Inthis context, the emergence of a smooth ?hydrodynamic? spacetime has been described asa condensation of simplicial quantum building blocks [40]. Such dual graph triangulationshave widely varying vertex valency but generally represent manifold-like surfaces, at leastin the condensed phase. In contrast, the emergent manifolds that we observe have nearconstant valency, but often bifurcating morphologies, e.g. the ?bubble-wrap? or ?frenulum?defects in Figure 1.7.One can ask whether the present graph model could act as a substitute for the Feynmandiagram construction in matrix models. The Feynman diagram construction has fixedvalency, and is dual to a triangulated manifold, so a graph model of nearly fixed valencynv could in principle give rise to an emergent manifold of dimensionality nv ? 1 as its401.6. Discussion(a)(b)Figure 1.22: (a) A 3D cube triangulated into 5 tetrahedra [41] may be replicated bytranslation and reflection to tessellate the 3D space. Here, part of the dual lattice is shownas well in red. Red vertices are at the centers of the tetrahedra in the original triangulation.At the sites where the dual lattice bonds pass through the faces of tetrahedra in theoriginal tessellation, open circles are drawn. (b) 3D Euclidean space subdivided into thecubes shown in panel (a) (grey lines); triangulation of the cubes in panel (a) is not shownexplicitly here. The thicker black lines correspond to the dual graph of this triangulation.411.6. Discussiondual. The present graph-symmetry-based Hamiltonian, and the resulting triangular lattice-like graphs in the low temperature phase, make this interpretation unlikely. The meanvalency in the low temperature phase of our graph model is approximately 6, correspondingto the triangular lattice graph; we thus may consider a tessellation of a 5-dimensionalEuclidean space by tetrahedra. The triangular lattice graph has smallest cycles of 3 vertices,corresponding to traversing the smallest triangles in the graph. However, a Euclideantessellation using non-obtuse simplices will have cycles of its dual graph with no less than 4vertices, i.e. due to the acuteness (or more precisely non-obtuseness) of the simplices, everycycle consists of a (potentially non-planar) polygon of at least 4 sides. As an illustrationof this, consider the dual graph to a 3 dimensional tessellation by tetrahedra with non-obtuse dihedral angles. A section of a 3 dimensional tiling by such tetrahedra is shownin Figure 1.22(a), and the corresponding dual graph is shown in Figure 1.22(b). Here wesee that the smallest cycles of the dual graph are indeed 4, corresponding to pi/2 dihedralangles of the tiling tetrahedra. However a significant fraction of the cycles have length 6.Moreover, the cycles of length 4 appear as faces of 3D cubes in the dual lattice. All of thisstructure is incompatible with a regular planar graph of valency 4 as a potential dual tothe 3 dimensional tessellation; in particular, a graph having the topology of a square latticeis ruled out.In the model, there are no constraints on the global structure of the graph. As a conse-quence, the low-temperature phase can still retain complicated topologies with small-worldproperties, for which the corresponding manifold shows handles, self-intersections, and localdefects that deviate from the manifold, in that a higher embedding dimension is necessaryto represent them. Defects on the low-temperature manifold induce scattering and lensingeffects on the propagation of bosonic matter fields [42], and are an interesting topic of fu-ture work for our model. As well, the presence of non-local links in the low temperaturegraph, and the corresponding non-locality in the emergent manifold, is consistent with thepossible presence of disordered locality in loop quantum gravity [43], and might constitutea mechanism for its generation. In the context of loop quantum gravity, macroscopic ex-421.6. Discussionpectation values of area or volume deviate from those on a flat metric by O(`2p) or O(`3p)where `p is the Planck length; nonlocal connections in the underlying metric modify thelocal Hamiltonian coupling a matter field to loop quantum gravity, but leave the above ex-pectation values essentially unchanged, indicating locality may be macroscopically smoothbut microscopically disordered.As a general property of the graph model, the high-temperature phase has an entropythat grows super-extensively with system size NV . This results in a transition temperatureof zero in the limit NV ? ?, so that the infinite manifold is always disordered at any fi-nite temperature. Aside from a finite universe or diverging coupling constraints as possiblesolutions, we implemented long-range interactions between vertex defects with repulsiveCoulombic potential, to energetically penalize the many graph configurations with defectarrangements consistent with small-world topologies. In analogy with low-dimensional con-densed matter systems, long-range potentials that couple defects induce prohibitive ener-getic cost to configurations that would otherwise destroy order entropically, so that anordered phase at low temperature is restored. Here, we found that such potentials result ina nearly constant transition temperature as the size of the graph NV increases. In addition,we found that attractive Coulombic potentials result in long-lived metastable states in thesimulations.Another interesting feature of the model is that the low lying energy levels, includingthe ground state level, have large configurational degeneracy. This residual entropy isdue to local defects that can ?absorb? extra edges without energetic cost. As well, thesimulation dynamics indicates that the energy barriers between different low-energy statesare not high. Thus at temperatures below the phase transition, the degrees of freedomin the system arising from this residual entropy are not frozen. The small or zero-energybarriers between degenerate states make the low-temperature graph system similar to thespin ices observed in spinel structures and pyrochlore lattices [44?46].We have implemented here a sufficiently general Hamiltonian such that the same dy-namic model can give rise to space-times of different dimensionality, i.e. spaces of different431.6. Discussiondimensions are solutions to the same model. Exclusively from the graph theory point ofview, there is no a priori reason to choose any particular dimensionality as a phenomeno-logical term in the Hamiltonian. The ?emergent dimensionality?, then comes from initialconditions. Our motivation for this was to choose the simplest Hamiltonian possible, thatwas free of phenomenological parameters, so that the dimensionality of space-time wasnot ?baked into? the energy function that governed dynamics. That said, we acknowledgethat this approach effectively shifts the space-time dimension from extra phenomenologicalparameters in the Hamiltonian that favor or disfavor particular subgraphs [16], to specialinitial conditions. Our Hamiltonian is local in that it is a sum over all the vertices, and eachterm only depends on a small neighborhood (in our case, the neighborhood subgraph) ofeach vertex. This contrasts with other quantum graphity Hamiltonians, which have actionsthat depend on the number of loops with long lengths [12].It is intriguing to interpret the low-temperature configurations of this graph modelas an emergent spacetime ? a notion other researchers have explored for similar graphmodels [5, 6, 11?16, 47]. In this picture, General Relativity is an effective ?hydrodynamic?theory emerging from the collective dynamics of more fundamental degrees of freedom.The graph model is appealing in that both spacetime manifolds and locality emerge in thelow-temperature regime of a discrete structure. The graph model introduced here gives riseto real, positive distances, so the emergent manifold can only be a Wick-rotated, Euclideanversion of spacetime. Monte Carlo ?time? steps in the current Hamiltonian methodologyare distinct from the time evolution of the graph or manifold, and are only a mechanism tosample equilibrium states. In the present formulation, the Euclidean gravity theory under-goes a phase transition to smooth metrics below a ?temperature? parameter ?. Exploitingthe isomorphism between the quantum propagator and the statistical mechanical partitionfunction [48], the quantity e??H/?[dg]e??H is the equivalent to the Euclidean path integralmeasure that determines Green functions ?g1 . . . gn? for the metric g in a quantum gravitymodel with the corresponding action. While we have seen a phase transition for the systemwith Euclideanized action, the identification of the appropriate thermal quantum states441.6. Discussionthat are periodic in real time, and so related to the parameter ?, is not clear at present.We see this problem of mapping back to the space-time coordinates with Minkowskian sig-nature as a general challenge for quantum graphity models. Another general issue is theabsence of an underlying symmetry principle to determine the action in quantum graphitymodels, analogous to the role of general covariance in the action for quantum gravity.The complex topologies of surfaces corresponding to low-temperature graphs, along withgraph defects having zero energetic cost, implies that a graph model consisting solely ofthe current Hamiltonian does not reduce to a classical theory of Euclidean gravity in themacroscopic limit. On the other hand, other discrete models of gravity are also known tohave scale-dependent spectral dimension, indicating fractal, non-smooth geometries for theemergent manifolds at least at intermediate length scales [49?51]. The set of all possiblelow-energy graphs in this model could potentially be identified with the phase space of aEuclidean gravity theory before imposing the equation of motion, i.e., the space of all pos-sible metrics modulo diffeomorphisms. Because the low-temperature graphs of our modelare nearly triangulations, and random triangulations form the phase space of many otherdiscrete gravity models [6,35?37,39], it may be interesting to investigate whether the graphmodel?s action may be extended to include terms in dynamical triangulation theory, whichdo reduce to the gravitational action in the continuous limit.The transition from disordered to ordered manifolds is first-order in the present graphmodel. However, the order of the transition, and its potential relevance to universality orindependence of underlying lattice specifics, is a non-issue for the investigation of orderedphases below the transition, where correlation lengths are finite. Power-law correlationscalculated in causal dynamical triangulation are between graphical elements analogous tograviton fields, so that graviton coupling is power law as in the classical limit. Space totime ratios of simplices have second order transition in this model, while the transitioninvolving gravitational coupling is first order [52]. In any event, a graph model at a criticalpoint would have wildly fluctuating connectivity and resemble more a fractal mix of orderedand disordered states, which is not consistent with an emergent manifold. The issue of the451.7. Appendix: The weighted histogram analysis methoduniversality classes and corresponding exponents of a transition is a separate one from theproperties of an emergent manifold as a low-temperature phase below a phase transition.Retention of microscopic structure in the disorder to order transition is a prediction of thegraph model, and may enable future experimental tests.Finally, it is intriguing to speculate on the utility of a such a graph theoretical transitionto describe a transition involving non-local to local causality, as might occur in a pre-inflationary universe. Such models may address the low-entropy initial condition problemsthat occur in inflationary models [53,54].1.7 Appendix: The weighted histogram analysis methodThe weighted histogram analysis method (WHAM) is a method used to combine thesamples from several Monte Carlo simulations taken under conditions of different temper-ature and added potential. We employ WHAM to generate optimal estimates of energydistributions of the graph model. In this model, the energy takes only integer values be-tween 0 and M = 1.5NV . Assume that S simulations are performed (in our cases, S = 4for NV = 1000, S = 10 for NV = 2000), with inverse temperature ?i, and biasing po-tential Vi(E), i.e., in the i-th simulation, the system is sampled with energy distribution?(E) exp(??i(E + Vi(E))), where ?(E) is the yet-unknown number of states with energyE. The inverse temperature ?i?s are taken to be near the inverse transition temperature.Because there is a large free energy barrier between the low and high energy phases nearthe transition temperature, a biasing potential is used to obtain better sampling in thebarrier region. The form of the biasing potential is taken to be parabolic:Vi(E) =???????????????vi??(E?Eli+Ehi2)2(Ehi ?Eli2)2 ? 1?? , Eli ? E ? Ehi ,0, E < Eli,0, E > Ehi ,461.8. Appendix: The Floyd-Warshall algorithmwhere the parameters vi, Eli and Ehi are chosen by trial-and-error to make the energydistribution of each simulation as flat as possible.After performing the simulations, let ni(E) be the number of counts of energy E fromthe i-th simulation, and Ni the total number of samples from the i-th simulation. Fromthis information, the optimal estimate of the probability p0(E) of energy level E at inversetemperature ?0 without any biasing potential is given byp0(E) =?Si=1 ni(E)?Si=1Nifici(E), (1.12)where ci(E) is the biasing factor ci(E) = exp[?(?i ? ?0)E ? ?iV (E)], and fi is a normal-ization constant satisfyingf?1i =M?E=0ci(E)p0(E). (1.13)To solve these equations, we take an arbitrary set of initial values for fi (namely f0i = 1),and apply (1.12) and (1.13) iteratively to find the solution to these equations. After findingp0(E), it is then straightforward to calculate the average energy and heat capacity at inversetemperature ?0.1.8 Appendix: The Floyd-Warshall algorithmThe most time-consuming step in the simulation is to compute the diameter and radiusof the neighborhood subgraphs. A straightforward method is to find the length of shortestpath for every pair of vertices in a neighborhood subgraph, using the Dijkstra?s algorithm[55]. If a vertex v have valency d, which is also the order of its neighborhood subgraph, therunning time of one implementation of the Dijkstra?s algorithm is O(d2), so the runningtime for computing the diameter and radius of GN (v) is O(d4).Instead of the Dijkstra?s algorithm, the Floyd-Warshall algorithm [56, 57] is used inthe simulation, which computes the distances of all pairs of vertices in a graph in oneimplementation. Denote the vertices of a neighborhood subgraph as {v1, v2, . . . , vd}. Inthis algorithm, a function s(i, j, k) is defined to be the length of shortest path between vi471.9. Appendix: The number of random graphs and random semi-regular graphsand vj , using only the set of vertices {v1, v2, . . . , vk} as intermediate points along the path.s(i, j, k) is computed by induction. The base case iss(i, j, 0) =???1, if vi, vj are adjacent,?, otherwise.(1.14)Assume that s(i, j, k ? 1) is known for all i, j. The are two possibilities for comput-ing s(i, j, k): either the shortest path between i and j using intermediate vertices in{v1, v2, . . . , vk?1} is the shortest path between i and j using intermediate vertices in {v1, v2, . . . , vk},or there is a shorter path that goes from vi to vk, using intermediate vertices in {v1, v2, . . . , vk?1},and then from vk to vj , using intermediate vertices in {v1, v2, . . . , vk?1}. This can be sum-marized as the relations(i, j, k) = min(s(i, j, k ? 1), s(i, k, k ? 1) + s(k, j, k ? 1)). (1.15)Thus for all i and j, s(i, j, k) can be computed from s(i, j, k ? 1) in running time O(d2).By definition, s(i, j, d) gives the length of shortest path between vi and vj , and the totalrunning time is O(d3). The operations inside the 3-fold loops is (1.15), which is composedof only an addition and a comparison, so this algorithm has better performance than theDijkstra?s algorithm even for small d?s (in our case, 6 or 7).1.9 Appendix: The number of random graphs and randomsemi-regular graphsIn this section, we give two examples of graph counting, to support the statementthat when NV is large, the number of inequivalent graphs with NV vertices is typicallyN??NVV , with ?? being a positive constant number. For this statement about the number ofinequivalent graphs to hold, we actually allow for other multiplicative factors in the numberof graphs, so long as they increase slower with NV than N??NVV . More formally, denote thenumber of inequivalent graphs by N , we like to show thatlnNNV lnNV= ?? +O(1NV). (1.16)481.9. Appendix: The number of random graphs and random semi-regular graphsIn the following, the Stirling?s formula will be used,n! =?2pin(ne)n(1 +O(1n)). (1.17)As a simplification of the simulated case, we first count the number of graphs with NVlabeled vertices, and NE unlabeled edges. Define n =(NV2), and the number is given byN =((NV2)NE)=(NV2)![(NV2)?NE]!NE !=?2pin(ne)n (1 +O(1n))?2pi(n?NE)(n?NEe)n?NE (1 +O(1n))?2piNE(NEe)NE (1 +O(1NE))=?n2pi(n?NE)NEnn(n?NE)n?NENNEE(1 +O(1NE))=1?2piNEnn(n?NE)n(n?NE)NENNEE(1 +O(1NE))=1?2piNEeNE(nNE? 1)NE (1 +O(1NE))If we take NE ' 3NV as in the simulations, then the above number becomesN '1?2piNEeNE(NV6)3NV (1 +O(1NV)).The dominant part of this number is thus N3NVV .The second example takes into account the distribution of valencies. Constrained by theHamiltonian, all vertices in the model have valency-6 or 7. For a graph with NV verticesand NE = 3NV + X edges, there are 2X vertices with valency-7, and NV ? 2X verticeswith valency-6. The number of graphs with this distribution of valencies is [27]N =(NV2X)(3NV +X)!(6!)NV ?2X(7!)2X[2(3NV +X)e]3NV +Xexp[?21(3NV + 2X)(5NV + 4X)4(3NV +X)2](1 +O(1NV))In our case, X is proportional to NV , and it can be seen that the dominant term in thiscase also takes the form N??NVV .Two other constraints in the simulation, which are that the graph must be connected,and that all the neighborhood subgraphs must be connected, are not implemented in theabove examples. However, we expect that this constraint will not change the general formof the graph counting.49Chapter 2Aspects of Chern-Simons theory in2 + 1 dimensions2.1 IntroductionGauge symmetries play a crucial role in quantum field theory. Historically, the firstwell-studied gauge theory is the theory of electromagnetic field, and then its non-Abeliancounterpart, Yang-Mills theory (see (2.2) below). Perhaps surprisingly, it was discoveredthat Chern-Simons theory (CST) in 2 + 1 dimensions (see (2.1) below), for which theaction takes a completely different form than the standard Yang-Mills action, is also a veryinteresting prototype gauge theory [58, 59]. From its action, it can be derived that CSTpossess many distinct properties from those of Yang-Mill theory. For example, CST is atopological field theory, and it imposes a chirality to the system, both of which will bediscussed in detail later. The study of CST has uncovered several intriguing connectionsbetween CST and other topics in both mathematics and physics, including knot theory [59,60], conformal field theory [61?64], and Morse theory [65]. CST has been widely used inbuilding various physics models. For example, it is incorporated in models for quantumHall effect [66], anyons [67], and protein folding with chirality [68].One important motivation for studying CST is its relation with three dimensional grav-ity [69?72]: There exists a mapping between the gauge fields from the theory defined by thesum of two CSTs, and the metric field of gravity in 2 +1 dimensions. As a consequence, in-finitesimal gauge transformations of CST are mapped to the infinitesimal diffeomorphismsof gravity. By quantization of CST, which is better understood than that of 3D gravity,502.1. Introductionquantization of 3D gravity then becomes relatively straightforward. Because of the difficul-ties involved in four (or more) dimensional gravity theories (see, e.g., [73?76]), 3D gravity isused as an important test ground for possible resolutions to its more realistic counterparts.Thus the relation between CST and 3D gravity is an important step in our exploration ofmodels of quantum gravity.Some subtleties exist in relating CST and 3D gravity [77, 78], however: By inspectingthese two theories, one can note that CST is only well-defined if the spacetime manifoldis orientable, while 3D gravity, which in principle includes all possible topologies of thespacetime manifold, has no such constraint. Thus it is natural to consider how the relationbetween CST and 3D gravity can be generalized to incorporate the case of non-orientablemanifolds. For this purpose, the definition of integration of forms will be reviewed, and amore general version of integration ? the integration of densities, which is well-defined onboth orientable and non-orientable manifold will be applied to this relation. With somemodifications, it will be shown that CST can be utilized in calculating quantities in 3Dgravity, now including the non-orientable topologies.Another interesting aspect of the connection between CST and 3D gravity is the map-ping class group (MCG) [79] of the spacetime manifold, which is the group of large diffeo-morphisms of the spacetime manifold. Since a gravity model should possess the property ofgeneral covariance, which includes the MCG as a classical symmetry, it is reasonable to tryto implement this symmetry into CST after the connection with 3D gravity is established.It is known that by incorporating the MCG in the process of quantization, non-trivial ef-fects can emerge, e.g., the value of the coupling constant is constrained. This questionwill be studied in detail later in this chapter, for the case of U(1) gauge group, and in theprocess of quantization, the large gauge transformation group and the holonomy group areonly required to have deformed representation after quantization.The method of quantizing U(1) CST can also be applied to non-orientable manifolds,using the formalism of integration of densities. CST cannot be defined on non-orientablemanifold however. Thus the analog theory, which is U(1) BF theory (named after the fields512.2. Fundamentals of Chern-Simons theoryinvolved in the theory, see (2.15) and (2.16)) in our case, will be quantized on non-orientablemanifolds.This chapter is organized as follows. In section 2.2, some relevant fundamental proper-ties of CST will be reviewed. In section 2.3, the relation among the CST, the BF theory, and3D gravity will be elucidated, especially when the space-time manifold is non-orientable.In section 2.4, some results from theory of MCG that are important to our calculationswill be reviewed. In section 2.5, the U(1) Chern-Simons theory on orientable manifolds willbe quantized in an explicit manner. In section 2.6, the same technique will be applied toquantizing U(1) BF theory on non-orientable manifolds.2.2 Fundamentals of Chern-Simons theoryIn this section some fundamental properties of CST will be reviewed. CST showsexceptionally rich structures after years of study. (For comprehensive review of CST, seee.g. [80].) This section will thus not cover all aspects of CST, but will focus on those aspectsrelated with its relation with BF theory and 3D gravity, and the quantization of U(1) CST.The action of CST is the integral of the Chern-Simons 3-form [81]:ICS[A] =kCS4pi?MTr{A ? dA+23A ?A ?A}, (2.1)where M is an orientable, three dimensional, spacetime manifold with no spatial boundary,A is a one-form field taking values in a Lie algebra? g, d is the exterior derivative, ? is thewedge product operator, Tr is a trace operator on g, and the integration is the integrationof n-forms defined on n-dimensional manifolds (for definitions of these terms, see, e.g., [83]).If M has spatial boundary, the action (2.1) should be supplemented with proper boundaryterms. For simplicity, here and in the following, M is always assumed to have no spatialboundary.?More generally, A is defined to be a connection of a G-bundle on M . If the bundle is trivial, and g isthe Lie algebra of G, then it reduces to the above simplified definition [82].522.2. Fundamentals of Chern-Simons theoryThe standard Yang-Mills theory in 2 + 1 dimensions has the actionIYM[A] =?M?det gg??g??Tr (F??F??) d3x, (2.2)where g?? is a metric on M , F = dA+A?A, and in this case the integration is the Riemannintegration.Compared with the Yang-Mills action (2.2), the most obvious features of the CST action(2.1) are that it has only first order derivative, and is independent of the metric on M . Aswill be explained later, these properties have important consequences for the structure ofCST.For both Yang-Mills theory and CST, the gauge transformation takes the formA? g?1dg + g?1Ag, (2.3)where g is a Lie group G-valued field, and the corresponding Lie algebra of G should beg. When the difference between g and the unity is infinitesimal, the Yang-Mills action andthe CST action are invariant under (2.3). However, for a general field g, the CST action(2.1) is not exactly invariant. Rather, it transforms asICS[A]? ICS[A]?kCS4pi??MTr((dgg?1)?A)?kCS12pi?MTr(g?1dg)?(g?1dg)?(g?1dg). (2.4)On the right-hand side, the second term vanishes as M is assumed to have no boundary; thethird term is a topological invariant [84], which is the winding number of g multiplied by2pikCS. If g is non-abelian, there exists gauge transformations that give non-zero windingnumbers. Thus for a non-abelian g, the path integral of the Chern-Simons action (2.1)is invariant under gauge transformations with nonzero winding numbers only if kCS is aninteger.CST is known be a topological field theory, in the sense that observables of CST dependonly on topological structures of the configuration, but not on the metric of the spacetimemanifold [59] (see [85] for a review of topological field theory). This result is shown undera Dirac quantization, wherein the full phase space is quantized first, and then the gaugeconditions are imposed at the quantum level. In an alternative method called the reduced532.2. Fundamentals of Chern-Simons theoryquantization, the gauge conditions are imposed at the classical level, and then the reducedphase is quantized. It is much easier to show that CST is topological under the reducedquantization, as it is only necessary to show that CST possess no local degree of freedomsclassically. The proof of CST being topological under the reduced quantization is reviewedbelow.In a nutshell, the absence of local degrees of freedom can be shown using a simplecounting of degrees of freedom ?per point?. Assume that the rank of the Lie algebra g isr. At one spacetime point, the A field has 3r degrees of freedom. In (2.1), there is no timederivative on the temporal component of A, so these r degrees of freedom act as Lagrangianmultipliers and are not dynamical. By fixing the gauge symmetries generated by (2.3), rdegrees of freedom are fixed by the gauge equation, and the last r degrees of freedom arefixed by the gauge-invariant condition. So in the end there is zero degree of freedom ateach spacetime point, which shows the CST theory is classically topological. Of course,when the topology of M is non-trivial, this argument does not take the global structuresinto consideration. There are ?left-over? discrete degrees of freedom which depend on thetopology of M .To be more precise, assume that M is in the form M = R ? ?, where R is the realline, and ? is a compact two dimensional manifold without boundary. The 1-form field Adefined on M can be decomposed as A = At + A?, with At the temporal component andA? the components on ?. The Chern-Simons action is decomposed asICS[A] =kCS4pi?MTr{A ? dA+23A ?A ?A}=kCS4pi?MTr {At ? dAt +A? ? dAt +At ? dA? +A? ? dA? + 2At ?A? ?A?}=kCS4pi?MTr {A? ? dtA? + 2At ? (d?A? +A? ?A?)}=kCS4pi?MTr {A? ? dtA? + 2At ? F?} ,(2.5)where dt and d? are the exterior differentiation operators on R and ? respectively. Notethat in the second line, the first term vanishes because the wedge product is antisymmetric,542.3. Relation with the BF theory and 3D gravityand the second and the third term cancel each other by doing integration by parts. In theabove action, At acts as a Lagrange multiplier and enforces the constraint equation F? = 0.In addition, gauge equivalent configurations need to be identified. Thus the reduced phasespace is the space of flat connections on ? modulo gauge transformations. This space isalso the space of all possible holonomies around non-trivial cycles on ?, modulo a constantgauge transformation. In mathematical terms, this isMreduced = Hom(pi1(?), G)/adG, (2.6)where pi1(?) is the fundamental group of ?, Hom(?, ?) is the space of homomorphisms, andadG is the space of adjoint action of G on the homomorphisms. This reduced phase spaceMreduced is finite dimensional, because pi1(?) and G are both finite dimensional. Thusthe conclusion that CST is topological by the naive counting argument in the previousparagraph is confirmed.2.3 Relation with the BF theory and 3D gravityIn this section we will study the relations between CST, BF theory and 3D gravity. 3Dgravity in this thesis refers to standard General Relativity in three dimensions, which isdefined by the path integral of the Einstein-Hilbert actionIEH =116piG?Md3x??det g(R? 2?) + boundary terms, (2.7)where the dynamic field g is a rank 2 symmetric tensor field on M with Lorentzian signature,? is the cosmological constant. In principle, the path integral includes all possible manifoldsM satisfying the boundary conditions, if there is any boundary. Although the action hasthe same form as its higher dimensional counterparts, the theory can be shown to be freeof any local degrees of freedom, so it is particularly simple to analyze. On the otherhand, interesting solutions can be constructed in 3D gravity, such as propagating massiveparticles [86], black holes [87] and wormholes [88]. As a consequence, 3D gravity can be552.3. Relation with the BF theory and 3D gravityviewed as a prototype quantum gravity theory, and be studied to understand the difficultiesarisen from quantum gravity theories, such as the black hole entropy paradox [87].It is well known that the action of 3D gravity can be reformulated as some gauge theoryaction [69, 70], usually the sum of two Chern-Simons actions. (See [71] for a review of therelation between the two theories.) Compared with 3D gravity, the corresponding gaugetheories are defined on a fixed spacetime manifold rather than all possible manifolds, andtheir properties are better understood. Thus this relation between 3D gravity and gaugetheory can further simplify the study of 3D gravity.However, there are subtleties in this relation [77, 78]. One inequivalence is that somegauge theory configurations are mapped to degenerate metrics, which is putatively forbid-den in gravity theories. As a result, the gauge theory phase space splits into several sectors,which are separated by the configurations corresponding to degenerate metrics, and the 3Dgravity phase space is only one of these sectors. Quantizations of these two different phasespaces are generally different.There is yet another inequivalence that will be focused on in this section. One cannote that the Chern-Simons action (2.1), as an integral of 3-form, is defined only when themanifold is orientable. On the other hand, the 3D gravity theory is a theory of geome-tries, and should be well-defined regardless of the orientability of the space-time manifold.Actually, because we are dealing with gravity, no prior metric is present, so we hope towrite the gauge theory action as an integral of differential forms. But if the space-timemanifold is non-orientable, the conventional definition of such integral fails. Fortunately,there is a generalization of such integral ? on an orientable or non-orientable n-manifold,n-form densities can be integrated. An n-form density is different with an n-form only inthat, under a coordinate transformation with a negative Jacobian determinant, an n-formdensity obtains an extra minus sign. The mathematical definition of densities will con-structed in detail below. In terms of such integral, 3D gravity in general can be written asa gauge theory known as BF theory. In [89], 3D gravity action with vanishing cosmologicalconstant is written as an integral of a 3-form density, and the classical solution space for562.3. Relation with the BF theory and 3D gravitythe space-time topology R? (Klein bottle) is discussed in detail. Our formalism below willgeneralize the results of [89] to arbitrary cosmological constant and arbitrary topology ofthe spacetime. Also, following the general recipe we developed, more models can be definedon non-orientable manifolds.We show below that 3D gravity is related with BF theory, so that techniques developedfor one theory can be utilized to deal with the other. Classically, BF theory is closely relatedwith CST defined on the orientable double cover with parity conditions on the solution,with the exception that their mapping class groups do not map simply. Most results ofChern-Simons gravity remain true in this more general theory.2.3.1 p-form densities and integrationIn this subsection we review the mathematical formulation involving integration of den-sities, which can be used to deal with fields on non-orientable manifolds.Recall that a diffeomorphism of open subsets of Rn is orientation-preserving if theJacobian determinant of the diffeomorphism is everywhere positive. Let M be covered bythe atlas {U?, ??}??A, where U??s are open sets that cover M , and for each ?, ?? : U? ? Rnis a homeomorphism. The atlas is oriented if all the transition functions g?? = ?????1? areorientation-preserving, and M is orientable if it has an oriented atlas. On an orientablemanifold M , there are two sets of coordinate charts, which is defined such that chartsin the same set have orientation-preserving transition functions. Either set is called anorientation, denoted by [M ]. It can be shown that an n-dimensional manifold M isorientable if and only if there exist a nowhere vanishing n-form on M .On an orientable n-dimensional manifold M , after choosing an orientation [M ], the (con-ventional) integration of a n-form is defined as follows. Given an oriented atlas {U?, ??}??Awithin [M ], the integration of n-form ? is?[M ]? =???A?Rn(??1? )?(???), (2.8)where {??}??A is a partition of unity of the atlas A, (??1? )? is the pullback of ??1? , and the572.3. Relation with the BF theory and 3D gravityintegrals on the right-hand side are Riemann integrals [90]. Usually a fixed orientation [M ]is understood, and the integration is simply written as?M ? . This definition of the integral?M ? has the property that it is independent of the atlas and the partition of unity.With the above conventional integral of forms in mind, we define several concepts todeal with integration on non-orientable manifolds. All the following concepts and propertiesapply to both orientable and non-orientable cases, although for the orientable cases, theyare rather trivial counterparts of the conventional concepts.On a non-orientable n-dimensional manifold, an n-form indeed cannot be integrated.However, another set of objects, the n-form densities, can be integrated. Let the n-dimensional manifold M be covered by the atlas {U?, ??}??A. The orientation bun-dle (O,M, pi) [91, 92] is a Z2-bundle over M , specified by transition functions t?? =sgn[det(J??)], where J?? is the Jacobian of the transition function between two charts.Let ?p(M) denote the bundle of smooth p-forms on M . A p-form density is a smoothsection of the bundle ?p(M)?p O, where the notation ?p means the the tensor product istaken for the fibers at each point.One can see the orientation bundle merely stores information about relative orientationbetween local charts ? if two overlapping charts have the same orientation, their transitionfunction is 1, otherwise it is ?1. In a local chart, assume a p-form density is expressed as(ai1???ipdxi1 ? ? ? ? ? dxip , z), then the combination of coefficients z ? ai1???ip of a p-form densitytransforms between two coordinate charts as [90]z? ? a?j1???jp = sgn(det J)?i1,...,ip?xi1?x?j1? ? ??xip?x?jpz ? ai1???ip (2.9)That is, they transform in the same way as coefficients of regular p-forms, except thatthere is an extra minus sign when the coordinate orientation is reversed. In physics, suchan object is also called axial scalar/vector/tensor; examples include magnetic field andangular momentum.The total space of the orientation bundle of M is called the orientable double cover?of M , and is denoted as M? . Because the fiber of this orientation bundle is a discrete set,?Note that given M , there can be other double cover spaces of M that is orientable. For example, a582.3. Relation with the BF theory and 3D gravityand thus sections take constant values in the fiber locally, M? is indeed a double cover ofM . Explicitly, M? is the set (???A U? ? {?1})/ ?, where (x, z) ? (x?, z?) if and only ifx = x? ? U? ? U? and z = t??(x)z?. In this way M? is a two-fold cover of M , with theprojection map pi : M? ? M given by pi(x, z) = x. M? as a manifold is described by theatlas {U??,z, ???,z}??A,z?Z2 , where the new atlas is labelled by two indices ? and z, and???,z = (??, z). If U? ? U? 6= ?, then U??,z ? U??,t??z 6= ?, and the transition function is????1? .As suggested by its name, M? is orientable. This can be proven by using a refinement{V?}??B of {U??,z}, that is, for any ? ? B, there exists ? and z such that V? ? U??,z, and{V?}??B still covers M? . Construct the functions ??(x?) such that ??(x?) = 1 for x? ? V?,??(x?) = 0 for x? /? U??(?),z(?), and ??(x?) ? 0 everywhere. Then the n-form???Bz??(x?)dx?1? ? ? ? ? ? dx?n?is nowhere vanishing, because every nonzero term in the summand has the same sign, dueto the expression of t??, and at each point in M? , at least one term is nonzero, since {V?}??Bcovers M? .With respect to the involution ? : M? ? M? given by ?(x, z) = (x,?z), p-forms on M?split into even forms and odd forms?p(M?) = ?p+(M?)? ?p?(M?) (2.10)according to (????+)(x?) = ??+(x?), and (?????)(x?) = ????(x?). The pullback pi? : ?p(M) ??p+(M?) is a bijection, so regular forms on M are equivalent with even forms on M? . Givena p-form density ? on M and v1, . . . , vp ? T(x,z)(M?), we can define ?? ? ?p?(M?) by?(pi?(v1), . . . , pi?(vp)) = ??(v1, . . . , vp)? (x, z), (2.11)which gives an identification of p-form densities on M and odd forms on M? . In plainwords, on M there exists p-forms and p-form densities, and equivalently we can work oncircle S1 can be double-covered by another S1, while the orientable double cover of S1 is two copies of S1.Thus the name ?orientable double cover? is a little confusing. In the following, we always use it to indicatethe total space of the orientation bundle.592.3. Relation with the BF theory and 3D gravitythe orientable double cover M? , on which we only consider p-forms with a definite parity. Itis obvious that the wedge product of two odd forms is an even form, the wedge product oftwo even forms is an even form, and the wedge product of an odd form and an even form isan odd form, as their names suggest. These relations hold for p-forms and p-form densitiescorrespondingly.We can also define Lie algebra valued p-form densities. They are sections of the tensorproduct space g? (?p(M)?p O).The exterior derivative d commutes with ??, because in general, the exterior derivativecommutes with pullbacks. The de Rham cohomology group splits accordingly,Hp(M?,R) = Hp+(M?,R)?Hp?(M?,R), (2.12)so we can talk about harmonic p-form densities on M , in addition to harmonic p-forms.The most important property of densities is that a p-form density can be consistentlyintegrated on a p dimensional manifold. From the above discussion, one can easily see thatthe following integration of p-form densities on a p-dimensional manifold M ? is well defined,?M ?? =12?M? ???, (2.13)where on the right side it is the regular integral of the corresponding odd p-form on theorientable double cover.Consider a p-form density ? supported on one coordinate chart. By (2.13), the integra-tion of ? is given in terms of the coordinates by?M ?? =?zai1???ipdxi1 ? ? ? dxipUnder a diffeomorphism of M ?, the integration transforms into?z?a?j1???jpdx?j1 ? ? ? dx?jp=???sgn(det J)?i1,...,ip?xi1?x?j1? ? ??xip?x?jpzai1???ip????sgn(det J)?i1,...,ip?x?j1?xi1? ? ??x?jp?xipdxi1 ? ? ? dxip??602.3. Relation with the BF theory and 3D gravitySo the transformations of the two parts cancel exactly, and the integration is invariantunder arbitrary diffeomorphisms, as opposed to regular integrations, which are only invari-ant under orientation-preserving diffeomorphisms. This conclusion holds for integrationof a general p-form density, because it can be decomposed into a sum of p-form densitiessupported on one coordinate chart, using a partition of unity for M ?.From Stokes? theorem of regular integrations, using (2.13), we can prove the followingStokes? theorem for densities: Let D be a regular domain in a p-dimensional manifold M ?,and ? be a (p? 1)-form density of compact support. Then?Dd? =??D?. (2.14)Example 1. As a first example, let M be orientable. By the nowhere vanishing n-formon M , all coordinate charts fall into two families: charts on which the coefficient of then-form is positive/negative. Then the orientation bundle is a trivial Z2-bundle ? it iscomposed of two disconnected copies of M , say M?1 = M ? {?1}. Given a p-form ? onM , the corresponding even form is pi??. It happens ? also corresponds to an odd form,by ??? = ?pi??, for x ? M?1, and the p-form density is given by (2.11). So essentiallythere is no need to distinguish between p-forms and p-form densities when the manifold isorientable.Example 2. A simple non-orientable example is the Mo?bius strip. It can be covered bythree coordinate charts (x, y) ? ?1(U1) = [0, 1/2) ? [0, 1], (x?, y?) ? ?2(U2) = [1/3, 5/6) ?[0, 1], (x??, y??) ? ?3(U3) = [2/3, 7/6)? [0, 1], and the transition functions are(x?, y?) = ?2,1(x, y) = (x, y)(x??, y??) = ?3,2(x?, y?) = (x?, y?)(x, y) = ?1,3(x??, y??) = (x?? ? 1, 1? y??).Consider a constant 0-form ? and a constant 0-form density ?. Assume that on U1, ? = a,where a is a constant real number. By the coordinate transformation law, it is easy to seethat ? = a on all charts. Assume that on U1, ? = b, where b is a constant real number. By612.3. Relation with the BF theory and 3D gravitythe coordinate transformation law of densities, by ?2,1, ? = b on U2; by ?3,2, ? = b on U3;by ?1,3, ? = ?b on U1. Thus this constant 0-form density is inconsistent unless b = 0.The orientable double cover of the Mo?bius strip by construction is covered by 6 coordi-nate charts, ?i,?1, and the transition functions are(x?+, y?+) = ?2,+1,1,+1(x+, y+) = (x+, y+)(x??+, y??+) = ?3,+1,2,+1(x?+, y?+) = (x?+, y?+)(x?, y?) = ?1,?1,3,+1(x??+, y??+) = (x??+ ? 1, 1? y??+)(x??, y??) = ?2,?1,1,?1(x?, y?) = (x?, y?)(x???, y???) = ?3,?1,2,?1(x??, y??) = (x??, y??)(x+, y+) = ?1,+1,3,?1(x???, y???) = (x??? ? 1, 1? y???)This is just a complicated way to describes a cylinder, because the transition functions listedabove connect the coordinate charts one by one, with the last chart connected back to thefirst, and two of the transition functions flip the orientation. In fact, if M is non-orientable,its orientable double cover M? is always connected.2.3.2 The relationIn the previous sub-section the integral of n-form densities on non-orientable n-manifoldswas defined. Using this construction we can define field theories on manifolds with eitherorientability by finding some n-form density as the Lagrangian. The BF theory [93] is sucha theory. The action of the BF theory in three dimensions is written asIBF0[A,B] =kBF02pi?MTr {B ? F} , (2.15)where the integral now is an integration of densities, A is a g-valued one-form field, B is ag-valued one-form density, F = dA+A?A, and kBF0 is the coupling constant. This theoryis well-defined regardless of the orientability of M .Because we like to map the BF theory to 3D gravity with arbitrary cosmological constant(see (2.24)), a generalized BF theory is needed. To construct a n-form density, it is required622.3. Relation with the BF theory and 3D gravityeach term of the Lagrangian includes odd number of densities. In n = 3 dimensions, anotherterm composed of A and B may be added to (2.15),IBF[A,B]M =kBF2pi?MTr{B ? F ??3B ?B ?B}(2.16)where kBF and ? are parameters. When we relate this theory with 3D gravity below, ?will become the cosmological constant. In the rest of this section, we will analyze this threedimensional, generalized BF theory, and will refer to it simply as BF theory. Using Stokes?theorem, its equations of motion aredB +A ?B +B ?A = 0,dA+A ?A? ?B ?B = 0.(2.17)Now we show that the BF theory is related with the 3D gravity theory. From the 3Dgravity actionIEH =116piG?Md3x??det g(R? 2?), (2.18)one can change the fundamental variable from the metric g to the local frame e and spinconnection ?, according to the definitions?abea? eb? = g?? , (2.19)??ea? + ?a? beb? = 0. (2.20)where ? = diag{?1, 1, 1}. We also define the spin connection field with one local index?a =12\u000Fabc??bcdx?.where \u000Fabc is totally antisymmetric with \u000F012 = 1, and its indices are raised and loweredby ?ab and ?ab. Note that in this change of variable, according to (2.19), the local frame eis determined by g up to a local Lorentz rotation. This symmetry is an additional gaugesymmetry of the resulting model. On the other hand, ? is fully determined by e classically,so there is no more gauge symmetry associated with ?. In fact, it can be shown that ? isgiven by? a? = \u000Fabce?c(??e?b ? ??e?b)?12\u000Fbcd(e?be?c??e?d)ea? . (2.21)632.3. Relation with the BF theory and 3D gravityNow we rewrite the action (2.18) in terms of the new variables e and ?. The determinantof metric is related to the local frame e as(?det g) = (\u000F???e 0? e1? e2? )2,where \u000F??? is totally antisymmetric with \u000Ftxy = 1. When taking square root on both sides,there may or may not be an extra minus sign, so the volume element in the Einstein-Hilbertaction (2.7) is??det gd3x =16\u000Fabcea ? eb ? ec ? sgn(det e).The left-hand side of the above equation is a volume form that can always be integrated;the right side is a 3-form, and it is integrable in general only if ea is a 1-form density.So we identify ea as a 1-form density field with a local frame index. According to thedefinition (2.20), ?a is still a 1-form field with a local frame index. After some calculation,the Einstein-Hilbert action can be cast into the Palatini form [94],I ?P =216piG?M{[ea ?(d?a +12\u000Fabc?b ? ?c)??6\u000Fabcea ? eb ? ec]? sgn(det e)}. (2.22)If the topology ofM is fixed, this action appears to be a well-defined gauge theory action,except for the awkward term sgn(det e). Actually, in gravity traditionally we require themetric to be non-degenerate everywhere, so for any gravity solution, the factor sgn(det e)does not change sign, and thus has no effect at all. However, as soon as we write themetric in terms of the local frame in this way, we allow the factor sgn(det e) to changesign within the space-time, which is equivalent to allowing the metric to take degeneratevalues. In other words, the gauge theory is not really a reformulation of 3D gravity, but anextension whose classical solutions include the gravity solutions as a subset [77,78]. For thesame reason, one can also choose to neglect the factor sgn(det e), and the result is anotherextension of 3D gravity. Due to difficulties in quantizing the original gravity theory, it isconjectured that such a gauge theory extension may give a quantization of 3D gravity [70].For simplicity, we choose to neglect the factor sgn(det e), so the action becomesIP =216piG?M{ea ?(d?a +12\u000Fabc?b ? ?c)??6\u000Fabcea ? eb ? ec}(2.23)642.3. Relation with the BF theory and 3D gravityThis Palatini gravity action is nothing but the BF action (2.16) with a cosmologicalconstant term, if we interpret the local indices as labeling the components of a gauge fieldtaking value in the Lie algebra sl(2,R). Let B = eaTa, A = ?aTa, where Ta is the followingset of sl(2,R) generators,T0 =12??0 ?11 0?? , T1 =12??1 00 ?1?? , T2 =12??0 11 0??They have the properties [Ta, Tb] = \u000F cab Tc, Tr(TaTb) =12?ab. ThenIP = IBF =14piG?MTr{B ? (dA+A ?A)??3B ?B ?B}. (2.24)This is the relation between BF theory and 3D gravity, at the level of Lagrangian. Thereare more conceptual differences between them. A gravity theory is supposed to include allpossible manifolds. In our case, there is no spatial boundary, so all manifolds of the formR?? with ? a compact 2-manifold should be included. On the other hand, the BF theoryis defined on a fixed manifold. If one performs a path-integral of 3D gravity, and decidesto include the non-orientable configurations, our formalism allows computing contributionfrom the non-orientable manifolds to the path-integral, by means of BF theory.A further step in this relation between theories is that the BF theory action is thesum of two Chern-Simons actions. In this relation, the Lie algebra of the BF theory isnot restrained to sl(2,R). This relation depends on the sign of the the parameter ?. If? < 0, let ` = 1/???, and define A? = A? ? `?1B?, where A? is the even form field on M?corresponding to A, and B? is the odd form field on M? corresponding to B. ThenIBF[A,B]M =kBF4pi?M?Tr{`4(A+ ?A?) ? (dA+ + dA?) +`8(A+ ?A?) ? (A+ +A?) ? (A+ +A?)+`24(A+ ?A?) ? (A+ ?A?) ? (A+ ?A?)}=`kBF16pi?M?Tr{A+ ? dA+ +23A+ ?A+ ?A+ ?A? ? dA? ?23A? ?A? ?A?}=12(ICS[A+]M? ? ICS[A?]M?)(2.25)652.3. Relation with the BF theory and 3D gravitywhere ICS[A?]M? is the Chern-Simons actionkCS4pi?M? Tr{A? ? dA? + 23A? ?A? ?A?}, andthe coupling constants of the two theories are matched by kCS = `kBF/2. It is well-knownthat the Chern-Simons theory is topological [59], so from this relation it is clear that theBF theory is topological too. Because A? is an even 1-form field and B? is an odd 1-formfield, A? can not take arbitrary values. Rather, they must satisfy??A+(x?) = A?(x?), (2.26)where ? is the involution defined in Section 2.3.1. By this parity condition, A? is determinedby A+. In fact, one can see thatICS[A?]M? = ?ICS[A+]M? . (2.27)The action of BF theory is re-expressed simply asIBF[A,B]M = ICS[A+]M? . (2.28)This is an exact equivalence between the BF theory on M and the Chern-Simons theoryon the orientable double cover M? , which is a very well understood theory. Properties ofthe BF theory on the left-hand side of (2.28), such as its gauge symmetry, classical modulispace, and quantization schemes, can be read off directly from the Chern-Simons theory onthe right-hand side of (2.28).On the other hand, if ? > 0, we can let ` = 1/??, and define C = A?+ i`?1B?. ThenIBF[A,B]M =kBF4pi?M?Tr{`4i(C ? C?) ? (dC + dC?) +`8i(C ? C?) ? (C + C?) ? (C + C?)+`24i(C ? C?) ? (C ? C?) ? (C ? C?)}=`kBF16ipi?M?Tr{C ? C +23C ? C ? C ? C? ? dC? ?23C? ? C? ? C?}=12i(ICS[C]M? ? ICS[C?]M?)(2.29)where the coupling constants of the two theories are again matched by kCS = `kBF/2. Thegauge group of the right hand side theory is GC, which is some group with algebra gC,662.4. The mapping class groupwhich in turn is the complexification of g. However, the parity conditions on A? and B? areequivalent to the following condition on C,??C(x?) = C?(x?). (2.30)Note that this does not imply the C field is real. Rather, this is a constrained Chern-Simonstheory. The gauge transformations are parameterized by a GC-valued function gC(x?),C ?(gC)?1dgC +(gC)?1CgC (2.31)Gauge transformations consistent with the parity conditions are of the form??gC(x?) = Z(x?)gC?(x?), (2.32)where Z(x?) belongs to the center of GC. As in (2.6), here the classical moduli space isHom(pi1(M?), GC)/adGC with the constraintexp(??C)= exp(???C?). (2.33)Existing quantization methods of Chern-Simons theory [59,61,63,95?98] can still be applied,but the constraint (2.30) or (2.33) restricts the phase space that will be so quantized.2.4 The mapping class groupIn this section, we review some basic properties about the mapping class group, whichwill be needed in the following sections.2.4.1 MCG on orientable manifoldsFor an orientable manifold M without boundary, the mapping class group (MCG) isdefined asMCG(M) = Diff+(M)/Diff+0 (M), (2.34)672.4. The mapping class groupFigure 2.1: The map T constructed for defining the Dehn twist.where Diff+(M) is the group of orientation-preserving diffeomorphisms on M , and Diff+0 (M)is the connected component of the identity in Diff+(M). This definition thus can also bewritten asMCG(M) = pi0(Diff+(M)). (2.35)Elements of the MCG are called mapping classes.A closed curve is a continuous map S1 ? M . A closed curve in a manifold M issimple if it is embedded, i.e., if the map S1 ?M is injective.We consider a special type of mapping class known Dehn twists, because of the followingtheorem known as the Dehn-Lickorish Theorem [99?101] : For the genus g surface withg ? 0, the group MCG(?g) is generated by finitely many Dehn twists about nonseparatingsimple closed curves.A Dehn twist is constructed as follows (see Figure 2.1). Let A be the annulus A =S1 ? [0, 1], and let T : A? A be the ?twist map? given byT (?, t) = (? + 2pit, t).Let M be a manifold and ? be a simple closed curve in M . Let N be a regular neighborhoodof ?. We can define a homeomorphism ? : A? N . The Dehn twist about ? is defined asT?(x) =???? ? T ? ??1(x), if x ? N,x, if x ?M\N.It can be shown that the mapping class of T? does not depend on the choice of N and thechoice of ?. Moreover, the mapping class of T? does not depend on the choice of ? withinits homotopy class a. Thus Ta is a well-defined element in MCG(M).682.4. The mapping class group(a) (b)Figure 2.2: The effect of a Dehn twist on a closed curve. The annulus in Figure 2.1 isembedded between the two green lines. The closed curve is shown as the blue directedloop. (a) and (b) show the curve before and after the Dehn twist operation, respectively.The effect of a Dehn twist can be quantified by its action on the isotopy classes of simpleclosed curves (see Figure 2.2). A Dehn twist can be represented by a simple closed curve?. Another simple closed curve ? is twisted by the Dehn twist by the following convention:after performing the Dehn twist, ? is turned to the left at the point where it intersects withthe representative curve ? of the Dehn twist, and goes along ?, until it comes back to theintersecting point and continues its original path.Due to the Dehn-Lickorish Theorem, we can constrain ourselves to only study the gener-ating set of Dehn twists, and the relations that they must satisfy in a specific presentation.One of the most convenient explicit presentation of MCG(?g) is given by Wajnryb [102].The form of the presentation splits into three cases: g = 1, g = 2, and g ? 3. As a conse-quence, we shall discuss the quantization of these three cases in Section 2.5.2, Section 2.5.3and Section 2.5.4, respectively, and we shall give the presentations in their respective sec-tions.692.4. The mapping class groupSD?(a)SDy?(b)Figure 2.3: The map y constructed for defining the Y -homeomorphism. The Mo?bius stripS is represented by a rectangle, with its left side and right side identified along the magentadirected lines. The disc D is shown in grey color, and the green dashed arrows show itsmovement direction by the isotopy map ft. The curve ? is shown in blue color. The mapy maps the configuration shown in (a) to the configuration shown in (b).2.4.2 MCG on non-orientable manifoldsFor a non-orientable manifold M without boundary, the MCG is defined slightly differ-ently than (2.34) asMCG(M) = Diff(M)/Diff0(M), (2.36)where Diff(M) is the group of diffeomorphisms on M , and Diff0(M) is the connected com-ponent of the identity in Diff(M).On non-orientable manifolds, in addition to the Dehn twists, there is another elementarytype of mapping class called Y -homeomorphisms, or crosscap slides. The mapping can beconstructed as follows (see Figure 2.3). Let S be a Mo?bius strip, and D be a disc in S.There is an isotopy map ft on S such that ft|?S = 1, f0 = 1, and f1 |D is an orientation702.5. Quantization of U(1) CST on orientable manifoldsreversing homeomorphism of D. Intuitively, ft can be viewed as a ?slide? of D throughS while fixing ?S, and f1 is when D travels around a circle and overlaps with its originalposition. Let L be another Mo?bius strip. There is a homeomorphism g : L? L such thatg|?L is orientation reversing. As an example of g, if we represent L as a rectangle with theleft side and right side identified (same as the representation of S in Figure 2.3(a)), then gcan be defined as the map that vertically reflects the rectangle. Now glue L around ?D toS ?D, and call this space Y . Define the homeomorphism y : Y ? Y by y??S?D = f1??S?D,y??L = g. For example, the curve ? in Figure 2.3, which connects two points on ?S, ismapped to y?, which is not isotopic to ?. Thus y is a nontrivial mapping class on the spaceY .Let M be a non-orientable manifold. If a subspace N of M is homeomorphic to Y viathe map ? : Y ? N , the Y -homeomorphisms isyN (x) =???? ? y ? ??1(x), if x ? N,x, if x ?M\N.As the Dehn twist, this is a well-defined element in MCG(M).The analog of the Dehn-Lickorish theorem for non-orientable manifolds is still true[103,104]: The MCG on a non-orientable manifold without boundary is generated by finitelymany Dehn twists and Y -homeomorphisms.2.5 Quantization of U(1) CST on orientable manifoldsIn this section, we consider the problem of quantization of U(1) CST on orientablemanifolds. In the last two decades, several different ways to quantize CST has been stud-ied [59, 61?63, 95?98, 105, 106], which have impact on diverse areas in mathematics andphysics. The path-integral approach [59, 61] shed light on the relation between Chern-Simons theory, knot invariants and conformal field theory. Geometric quantization [95] gavea three-dimensional covariant formalism of the quantization. Canonical quantization canbe performed using either a real polarization [62], or a complex polarization and coherent712.5. Quantization of U(1) CST on orientable manifoldsstates [63,105], and a general theory has been developed using quantum groups [96?98,106].The example of Chern-Simons theory with a U(1) gauge group is particularly tractablein that quantization can be done explicitly. When the spacetime manifold has the productform M = R ? ?, with R the time and ? a two-dimensional orientable surface, explicitwave-functions are obtained [107,108] and are identified with the generating functionals forthe current correlator blocks of c = 1 rational conformal field theories [107].Our goal in this section is to examine the role of the MCG of the orientable surfacein quantizing U(1) CST. We shall demonstrate that the MCG is quantizable and we shallfind its representation explicitly [2]. Quantization with a finite dimensional Hilbert space ispossible only when the parameter k = kCS in the Chern-Simons action (2.37) is a rationalnumber [80, 109]. In [80, 107, 109], when k = p/q with p and q coprime, it was statedthat p (or k in [107]) must be an even integer. Our results differ qualitatively from thesequantizations and depend on the genus. When the genus is one (? is the 2-torus), k canbe any rational number. For higher genus, one of p or q must be even. Moreover, byincorporating MCG, we find that for a given k, the representations of the holonomy groupand the large gauge transformation (LGT) group become unique, and the representationfor MCG is also unique, apart from an arbitrary unitary sub-representation which acts onthe holonomy group and LGT group trivially.Generally, at the classical level, when ? has genus g, the group of large gauge trans-formations is Z2g. We find that, commensurate with results of Ref. [107], this discretegroup is realized undeformed at the quantum level only when k is an integer. However,even in that case, we find that, augmenting the quantization with the requirement thatthe Hilbert space carries a unitary representation of the MCG, restricts the representationof the LGTs to those where states are strictly invariant, i.e., theta angles associated withlarge gauge transforms vanish. Furthermore, we shall show that when k is rational but notinteger-valued, the discrete group of LGTs, which was abelian at the classical level, obtainsa 2-cocycle and becomes a clock algebra [80,109]. We find an interesting new result, wherein there exists a k ? 1/k duality of the representations of the homology group and the722.5. Quantization of U(1) CST on orientable manifoldslarge gauge group which, with the restrictions on k stated above, is compatible with ourquantization of the MCG.In a topological field theory, where the action does not depend on the metric, one mayask how the quantization of the MCG could be an issue at all. This is because in order to docanonical quantization, we must choose a set canonical variables, and to quantize, we mustfurther choose a polarization. It is the latter which is not generally covariant. Covariancethen needs to be restored by quantizing the MCG. As we shall show, the quantization ofthe MCG is non-trivial and, as we have discussed above, it can only be carried out withsome restrictions on k and even then it poses restrictions on certain parameters which arisenaturally in the quantization of the theory. See also [77, 110], where the question whetherthe MCG should be included in the quantization of CST, and its possible impacts, arediscussed.To avoid possible confusion, the notation conventions used in this section (Section 2.5)and the next section (Section 2.6) are listed on page xii.2.5.1 General formalismThe action of CST with the U(1) gauge group simplifies from that in (2.1) toICS[A] =k4pi?MA ? dA, (2.37)and the gauge transformation simplifies from that in (2.3) toA? A+ g?1dg, (2.38)where g is a U(1)-valued function. We shall consider the Hamiltonian approach on a 3-manifold M = R ? ? where R is time and ? is a closed, oriented 2-manifold. The 1-formfield A defined on M can be decomposed as A = At+A?, with At the temporal componentand A? the components on ?. The decomposition of the CST action can be written asICS[A] =k4pi?M(A? ? dtA? + 2At ? d?A?) (2.39)732.5. Quantization of U(1) CST on orientable manifoldswhere dt and d? are the exterior differentiation operators on R and ? respectively. Inthe above action, At acts as a Lagrange multiplier and enforces the constraint that theconnection on ? is flat, F?.= d?A? = 0. In the meantime, At is integrated over. Becauseonly A? appears in the analysis below, for simplicity, we use A to denote A? from now on.By Hodge decomposition, any 1-form field A can be written asA = dU + d?V + hwhere d? is the adjoint to d, U is a 0-form, V is a 2-form, h is a harmonic 1-form, and U, V, hare all u(1)-valued. By the equation of motion dA = 0, because d2U = 0 and dh = 0,it follows that V = 0. Because any u(1)-valued function can be continuously deformedto zero, the term dU can be eliminated by a small gauge transformation. There are stilllarge gauge transformations to consider, which have gauge function with nonzero windingnumber around some non-trivial loop. To be explicit, for the genus g orientable surface ?g,we can take a set of generators of the fundamental group ??n, ??n, n = 1, . . . , g, such that#(??n, ??m) = 0,#(??n, ??m) = 0,#(??n, ??m) = ?n?m, where #(, ) is the algebraic intersectionnumber between two loops. Then there is complete basis of harmonic 1-forms ??n, ??n,such that???n??m =???n??m = ?n?m,???n??m =???n??m = 0, which implies????n ? ??m = ?n?m,????n ? ??m =????n ? ??m = 0. (2.40)Since now the field A only has the harmonic part,A =g?n=1(an??n + bn??n). (2.41)For N?n, N?n ? Z, gauge transformations of the gauge functiong(x) = exp[ g?n=1i2pi(N?n? xx0??n +N?n? xx0??n)]commute with the small gauge transformations, and are called large gauge transformations.Effectively they translate the variables an, bn by multiples of i2pi. They form the abeliangroup Z2g.742.5. Quantization of U(1) CST on orientable manifoldsSubstituting (2.41) into (2.39), the action reduces toICS =k4pi?dt??g?n=1(an??n + bn??n)? ?tg?n=1(an??n + bn??n)=k2pi?dtg?n=1an?tbn.where (2.40) is used from the first line to the second line. According to the canonicalquantization recipe, at this point, there is some freedom in choosing the canonical coordinateand momentum. We will use a real polarization here, in that bi and k2piai are taken as thecanonical variables, with the commutation relation [an, bn] = ?i2pik , and any other pairscommute.We shall require the quantum states to transform under LGTs covariantly.Generatorsof LGTs can be written as ?n = exp(kan) and ?n = exp(kbn). From the commutator of anand bn, we can find they satisfy the relation?n?n = ?n?n exp(k2[an, bn]) = ?n?n exp (?i2pik) . (2.42)This is called the clock algebra. When k is not integer-valued, this is a deformed version ofthe classical commutation relation between ?n and ?n. As a side note, it seems natural tointerpret this deformation of algebra as a quantum effect: if one requires the quantum statesto form a representation of the original undeformed classical algebra, then k is quantizedto be integer-valued. We will not make such requirement in this section, and our resultsapply to the case of integer-valued k as a special case.Aside from carrying a representation of the above clock algebra, a quantum statealso stores information that is invariant under LGT. The invariant subspace of the phasespace is a 2g-dimensional torus, parameterized by generators of the holonomy group ?n =exp(???nA)= exp(an) and ?n = exp(???nA)= exp(bn). The non-trivial relation is an-other clock algebra?n?n = ?n?n exp(?i2pik). (2.43)These two clock algebras (2.42) and (2.43) can be regarded as being dual to each other,with duality transformation k ? 1/k. Note that these two sets of operators commute. For752.5. Quantization of U(1) CST on orientable manifoldsexample, ?n?n = ?n?n exp(?i2pi). Thus they realize the statement that on the classicallevel holonomies are invariant under LGTs.Since both the LGT group and the holonomy group need to be represented in quan-tization, and there exists the above interesting duality transformation between them, welike to treat these two groups on an equal footing. This is another reason why k is notrestrained to be integer-valued. There is no obvious reason to insist that the holonomygroup is un-deformed, so by (2.43), 1/k does not need to integer-valued. To exploit theduality, it is better to allow non-integer-valued k as well.To quantize the theory, we shall look for representations of the algebras (2.42) and (2.43),as well as of the MCG with appropriate induced action on (2.42) and (2.43), so that thequantum states form the left modules of the representations. Because the algebras (2.42)and (2.43) commute with each other, we can look for representations for them separately,and the complete representation is a tensor product.2.5.2 Quantization on ?1 = T 2Now we proceed to quantize the theory on a torus. We will use the following topologicalrelations. For a torus, the fundamental group pi1(T 2) is abelian and generated by two loops??, ??, with ???? = ????. The MCG of the torus, MCG(T 2) is generated by a pair of Dehntwists, A,B, which can be presented in Figure 2.4 as the loops A,B. The MCG generatorsact on the the fundamental group generators asA(??, ??) =(??, ????), (2.44a)B(??, ??) =(???1??, ??). (2.44b)This group is actually SL(2,Z), so the relations areABA = BAB, (2.45a)(BAB)4 = 1. (2.45b)Let us consider the representation of holonomy group first. This group is generated762.5. Quantization of U(1) CST on orientable manifoldsAB??Figure 2.4: Fundamental group generators and MCG generators for ?1. The fundamentalgroup generators are denoted by oriented loops with single thin lines, and labeled by Greekletters; the MCG generators are the unoriented loops with double lines, and labeled byRoman letters.by ? and ? with ?? = ????1, where ? = exp(i2pik). We first look for the irreduciblerepresentation of this clock algebra.If ?? and ?? form a representation of the clock algebra, and ?? is diagonal, their componentssatisfy??ij ??j = ??i??ij??1.So if ??ij is nonzero, ??i = ???j . A general solution can be written as?? =????????Id0?Id1. . .?p?1Idp?1????????ei??, ?? =????????0 ??0,p?1??10 0. . . . . .??p?1,p?2 0????????ei??,where di is the size of each block, and ??i,i?1 is di?di?1 dimensional. But ?? can be unitaryonly if d0 = d1 = ? ? ? = dp?1 = d. While fixing ??, the allowed unitary transformations have772.5. Quantization of U(1) CST on orientable manifoldsthe form U = diag{U0, . . . , Up?1}, andU?1??U =????????0 U?10 ??0,p?1Up?1U?11 ??10U0 0. . . . . .U?1p?1??p?1,p?2Up?2 0????????ei??.We can take all the Ui?s to be the same, but perform such unitary transformation p times.One of the ??i,i?1?s can be diagonalized each time. Finally we get a reducible representationunless d = 1.So in the (not necessarily irreducible) representation where ? is diagonal, ?, ? has theblock-diagonal form: (From here on, index of every series starts from 0.)? = diag{??(k, ??0 ), . . . , ??(k, ??r?1)}, ? = diag{??(k, ??0 ), . . . , ??(k, ??r?1)}, (2.46)where each block forms irreducible representation and is determined by two parameters??(k, ??) =????????1?. . .?p?1????????ei??, ??(k, ??) =????????0 11 0. . . . . .1 0????????ei??, (2.47)where ? = exp(i2pik), k = p/q with p, q coprime, and each block in ?, ? is p?p dimensional.Note that after taking ? to be diagonal, there still remains some unitary transformationon these matrices: while keeping the above form, we can do a cyclic permutation of basis,which changes ?? by a multiple of 2pip , and we can shift the phases of the set of basis,which changes ?? by a multiple of 2pip . Thus using this unitary transformation, the phaseparameters can be restricted as ??, ?? ? [0, 2pip ).Next, we find the representations for the MCG generators, whose operation on theholonomies is derived from their classical operation (2.44). The relations that A shouldsatisfy areA??A = ?, A??A = exp(b+ a) = ????1/2. (2.48)782.5. Quantization of U(1) CST on orientable manifoldswhere a and b are the coefficients in (2.41) (the subscript is omitted because it can only be1). To solve these equations, we decompose A into r ? r blocks of p ? p elements as theholonomies. If we focus on the (m,m)-th block of (2.48), we find that the solution is givenbyAmm = uAmmA?(k, ??m, ?A), (2.49)where uAmm is a complex number, and the components of the p? p matrix A? are given byA?(k, ??m, ?A)ij =1?p??(i?j)2/2ei(i?j)??mei?A. (2.50)The parameter ?A, which does not depend on the block indexm, is redundant, because it canbe absorbed into uAmm. We keep this seemingly redundant parameter in order to make surethat the matrices A? and B? can form a representation of the MCG (see below). In addition,(2.50) solves the equations (2.48) provided it is periodic with respect to the two indices.Changing i from 0 to p in A?ij gives the condition ??p2/2eip??m = exp[i2pi(?pq/2+p??m/2pi)] =1. This means if p or q is even, then ??m are multiples of2pip ; if p, q are both odd, then ??mare multiples of 2pip pluspip . On the other hand, we knew 0 ? ??m <2pip , so ??m?s are uniquelydetermined by k,??m =pip??, ? =???0, p or q even,1, p and q odd.(2.51)After fixing the value of ??m, we can solve for all blocks of A, and the solution isAmn = uAmnA?(k,pi?p, ?A). (2.52)In other words, the representations have the form? = I ? ??(k,pi?p), ? = I ? ??(k,pi?p),A = UA ? A?(k,pi?p, ?A), (2.53)where UA is any unitary matrix.For B, the conditions areB??B = ??1??1/2, B??B = ?. (2.54)792.5. Quantization of U(1) CST on orientable manifoldsThe solution isBmn = uBmnB?(k, ??n, ?B), (2.55)where the components of the p? p matrix B? are given byB?(k, ??n, ?B)ij = ?i2/2eii??n?i?jei?B .By the same periodicity argument, we have??n = ??n =pip??, ? =???0, p or q even,1, p and q odd.(2.56)Therefor, B also has the formB = UB ? B?(k,pi?p, ?B). (2.57)Because the MCG of T 2 is SL(2,Z), its generators A,B should satisfy the relationsABA = BAB, (BAB)4 = 1. Because of the redundant parameters ?A and ?B, we can requirethat the two parts of direct production in (2.53) and (2.57) satisfy the relations separately.So UA and UB are generators of an arbitrary unitary representation of the MCG. A? andB? are specified by the parameters ?A and ?B, and we need to check how the relationsABA = BAB, (BAB)4 = 1 constrain these parameters. For the first relation ABA = BAB,the right hand side is(B?A?B?)ij =1?p?i2/2+j2/2?(i?j)2/2ei(i+j)pi?/p+i(i?j)pi?/pei(2?B+?A) =1?p?ijei2ipi?/pei(2?B+?A),and the left-hand side of (2.45a) is(A?B?A?)ij =1pp?1?l=0??(i+j?l)2/2?ijei(i?j+l)pi?/pei(2?A+?B)=1pp?1?l=0??l2/2?ijei(l+2i)pi?/pei(2?A+?B)=1pp?1?l=0??l2/2+?l/2q?ijei2ipi?/pei(2?A+?B).802.5. Quantization of U(1) CST on orientable manifoldsComparing the two sides, we find a condition for ?A, ?Bei(?B??A) =1?pp?1?l=0exp(ipi(?ql2 + ?l)p). (2.58)The right-hand side is a quadratic Gauss sum, for which the summation could be analyti-cally performed. The exact expression will not be presented here. The important fact is,this equation is satisfiable for all possible p and q?s (p, q odd, or p even q odd, or p odd qeven). It can be checked that the two sides always have the same abstract values, and thephases can be matched by the yet-unknown ?A and ?B.For the second relation (BAB)4 = 1,(B?A?B?)ij =1?p?ijei2ipi?/pei(2?B+?A),((B?A?B?)2)ij =1pp?1?l=0?il?ljei(2i+2l)pi?/pei2(2?B+?A)=?(q(i+j)+?) mod pei2ipi?/pei2(2?B+?A),((B?A?B?)4)ij =?(i?j)e?i2pi?q?/pei4(2?B+?A),where q? satisfies qq? ? 1 (mod p). So we get the another condition on ?A, ?Be?i2pi?q?/pei4(?A+2?B) = 1. (2.59)The two conditions (2.58) and (2.59) will determine ?A and ?B up to 12 choices, but differentchoices are equivalent. Actually, if ?A and ?B are a set of solution, then ?A+n2pi12 and ?B+n2pi12also solve (2.58) and (2.59). The difference between these two set of solutions is nothingbut an abelian representation of the MCG, so it can be absorbed into UA and UB.We still need to find representation for the dual clock algebra (2.42) for LGTs andrepresentation for the action of MCG to the LGTs. But these are exactly the same algebrasas those solved above, except k is replaced by 1/k, or equivalently, p, q are exchanged. Thusthe irreducible unitary representation for the dual clock algebra is q-dimensional, phaseparameters ??n and ??n are uniquely determined to bepiq ??, and counterparts of (2.58) and(2.59) give some solution to the phase parameters ??A and ??B. The full representation for812.5. Quantization of U(1) CST on orientable manifoldsthe algebras is? = Ir ? ?? (k, pi?/p)? Iq, ? = Ir ? ?? (k, pi?/p)? Iq,? = Ir ? Ip ? ?? (1/k, pi?/q) , ? = Ir ? Ip ? ?? (1/k, pi?/q)A = UA ? A?(k, pi?/p, ?A)? A?(1/k, pi?/q, ??A), B = UB ? B?(k, pi?/p, ?B)? B?(1/k, pi?/q, ??B),(2.60)where Id is the d? d identity matrix.Generalizing the work of [107], in this section, the value of k is not restricted after impos-ing MCG. However, representing the MCG still affects the representation of the holonomygroup and the LGT group, because in this process, the phase parameters ??n and ??n aredetermined as in (2.56), which are otherwise free to change within [0, 2pip ), and ??n, ??n arerestricted similarly.2.5.3 Quantization on ?2We now consider quantization of CST on a genus two surface ?2. The relevant topo-logical properties of ?2 are the following. The fundamental group of ?2 has 4 generators??1, ??1, ??2, ??2 with one relation ???11 ??1??1???11 ???12 ??2??2???12 = 1. The MCG of ?2, MCG(?2), isgenerated by five Dehn twists, A1,B1,A2,B2,S, as are drawn in Figure 2.5. Their operationon the loops are derived to beA1(??1, ??1, ??2, ??2) = (??1, ??1??1, ??2, ??2), (2.61a)B1(??1, ??1, ??2, ??2) = (???11 ??1, ??1, ??2, ??2), (2.61b)A2(??1, ??1, ??2, ??2) = (??1, ??1, ??2, ??2??2), (2.61c)B2(??1, ??1, ??2, ??2) = (??1, ??1, ??2???12 , ??2), (2.61d)S(??1, ??1, ??2, ??2) = (??1???11 ??2, ??1, ???12 ??1??2, ??2), (2.61e)822.5. Quantization of U(1) CST on orientable manifoldsA1 A2S1B1 B2?1?1 ?2?2Figure 2.5: Fundamental group generators and MCG generators for ?2. The fundamentalgroup generators are denoted by oriented loops with single thin lines, and labeled by Greekletters; the MCG generators are the unoriented loops with double lines, and labeled byRoman letters.and they satisfy the following relations [111][[A1,A2]] = [[A1,B2]] = [[B1,A2]] = [[B1,B2]] = [[B1, S]] = [[B2,S]] = 1, (2.62a)A1B1A1 = B1A1B1, A2B2A2 = B2A2B2, A1SA1 = SA1S, A2SA2 = SA2S, (2.62b)(B1A1S)4 = B22, (2.62c)[[B2A2SA1B1B1A1SA2B2,B1]] = 1, (2.62d)(B2A2SA1B1B1A1SA2B2)2 = 1. (2.62e)where [[?, ?]] is the group theory commutator defined as [[g1, g2]].= g1g2g?11 g?12 .By the conventions shown in Figure 2.5, with ai =??iA, bi =??iA, the Chern-Simonsaction isICS =k2pi?dt(a1?tb1 + a2?tb2)which results in the commutators[a1, b1] = [a2, b2] =?i2pik832.5. Quantization of U(1) CST on orientable manifoldsand any other pair commutes.As in section 2.5.2, let us only consider representation of the holonomy group for now.From the above commutation relations, the holonomy group generators satisfy the clockalgebra,?1?1 = ?1?1??1, ?2?2 = ?2?2??1, (2.63)and any other pair commutes. Similar to section 2.5.2, we have the following equations forthe MCG generators,B?1?1B1 = ??11 ?1?1/2, B?2?2B2 = ?2?2?1/2, A?1?1A1 = ?1?1??1/2, A?2?2A2 = ?2??12 ??1/2,and they commute with the rest of the holonomy group generators.The equations we have listed so far are just two copies of their counterparts in section2.5.2, so the solution of the generators is just a direct product of the solutions in section2.5.2,?1 = Ir ? ??1, ?2 = Ir ? ??2, ?1 = Ir ? ??1, ?2 = Ir ? ??2,B1 = UB1 ? B?1, B2 = UB2 ? B?2, A1 = UA1 ? A?1, A2 = UA2 ? A?2,(2.64)where??1 = ?? (k, pi?/p)? Ip, ??2 = Ip ? ?? (k, pi?/p) ,??1 = ?? (k, pi?/p)? Ip, ??2 = Ip ? ?? (k, pi?/p) ,B?1 = B?(k, pi?/p, ?B1)? Ip, B?2 = Ip ? B?(k, pi?/p, ?B2),A?1 = A?(k, pi?/p, ?A1)? Ip, A?2 = Ip ? A?(k, pi?/p, ?A2).The new generator S is determined by the equationsS??1S = ?1??11 ?2??1/2, S??2S = ??12 ?1?2?1/2, S??1S = ?1, S??2S = ?2.The solution isS = US ? S?(k, ?S),whereS?(k, ?S)i1j1,i2j2 = ?(i2?i1)2/2?i1?j1?i2?j2ei?S .842.5. Quantization of U(1) CST on orientable manifoldsThis matrix is periodic only if one of p, q are even, that is, ? = 0. This is a non-trivial?quantization condition? for k on ?2. One can see that if we restrict k to be integer-valued,then this condition agree with that in ref. [107], which is that k must be an even integer.Now we check the relations (2.62a)-(2.62e). Equation (2.62a) is automatically satisfied;(2.62b) gives the same equation as (2.58) except now ? = 0,ei(?B1??A1 ) = ei(?B2??A2 ) = ei(?S??A1 ) = ei(?S??A2 ) =1?pp?1?l=0exp(?ipiql2p)(2.65)which means ?A1 = ?A2 , ?B1 = ?B2 = ?S, and the two angles ?A1 and ?B1 are related by thisequation. So there is really only one free angle parameter left. Consider the relation(2.62c),((B?1A?1S?)2)i1j1,i2j2 =?i1+j1?j2?i2?j2??j1j2+j22ei2(?B1 +?A1 +?S)((B?1A?1S?)4)i1j1,i2j2 =?i1?j1?i2?j2?j22ei4(?B1 +?A1 +?S).Equating this with (B22)i1j1,i2j2 givesei4(?B1 +?A1 +?S)?i2?B2 = 1 (2.66)and this will fix all the angles up to 10 choices. Next consider the relation (2.62d),(B?2A?2S?A?1B?1)i1j1,i2j2 =1p?i1j1?i1j2+i2j2ei(?A1 +?A2 +?B1 +?B2 +?S)(B?2A?2S?A?1B?1B?1A?1S?A?2B?2)i1j1,i2j2 =?i1+j1?i2+j2ei2(?A1 +?A2 +?B1 +?B2 +?S)It can be checked now that this matrix commutes with B?1. Multiplying B?1 from left orfrom right just adds the factor ?i21/2 or ?j21/2, respectively, and they are the same becauseof the first delta function. So the relation (2.62d) poses no condition on the angles. Thelast relation (2.62e) is((B?2A?2S?A?1B?1B?1A?1S?A?2B?2)2)i1j1,i2j2 = ?i1?j1?i2?j2ei4(?A1 +?A2 +?B1 +?B2 +?S)soei4(?A1 +?A2 +?B1 +?B2 +?S) = 1 (2.67)852.5. Quantization of U(1) CST on orientable manifoldsGiven (2.65) and (2.66), this condition is also redundant. The nontrivial conditions are(2.65) and (2.66), and they have 10 distinct solutions, which are equivalent because thedifference between the solutions are merely an abelian representation of the MCG.By repeating the above calculation with k replaced by 1/k, we can obtain the repre-sentation for the dual algebra satisfied by LGT generators. In particular, the quantizationcondition for k, which is that one of p, q must be even, is symmetric with respect to p andq, so the dual algebra will not give additional restriction on k.2.5.4 Quantization on ?g, g ? 3For higher genus surfaces, the fundamental group and MCG of ?g with g ? 3 have thefollowing presentation. The fundamental group pi1(?g) is generated by 2g loops ??1, . . . , ??g, ??1, . . . , ??g,with one relation ???11 ??1??1???11 ? ? ? ???1g ??g??g???1g = 1. For g ? 3, MCG have 2g + 2 genera-tors, which are An, n = 1, . . . , g, Sn, n = 1, . . . , g, and Bn, n = 1, 2, as shown in Fig.2.6. Anexplicit presentation of MCG is given in [102]. It takes the following form in our convention[[C,C?]] = 1, when #(C,C ?) = 0, (2.68a)CC?C = C?CC?, when #(C,C ?) = ?1, (braid relation),(2.68b)(S1A1B1)4 = E0B2, (3-chain relation),(2.68c)E2E1B2 = E3S2S1B1, (lantern relation),(2.68d)[[AgSg?1Ag?1 ? ? ? S1A1B1B1A1S1 ? ? ?Ag?1Sg?1Ag,Bg]] = 1, (hyperelliptic relation),(2.68e)862.5. Quantization of U(1) CST on orientable manifolds. . .A1 A2 A3 AgS2S1 S3 Sg-1B1 B2Figure 2.6: MCG generators for ?g, g ? 3.where the conventional names of the last four relations are also from [102], andE0 =(A2S1A1B1B1A1S1A2)B2(A2S1A1B1B1A1S1A2)?1,E1 =(A2S2S1A2)?1B2(A2S2S1A2),E2 =(A1S1B1A1)?1E1(A1S1B1A1),E3 =(A3S2A2S1A1UB?11 A?11 S?11 A?12 )B2(A3S2A2S1A1UB?11 A?11 S?11 A?12 )?1,U =(A3S2)?1E?11 (A3S2),and Bn+2 is computed from Bn,Bn+1 and the generators by inductionBn+2 = WnBnW?1n , (2.69)whereWn = (AnSnAn+1Bn+1)(Sn+1An+2An+1Sn+1)(SnAn+1AnSn)(Bn+1An+1Sn+1An+2).The holonomy group is generated by 2g generators ?n, ?n, n = 1, ldots, g, and theysatisfy the clock algebra in pairs. Representation of the 2g + 2 MCG generators can alsobe derived from their actions on the holonomies. The result is?n = Ir ? ??n, ?n = Ir ? ??n,An = UAn ? A?n, Sn = USn ? S?n, Bn = UBn ? B?n,872.5. Quantization of U(1) CST on orientable manifoldswhere??n = I?n?1p ? ??(k, 0)? I?g?np , (2.70a)??n = I?n?1p ? ??(k, 0)? I?g?np , (2.70b)A?n = I?n?1p ? A?(k, 0, ?An )? I?g?np , (2.70c)S?n = I?n?1p ? S?(k, 0, ?Sn)? I?g?n?1p , (2.70d)B?n = I?n?1p ? B?(k, 0, ?Bn )? I?g?np . (2.70e)In this process, we get the same quantization condition on k, which is one of p, q must beeven.We still need to make sure the relations (2.68a)-(2.68e) are satisfied. Equation (2.68a)is trivially satisfied. The braid relations (2.68b) give as before?An = ?A, ?Bn = ?Sn = ?B, ei(?B??A) =1?pp?1?l=0exp(?ipiql2p)(2.71)There leaves only one undetermined phase in the MCG generators. The 3-chain relation(2.68c) is(S1A1B1)4 = (A2S1A1B1B1A1S1A2)B2(A2S1A1B1B1A1S1A2)?1B2Note that every element in this relation has the same form as in the previous section, sothose results can be used. From (2.62d), we know that [[A2S1A1B1B1A1S1A2,B2]] = 1.By conjugation and commutation, this 3-chain relation (2.68c) reduces to the previouslyproven relation (2.62c), (B1A1S1)4 = B22. Regarding the lantern relation (2.68d)E2E1B2 = E3S2S1B1,after some calculation, we find(E?2E?1B?2)i1j1,...,igjg =?j21+j22+j23?j1j2?j2j3ei3?B?i1?j1?i2?j2?i3?j3 ? ? ?(E?3S?2S?1B?1)i1j1,...,igjg =?j21+j22+j23?j1j2?j2j3ei4?B?i1?j1?i2?j2?i3?j3 ? ? ?882.5. Quantization of U(1) CST on orientable manifoldsso ?B = 0. This fixes the remaining freedom in the MCG generators. To check the hyper-elliptic relation (2.68e),[[AgSg?1Ag?1 ? ? ? S1A1B1B1A1S1 ? ? ?Ag?1Sg?1Ag,Bg]] = 1,by (2.69), we find that B?n takes the form of (2.70e) for all n, and(A?gS?g?1A?g?1 ? ? ? S?1A?1B?1B?1A?1S?1 ? ? ? A?g?1S?g?1A?g)i1j1,...,igjg = ?i1+j1 ? ? ? ?ig+jgeig(?A+?B)Obviously this commutes with B?g.As in the previous section, representation of the dual clock algebra gives no additionalquantization condition on k.2.5.5 DiscussionTo summarize our results [2], in this section, we found that the U(1) Chern-Simonstheory defined on R ? ?g is quantizable, if we required the quantum states to form rep-resentations for the deformed holonomy group, the deformed LGT group, and the MCG.Explicit, finite dimensional representations of these groups were found. The parameter kwas quantized as follows: on the torus ?1, k can take any nonzero rational value, howeverfor ?g with g ? 2, k must be a rational number with either its numerator or denomina-tor being even. The representations are unique in the sense that, apart from a choice ofarbitrary unitary representation of the MCG, the representations of the discrete groups(holonomy group + LGT group + MCG) are completely fixed.The uniqueness of the representation of these discrete groups is an interesting result.In general, when one considers gravity with some non-trivial space-time topology, it isexpected that some theta angle parameters, or more complicated non-abelian parameters,will arise. But in our toy model, which can be regarded as three dimensional Chern-Simonsgravity with gauge group U(1) instead of some non-abelian gauge group [70], although sometheta angle parameters appear in representation of the clock algebra, they disappear afterrepresenting the MCG.892.5. Quantization of U(1) CST on orientable manifoldsThe representations of the discrete groups on ?g are found to be r(pq)g dimensional,where r is the dimensionality of an arbitrary unitary representation of the MCG, andk = p/q with p, q coprime. This can be compared with the result of the path-integralquantization in Ref. [107], which studied the special case of k being integer-valued. If wetake r = 1 and k integer-valued, it is easy to check that, the kg dimensional dimensionalrepresentation of the holonomy group from this work is exactly the same representationformed by states in the kg dimensional Hilbert space found in Ref. [107](see Equation (23)and (24) therein). As a consequence, the representations of MCG in this work and that inRef. [107] are also the same.The r(pq)g dimensional Hilbert space that we find can be viewed as a direct productof g (pq)-dimensional subspaces, and one r-dimensional subspace. Each (pq)-dimensionalsubspace is associated with one specific handle on ?g, and the r-dimensional subspace formsan extra representation of the MCG. Due to this tensor product structure, we can considerpinching of the handles, in which some handles are shrank to marked points. Because thequantization condition on k is stronger for g ? 2 than for g = 1, i.e., an allowed k valueon a higher genus surface will not pose any problem on a lower genus surface. Withoutloss of generality, assume the first handle is pinched. The holonomy around the remainingmarked points is ?1?1??11 ??11 , which is the constant number exp(? i2pik)by Equation (2.43).This means in a quantum state, after the pinching, all information about holonomies of thefirst handle is lost. The same is true for information about LGTs, with the same reason.Thus the (pq)g-dimensional subspace becomes (pq)g?1 dimensional after pinching. For ther-dimensional subspace, the situation is more complicated. In general, representations ofthe MCG of higher genus surface does not reduce to representations of MCG of lower genussurface with marked points, so if pinching is allowed, there may be some extra conditionson the r-dimensional representation of the MCG.As shown previously in Section 2.5.2, 2.5.3 and 2.5.4, to impose the large gauge symme-try and large diffeomorphisms, it is impossible to simply reduce the original classical phasespace to some invariant subspace of these symmetries. However, it is straightforward, at902.6. Quantization of U(1) BF theory on non-orientable manifoldsleast classically, to find the invariant phase space under one of the two symmetries. In fact,we chose to represent the large gauge symmetry first, and as a result the b1(?g)-dimensionalquantum plane, where b1 is the first Betti number, reduces to a b1(?g)-dimensional torustimes a Zb1(?g) lattice, both of which are deformed by the canonical commutator to non-commutative spaces. Wave functions take values on these two parts of phase space sep-arately. Then the implementation of MCG gives some non-trivial and rather technicalrestrictions on the parameters of the theory, as were listed above.In principle, the other way around, i.e., to impose MCG first should be equally tractable.Indeed, the invariant subspace is the moduli space of Teichmu?ller space of ?g, and wavefunctions are sections based upon this moduli space. But presently it is not clear how thewave functions can carry a representation of the large gauge transformations.2.6 Quantization of U(1) BF theory on non-orientablemanifoldsWith the results from Section 2.3, we can apply the same methodology in Section 2.5to the case of non-orientable manifolds, on which a single CST is not well-defined, but theBF theory is well-defined.The question of quantizing BF theory on non-orientable manifolds has been studiedin [89], which is for the case of ? being the Klein bottle, and the gauge group is taken tobe the 2 + 1 dimensional Poincare? group IO(2, 1), to match with the corresponding 2 + 1dimensional gravity theory with vanishing cosmological constant. In that paper, it is foundthat the classical solution space of this model splits into seven components. Four of thecomponents correspond to non-degenerate metrics, and in particular for one componentthe Klein bottle metric is space-like. Thus quantization on this component will lead to areasonable quantization of 2+1 dimensional gravity on Klein bottle.In this section, the quantization will be studied for arbitrary non-orientable surfaces,and explicit quantum states can be found, as long as the explicit presentation of the MCG912.6. Quantization of U(1) BF theory on non-orientable manifoldsis known. As in Section 2.5, we shall take the gauge group to be U(1) for simplicity; theLGT group and holonomy group are required to have projective representations, and theMCG is required to have (non-projective) representations.2.6.1 General formalismTo find an analogous model with the orientable case we studied before, we consider theBF theory (2.15) with gauge group U(1). With this Abelian gauge group, (2.15) simplifiestoI =k2pi?R?NB ? dA (2.72)where k = kBF0, B is a 1-form-density U(1) gauge field, and A is a regular 1-form U(1) gaugefield. By decomposing the fields into time-like components and space-like components, theaction becomesI =k2pi?N?R(By?tAx ?Bx?tAy +BtFAxy +AtFBxy)(2.73)where FAxy =(ddxAy ?ddyAx)dx ? dy, FBxy =(ddxBy ?ddyBx)dx ? dy. By imposing thegauge fixing conditions At = 0, Bt = 0, and regarding A and B as forms on 2-manifold, theconstraint equation is dA = 0, dB = 0 (A,B closed). Any classical solution thus can bedecomposed asA =dU +?ai?iB =dV +?bi?i(2.74)where {?i}({?i}) is a complete basis of harmonic 1-forms (1-form densities).The topology of a non-orientable compact surface is specified by the non-orientablegenus g, and we denote the surface by Ng. The orientable double cover of Ng is the genusg orientable compact surface ?g. Generators of pi1(?g) can be taken as ?i, ?i, i = 1, . . . , g,such that #(?i, ?j) = 0,#(?i, ?j) = 0,#(?i, ?j) = ??i?j , where #(, ) is the algebraicintersection number between two loops. Each loop corresponds to exactly a harmonic form??i, ??i, such that??i??j =??i??j = ?i?j ,??i??j =??i??j = 0. From these harmonic922.6. Quantization of U(1) BF theory on non-orientable manifoldsforms on ?g, one can construct the corresponding harmonic forms and densities on Ng.Forms of the form ??i + ??g+1?i and ??i ? ??g+1?i are even forms; ??i ? ??g+1?i and??i + ??g+1?i are odd forms. When g is odd, ??(g+1)/2 is even, and ??(g+1)/2 is odd. Theharmonic forms and densities we found above should be complete, because it can be shownany harmonic form or density on Ng induce a harmonic form on ?g, and there are 2gharmonic forms on ?g, while we already found g harmonic forms and g harmonic densitieson Ng. Using these explicit harmonic forms on Ng, we obtain the symplectic structure ofthe phase space.The reduced phase space is spanned by ai, bi in (2.74). To account for the LGTs, insteadof quantizing the u(1)-valued coordinates ai, bi, we quantize the U(1)-valued holonomies (seeSection 2.5.1)?? = exp(???A), ??? = exp(???B), (2.75)and the U(1)-valued LGT generators?? = exp(k???A), ??? = exp(k???B). (2.76)Classically, the holonomy group and the LGT group formed from these generators areabelian. After quantization however, these two groups are deformed to be non-abelian dueto the canonical commutators. Still, these two groups commute with each other, so we cantreat with them separately. Their representations are related by the duality transformationk ? 1/k. In addition, we require the quantum states to form (un-deformed) representationsof the MCG. MCG elements operate on the loops in a definite way, thus their operationson the holonomies and LGTs can be derived accordingly.The MCG of the Klein bottle MCG(N1) was found to be Z2 ? Z2 in [103]. It wasshown in [112] that the MCG of an non-orientable surface can be derived from its orienteddouble cover, and an explicit presentation of MCG(N2) was derived there. In Ref. [113]an algorithm was devised to provide an explicit presentation of the MCG for any non-orientable surface, and this was applied to N3 in [114]. However, the resulting presentationof MCG(N3) is quite complicated, and we shall not calculate the representation of this932.6. Quantization of U(1) BF theory on non-orientable manifoldsgroup in the quantization of BF theory. Beyond N3, no explicit presentation is presentlyknown.2.6.2 N1, Klein bottleFor the Klein bottle N1, the fundamental group is generated by two loops ??, ??, withthe relation ?????????1 = 1. It has 1 even harmonic form ?1 = ??1 and 1 odd harmonic form?1 = ??1, so we define two holonomies? = e??? A = ea, ? = e??? B = eb. (2.77)From [b, a] = ?i2pik , we obtain the clock algebra?? = ????1 (2.78)The MCG of the Klein bottle is generated by two elements, a Dehn twist A and across-cap slide Y. These operations act on the loops ??, ?? as [103]:A(??, ??) =(??, ????) (2.79a)Y(??, ??) =(???1, ??) (2.79b)It can be checked that A2 = 1,Y2 = 1,AY = YA, which confirms the MCG is Z2 ? Z2.The induced operations on the holonomies areA?(?, ?)A =(?, ?), (2.80a)Y?(?, ?)Y =(??1, ?). (2.80b)Note that although the Dehn twist A maps the loop ?? to ????, the holonomies are not affectedby the operator A. Thus A is just the identity operator, up to a unitary representation UAof the element A in Z2 ? Z2.Because Equation (2.78) is identical to Equation (2.43), the holonomies ? and ? havethe same block-diagonal form,? = diag{??(k, ??0 ), . . . , ??(k, ??r?1)}, ? = diag{??(k, ??0 ), . . . , ??(k, ??r?1)}, (2.81)942.6. Quantization of U(1) BF theory on non-orientable manifoldswith ??,?i ? [0,2pip ).To solve the equations Y??Y = ?,Y??Y = ??1, we decompose Y into r ? r blocks ofp ? p element as the holonomies. Substituting (2.81) into (2.80b), we find that a solutionexists only if p = 1 or 2, and when p = 1 or 2, the expression for each block of Y is simplyYmn = umnY? = umnIp,where uYmn is complex number. Because Y? = Ip does not depend on the indices m,n, Y canbe written as the tensor product form Y = UY ? Ip, where UY is a unitary matrix.The conditions A2 = 1,Y2 = 1,AY = YA are trivially satisfied. Note that in this case of? = N1, ??,?i is not fixed by the MCG.The representations for the LGT group is just the dual of the representation of theholomony group, with p? q. Thus q can also only take value 1 or 2, i.e., k is quantized tobe 1/2, 1 or 2. The full representation of these discrete groups is? = U? ? ??(k, 0)? Iq, ? = U? ? ??(k, 0)? Iq,? = U? ? Ip ? ?? (1/k, 0) , ? = U? ? Ip ? ?? (1/k, 0) ,A = UA ? Ip ? Iq, Y = UY ? Ip ? Iq,(2.82)where UA and UY form a unitary representation of the generators of the MCG Z2 ? Z2,U?, U? are diagonal unitary matrices such that(UA)?(U?, U?)UA = (U?, U?)(UY)?(U?, U?)UY = ((U?)?1, U?),and similarly for U?, U?.2.6.3 N2According to the general formalism in Section 2.6.1, the closed 1-form A and the closed1-form density B on N2 can be decomposed asA =dU + a1(??1 + ??2) + a2(??1 ? ??2),B =dV + b1(??1 + ??2) + b2(??1 ? ??2),952.6. Quantization of U(1) BF theory on non-orientable manifoldsand thus the canonical commutators are [b1, a1] = [a2, b2] = ?i2pik . We define the holonomiesas?1 = e???B = eb2 , ?1 = e??? A = ea2 ,?2 = e??? A = ea1 , ?2 = e??? B = eb1 .(2.83)Then again we find the clock algebra ?n?n = ?n?n?, n = 1, 2. The clock algebra represen-tation can be written as?1 =diag{??(k, ??10 )? Ip, . . . , ??(k, ??1r?1)? Ip}?1 =diag{??(k, ??10 )? Ip, . . . , ??(k, ??1r?1)? Ip}?2 =diag{Ip ? ??(k, ??20 ), . . . , Ip ? ??(k, ??2r?1)}?2 =diag{Ip ? ??(k, ??20 ), . . . , Ip ? ??(k, ??2r?1)}The MCG generators act on the loops as [112]A(??, ??) =(??, ????),B(??, ??) =(???1??, ??),Y(??, ??) =(???1, ??),and they have the relations ABA = BAB, (BAB)4 = 1,Y2 = 1,YAY = A?1,YBY = B?1.Their induced operations on holonomies areA?(?1, ?1, ?2, ?2)A =(?1, ?1?2, ?2, ?2?1),B?(?1, ?1, ?2, ?2)B =(??12 ?1, ?1, ??11 ?2, ?2),Y?(?1, ?1, ?2, ?2)Y =(??11 , ?1, ??12 , ?2).To find representations of the MCG, we again decompose A,B and Y into r ? r blocks ofp? p elements. Let us first focus on the (m,m)-th block. Amm and Bmm have the solutionBmm =uBmmB?(k, ??1m , ??2m , ?B),Amm =uAmmA?(k, ??1m , ??2m , ?A),whereB?(k, ??1m , ??2m , ?B)i1j1,i2j2=??i1i2e?i(i1??2m +i2??1m )?i1?j1?i2?j2ei?BA?(k, ??1m , ??2m , ?A)i1j1,i2j2=1d?(i1?j1)(i2?j2)e?i[(i1?j1)??2m +(i2?j2)??1m ]ei?A962.6. Quantization of U(1) BF theory on non-orientable manifoldsThe unitarity of A? and B? enforces that d = p, and the periodicity of A? and B? enforces that??1m , ??2m , ??1m , ??2m are all multiples of 2pi/p, so we can take them all to be 0. Note that unlikethe case of ? = ?2, in this process the value of k is not restricted. After fixing these phaseparameters, it is then straightforward to solve for all blocks of A,B,B =UB ? B?(k, 0, 0, ?B),A =UA ? A?(k, 0, 0, ?A),where UB and UA are arbitrary r-dimensional unitary matrices.The relation ABA = BAB gives ?A = ?B. Note that in this case no quadratic Gauss sumis involved in the equation. The relation (BAB)4 = 1 gives ei12?B= 1.However, when solving for Y, it turns out that solution exists only if p = 1 or 2, andY = ?Ip ? Ip, ?A = ?B = 0 or pi. As the previous cases, these choices of phases canbe absorbed into the abelian representation of the MCG, which leaves the part of MCGrepresentation that interacts with the holonomy group trivial when p = 1, andB? =????????1 0 0 00 1 0 00 0 1 00 0 0 ?1????????, A? =12????????1 1 1 ?11 1 ?1 11 ?1 1 1?1 1 1 1????????, Y? =????????1 0 0 00 1 0 00 0 1 00 0 0 1????????when p = 2.As for the representation of LGT and the part of MCG interacting with LGT, the sameresult can be found, with p ? q. Thus when ? = N2, the quantization condition for k isthat k can take value among 1/2, 1 and 2.2.6.4 DiscussionTo summarize the results in this section, we applied the formalism developed in Sec-tion 2.3, and quantized U(1) BF theory defined on R?Ng, where Ng is the non-orientablesurface whose orientable double cover is ?g. In this process, the holonomy group and theLGT group are deformed according to the canonical commutation relation, while the MCG972.6. Quantization of U(1) BF theory on non-orientable manifoldsis not deformed. For the cases g = 1, 2, for which explicit, tractable presentations of MCGare known, we found explicit, finite dimensional representation of the discrete groups. Inorder to consistently quantize the system, k are restricted to be either 1/2, 1 or 2. For theKlein bottle N1, the phase parameters associated the holonomy group generators and theLGT group generators are not totally fixed by the value of k; for the non-orientable surfaceN2, similar with the cases of orientable surfaces ?g, these phase parameters are fixed by k.For higher g, because no tractable presentation of the MCG is known, the representationsof the MCG have not been calculated. However, if we do not require that the MCG ispromoted into quantum operators, then the representations of the holonomy group and theLGT group can be directly generalized to cases of higher g.Similar with the comments in Section 2.5.5, for U(1) BF theory defined on R?Ng, onecan consider pinching of the topological structures, because the representations that wefound have tensor product structure; because the phase parameters are fully fixed for thecase of N2, it is interesting to consider the implication on a quantum gravity model definedon R?N2.In addition, we note that the quantum states on the non-orientable manifolds are notsimply the quantum states on the oriented double cover with the correct parity. For ex-ample, on N1 and N2, when k does not take value among 1/2, 1 or 2, there is no quantumstate consistent with a representation of the MCG, while on ?1 and ?2, k can take anyrational value with the numerator or the denominator being even, and quantum states withany parity can be constructed. This extra restriction on k is due to non-trivial effects fromthe quantization of the MCG. In particular, in the calculation in Section 2.6.3, representingthe Dehn twists A and B does not introduce this extra quantization condition. It is onlywhen we calculate the representation of the Y -homeomorphism Y that the quantizationcondition appears.98Chapter 3Future directions3.1 Introduction: finite size scaling of systems withfirst-order phase transitionIn Chapter 1, the finite size scaling (FSS) method is applied to the numerical resultof the graph model. In Figure 1.10, the inverse transition temperature is plotted as afunction of system size NV , from which it is derived that the transition temperature inthe thermodynamic limit is zero. Moreover, the energy distributions of different NV ?sare plotted in Figure 1.11. Given enough numerical data, in principle how the energydistribution depends on NV , i.e., a FSS model of the distribution, can be deduced. Sucha FSS model can facilitate our understanding of the macroscopic properties of the graphmodel.More generally, the FSS method is a very useful tool in understanding results fromphysics systems with finite sizes. A phase transition is only strictly well-defined in thethermodynamic limit, for which the system size is infinite. For a finite size system, which isusually studied numerically, the free energy in the canonical ensemble is an analytic functionof the temperature. In addition to smoothing out the singularities at transition, finite sizescan also affect other observed quantities non-trivially. The FSS method extrapolates theresults with different finite sizes, and thus can make predictions in the thermodynamiclimit.For systems with second-order transition, the FSS method is particularly powerful (see,e.g., [28]). Near a second-order transition point, the correlation length ? diverges in thethermodynamic limit, but with a finite size, it is bounded above by L, which is the typical993.2. Physics models and numerical resultslength the finite size. From this observation, it can be derived how other diverging quantitiesdepend on L, and then the critical exponents can be determined by fitting the numericalresults.Systems with first-order transition on the other hand do not show such universality, andas a consequence, there are more open questions regarding how FSS should be performed.In this chapter, we will consider a wide range of the statistical models, including the Pottsmodel [115], a structure-based model for protein folding known as the Go? model [116,117],and the graph model in Chapter 1 [1], all of which possess a first-order phase transition.We will attempt to find FSS models for these models. If for such a diverse set of models,there are some common features in the FSS models, then these features will likely hold truefor other physics models.3.2 Physics models and numerical resultsIn this section, the definitions of the three physics models are reviewed, and for eachmodel, numerical simulations are performed in preparation for FSS.3.2.1 The Potts modelThe Potts model [115] is a generalization of the Ising model. (For a review of the Pottsmodel, see [118].) In the Ising model, at each site, the spin has two possible states, while inthe Potts model, each spin can take q different states. The Hamiltonian of the Potts modelisH = ?J??ij???i,?j , (3.1)where the summation is over all adjacent pairs of spins, ?i denotes the spin at site i, ? isthe Kronecker delta function, and J is the coupling constant.The Potts model possesses a phase transition between a high temperature, disorderedphase and a low temperature, ordered phase. In the following, this transition will be studiedon a two-dimensional square lattice. In this setup, the transition is second-order for q ? 4,1003.2. Physics models and numerical resultsand first-order for q > 4 [119]. The transition temperature is given by [119]Tc =JkB[ln(1 +?q)]?1. (3.2)In our simulations, the finite systems are taken to have size L?L, with periodic bound-ary conditions. The transition temperature Tc(L) for a finite system is defined to be thetemperature that maximizes the heat capacity C = T?2(?E2?? ?E?2).For L = 10, 15, 20, 30, 40, 50, 60 and 70, the (rescaled) energy distribution at Tc(L)is shown in Figure 3.1(a), and ?E? /L2 and C/L4 are plotted as functions of ??L2 =[T?1 ? (Tc(L))?1]L2 in Figure 3.1(b) and (c), respectively. As L increases, the curvesin Figure 3.1(b) and (c) converges. This is actually true for any extensive system withfirst-order transition, because in the thermodynamic limit, the energy density distributionalways becomes the sum of two delta functions, and the curves plotted in Figure 3.1(b) and(c) become two universal curves.3.2.2 Structure-based model for protein foldingNumerical simulations of protein folding is a challenging problem. Compared with thosederived from first principles, structure-based models for protein folding [120] are easier toimplement. In structure-based models, the native state, i.e., the properly folded, functionalstate, of a protein is used in constructing the Hamiltonian, such that the native state is theglobal energy minimum.The Go? model [116, 117] is one of the structure-based models for protein folding. Inthis model, hydrogen atoms are ignored. Each heavy atom is represented by a bead ofunit mass and radius rb. Two atom are called ?in contact? if: 1. there are at least threeresidues between these two atoms; 2. in the native state, the two atoms are within thecutoff distance rc; 3. in the native state, there is no atom between the two atoms spatially.1013.2. Physics models and numerical results?1 ?0.9 ?0.8 ?0.7 ?0.6 ?0.5 ?0.4 ?0.3 ?0.2024681012E/2L2P(E/2L2) L=10L=15L=20L=30L=40L=50L=60L=70(a)?15 ?10 ?5 0 5 10 15?2?1.8?1.6?1.4?1.2?1?0.8?0.6?? ? L2?E(?)?/L2 1015203040506070(b)?15 ?10 ?5 0 5 10 1500.050.10.150.20.250.30.35?? ? (L2)C(?)/(L2 )2 1015203040506070(c)Figure 3.1: Simulation results of the Potts model. (a) The energy distributions at Tc(L);(b) the rescaled energy expectation value as a function of ?? ? L2. (c) the rescaled heatcapacity as a function of ?? ? L2.1023.2. Physics models and numerical resultsThe Hamiltonian isH =?bonds\u000Fr(r ? r0)2 +?angles\u000F?(? ? ?0)2 +?improper/planar\u000F?(?? ?0)2+?backbone\u000FBBFD(?) +?sidechains\u000FSCFD(?)+?contacts\u000FC[(?ijr)12? 2(?ijr)6]+?non-contacts\u000FNC(?NCr)12(3.3)whereFD = [1? cos(?? ?0)] +12[1? cos(3(?? ?0))]and \u000Fr = 100, \u000F? = 20, \u000F? = 10, \u000FNC = 0.01, and ?NC = 2.5A?. r0, ?0, ?0 and ?ij are givenby the values measured in the native state. We take rb = 1.0A? and rc = 6.0A?. The bonds,angles, improper/planar, backbone and sidechains that are summed over are all identifiedin the native state, and appropriate potentials are associated with them to favor the nativestate geometry. A Lennard-Jones potential is added to a pair of atoms that are in contact.Finally, a repulsive power-12 potential is assigned to a pair of atoms that are neither bondednor in contact. See [116,117] for more details.Simulations are performed for eight two-state folders, i.e., proteins that have only twodistinct macroscopic states. The rescaled energy distributions at the transition temperatureare shown in Figure 3.2(a). The rescaled energy expectation value and the rescaled heatcapacity are shown in Figure 3.2(b) and (c) as functions of ??L = [T?1 ? T?1c ]L, whereL is the number of amino acids in the protein, and Tc is defined for each protein as thetemperature that maximize the heat capcity.3.2.3 The graph model of emergent manifoldThe graph model of emergent manifold is defined in Chapter 1. For the three largestsizes NV = 1000, 1500 and 2000, the energy distributions at the transition temperature areplotted in Figure 1.11. The energy expectation value and heat capacity as functions of?? ?NV = [T?1 ? (Tc(NV ))?1]NV are plotted in Figure 3.3.1033.2. Physics models and numerical results15 20 25 3000.10.20.30.40.50.60.7E/Lp(E/L) 1pgb1shg1bdd1lmb1hrc256b1e651lop(a)?10 ?5 0 5 1016182022242628?? ? L?E(?)?/L 1pgb1shg1bdd1lmb1hrc256b1e651lop(b)?10 ?5 0 5 1000.511.522.533.5?? ? LC(?)/L2 1pgb1shg1bdd1lmb1hrc256b1e651lop(c)Figure 3.2: Simulation results for the protein folding model. (a) The rescaled energydistributions at the transition temperature; (b) the rescaled energy expectation value as afunction of ?? ? L. (c) the rescaled heat capacity as a function of ?? ? L.1043.2. Physics models and numerical results?15 ?10 ?5 0 5 10 1500.20.40.60.811.21.4?? ? NV?E(?)?/NV 100015002000(a)?15 ?10 ?5 0 5 10 1500.10.20.30.40.50.60.7?? ? NVC(?)/N2 V 100015002000(b)Figure 3.3: Simulation results of the graph model. (a) the rescaled energy expectationvalue as a function of ?? ?NV . (b) the rescaled heat capacity as a function of ?? ?NV .1053.3. Finite size scaling models3.3 Finite size scaling modelsIn this section, we will test a series of FSS models on the above physics models. EachFSS model is motivated by features of some physics model near the transition point.3.3.1 Sum of two Gaussian functionsIn [121], near the transition temperature of a first-order phase transition, the energydistribution is modeled by the sum of two Gaussian functions, and this FSS model is testedfor the Potts model described in section 3.2.1. This form of energy distribution can bemotivated as follows. When the system size is large enough, the phase-coexisting statescan be ignored (see also the capillarity model in Section 3.3.4). For a state composed ofone phase, the correlation length of the field is finite, and the system can be viewed asbeing composed of independent sub-systems. When the system size is large enough, andconsequently the number of sub-systems is large enough, by the central limit theorem, thetotal energy distribution approaches a Gaussian distribution. Near the transition tempera-ture, states of either phase can be observed in the thermodynamic ensemble, so the energydistribution is taken to be the sum of two Gaussian functions.The energy distribution at Tc is assumed to be,P (e, Tc) = A{exp[?(e? e1)2V2T 2c c1]+ exp[?(e? e2)2V2T 2c c2]}, (3.4)where V is the volume of the system, e = E/V is the intensive energy, and e1,2 and c1,2are volume-independent constants. The two Gaussian functions have the same amplitude,because at Tc, the two phases have the same intensive free energy.At a different temperature, the distribution isP (e, Tc+?T ) ' A(?T ){a1c1/21exp[?(e? (e1 + c1?T ))2V2T 2c c1]+a2c1/22exp[?(e? (e2 + c2?T ))2V2T 2c c2]}(3.5)where A(?T ) is the normalization factor, a1 = c1/21 eX , a2 = c1/22 e?X ,X =(e1 ? e2)?TV2T 2c. (3.6)1063.3. Finite size scaling modelsand terms of order (?T/T )2 are ignored.The following thermodynamic quantities can be computed,?E? = V ?a1(e1 + c1?T ) + a2(e2 + c2?T )a1 + a2(3.7)?E2?= V 2[a1(e1 + c1?T )2 + a2(e2 + c2?T )2a1 + a2+T 2cVa1c1 + a2c2a1 + a2](3.8)C '1T 2c(?E2?? ?E?2)= V ?a1c1 + a2c2a1 + a2+ V 2 ?a1a2 [e1 ? e2 + (c1 ? c2)?T ]2T 2c (a1 + a2)2. (3.9)If c1,2 = 0, i.e., and the energy distribution is the sum of two delta functions, then ?E?and C obey simple universal scaling laws, which is observed and tested numerically for thePotts model in [121]. If we keep c? nonzero, there is no simple universal scaling laws for?E? and C.Figure 3.4 shows the fitting results for the Potts model, which become better for largersystem sizes. As can be seen from this figure, the energy distribution of one phase is notleft-right symmetric, and the probability between the two Gaussian peaks are too large tobe fitted well by the Gaussian functions. In Section 3.3.2 and Section 3.3.4, two improvedFSS models are proposed to address these issues.It turns out that this FSS model works very well for the results of the protein foldingmodel. The fittings to the energy distributions are plotted in Figure 3.5(a), and values ofthe fitting parameters are shown in Figure 3.5(b). From Figure 3.5(b), one can see thatalthough e1 and e2 vary for different proteins, the quantities e2 ? e1 is relatively morestable, and thus can be used for extrapolation. c1 and c2 for different proteins also havefairly constant values. The fluctuation of these parameters among different proteins isnatural, because different proteins have distinct structures.3.3.2 Exponential of degree-4 polynomialWhen the system size is not very large, the energy distribution of one phase is notnecessarily Gaussian. In this sub-section, a heuristic generalization to the two-Gaussian1073.3. Finite size scaling models?1 ?0.9 ?0.8 ?0.7 ?0.6 ?0.5 ?0.4 ?0.3 ?0.2024681012E/2L2P(E/2L2) L=10 dataL=10 fitL=15 dataL=15 fitL=20 dataL=20 fitL=30 dataL=30 fitL=40 dataL=40 fitL=50 dataL=50 fitL=60 dataL=60 fitL=70 dataL=70 fitFigure 3.4: The Potts model WHAM results, and the best fit lines using the sum of twoGaussian functions1083.3. Finite size scaling models15 20 25 3000.10.20.30.40.50.60.7E/Lp(E/L) 1pgb data1pgb fit1shg data1shg fit1bdd data1bdd fit1lmb data1lmb fit1hrc data1hrc fit256b data256b fit1e65 data1e65 fit1lop data1lop fit(a)50 100 150 2000.50.520.540.560.580.6A50 100 150 200181920212223e150 100 150 2002.42.62.833.2 x 10?3 c150 100 150 2002021222324e250 100 150 2001.522.5 x 10?3 c250 100 150 20011.522.533.5e2?e1(b)Figure 3.5: (a) The protein WHAM results, and the best fit lines using the sum of twoGaussian functions. (b) The values of the parameters of the best fit lines as functions ofthe length of the protein. 1093.3. Finite size scaling modelsmodel, which replace the distribution of one phase by an exponential of degree-4 polynomial,is considered:P4(x+ x0) = N4 exp(?x2c2?sx3c3?kx4c4). (3.10)where x0, c, s and k are parameters, N4 is the normalization factor, c has the same di-mensionality as x, s and k are dimensionless, and they are named for their relations tothe skewness and kurtosis of this distribution. The physical reason to use this functionalform is the following. Value of the energy distribution function can change by several or-ders of magnitude from its minimum to maximum, while the free energy of each energylevel, which is proportional to the logarithmic of the energy distribution function, typicallychanges within the same order of magnitude. For one phase, there is an energy with min-imal free energy, and in this FSS model, the free energy as a function of energy is Taylorexpanded around this energy up to the fourth power.Now we apply this fitting function to the Potts model. Let x = E/2L2. We assumethat the energy distribution takes the formPPotts(x) = A1P4(c1, s1, k1;x+ e1) +A2P4(c2, s2, k2;x+ e2). (3.11)The fitting results are shown in Figure 3.6(a), and the values of the parameters are shownin Figure 3.6(b). It can be seen that this functional form can fit the data very well. Inaddition, all the parameters show smooth trends as functions of L. We can in principlefit the parameter functions with appropriate functional forms, and use them to predictthe energy distribution at other system sizes. However, unlike the two-Gaussian model, inwhich the parameters are taken to be L-independent, it is not clear what functional formsshould be used to fit the parameters s1,2 and k1,2 as functions of L.3.3.3 A distribution concentrated near its lower boundFor the graph model, neither the Gaussian function nor Equation (3.10) can fit thedistribution of the low temperature phase, because this distribution is concentrated aroundthe lower bound E = 0. The distribution of one phase is thus assumed heuristically to take1103.3. Finite size scaling models?1 ?0.9 ?0.8 ?0.7 ?0.6 ?0.5 ?0.4 ?0.3 ?0.2024681012E/2L2P(E/2L2) L=10 dataL=10 fitL=15 dataL=15 fitL=20 dataL=20 fitL=30 dataL=30 fitL=40 dataL=40 fitL=50 dataL=50 fitL=60 dataL=60 fitL=70 dataL=70 fit(a)10 20 30 40 50 60 700.480.50.520.540.56A110 20 30 40 50 60 70?0.865?0.86?0.855?0.85?0.845?0.84?0.835?0.83e110 20 30 40 50 60 700.020.040.060.080.10.12c110 20 30 40 50 60 70?0.6?0.5?0.4?0.3?0.2s110 20 30 40 50 60 700.020.040.060.080.10.120.14k110 20 30 40 50 60 700.440.450.460.470.480.490.50.51A210 20 30 40 50 60 70?0.48?0.46?0.44?0.42?0.4?0.38e210 20 30 40 50 60 700.020.040.060.080.1c210 20 30 40 50 60 700.20.250.30.350.4s210 20 30 40 50 60 7000.020.040.060.080.1k2(b)Figure 3.6: (a) The WHAM results of energy distribution of the Potts model, with L =10, 15, 20, 30, 40, 50, 60 and 70, and the best fit lines using the distribution (3.11). (b) Thevalues of the parameters of the best fit lines as functions of L. 1113.3. Finite size scaling modelsthe formPe(x) = Ne exp [s exp(?cx)? bx] , x ? [0,?), (3.12)where c, b and s are parameters, and Ne is the normalization factor. The full energydistribution of graph model is fitted by the functionPgraph(x) = A1Pe(s1, c1, b1;x) +A2Pe(c2, s2, k2;x+ e2), (3.13)where x = E/NV , and A1 + A2 = 1. The fitting results are shown in Figure 3.7(a), andthe values of the parameters are shown in Figure 3.7(b). This FSS model can capture theshape of the energy distribution very well. However, because only three different sizes areavailable, additional numerical data are needed to identify the trends of the parameters asfunctions of NV , and to further evaluate this FSS model.3.3.4 A capillarity modelFor a model with first-order transition, a state in the thermodynamic limit is alwayscomposed of one phase. At finite sizes, states with mixed phases can contribute to thepartition function. For the phase-coexisting states, we can use the capillarity theory toanalyze their effects. (See, e.g., [23, 122].)In Monte Carlo simulations, the dynamics of a first-order phase transition can be un-derstood as a nucleation process [23, 122]. Near the transition temperature, starting witha state composed of only one phase, the configuration contains many ?bubbles?, or nu-clei, of the other phase. When a nucleus is small enough, due to the interface tension,the nucleus is not stable, and tends to shrink and disappear. However, with a very smallprobability, a nucleus can also grow large enough and overcome the free energy barrier.Thus in the rare process of one phase turning into the other phase, the intermediate statesare phase-coexisting states, and the interface area between phases is suppressed by theinterface tension. A typical phase-coexisting state of the Potts model with L = 50 is shownin Figure 3.8.1123.3. Finite size scaling models0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.500.511.522.533.54E/NVp(E/N V) NV=1000 dataNV=1000 fitNV=1500 dataNV=1500 fitNV=2000 dataNV=2000 fit(a)1000 1500 20000.40.450.50.550.6A11000 1500 20001.822.22.42.62.8s11000 1500 200020406080100c11000 1500 2000345678910b11000 1500 20000.40.450.50.550.60.650.70.75A21000 1500 20000.70.80.911.1e21000 1500 20000.10.150.20.250.30.350.40.45c21000 1500 20000.40.50.60.70.80.91s21000 1500 20000.050.10.150.20.250.30.350.4k2(b)Figure 3.7: (a) The WHAM results of energy distribution of the graph model, with NV =1000, 1500 and 2000, and the best fit lines using (3.13). (b) The values of the parametersof the best fit lines as functions of NV . 1133.3. Finite size scaling modelsFigure 3.8: A typical phase-coexisting state of the Potts model with L = 50. Differentspin values are denoted by different colors.For a system of volume V , consider a phase-coexisting state which has volumes of thetwo phases V1 and V2, respectively, and the expected interface area A is determined by V1.The entropy of the interface is ignored. Let Tc be the transition temperature in the bulklimit.Assume first that the energy distribution of one phase is a delta function. At Tc, theenergy distribution is the superposition of all possible values of V1,P (E, Tc) =? V0dV1 B(V1)?[E ? (V1e1 + V2e2 +Aea)] (3.14)where e1, e2 are the energy densities of each phase, ea is the interface tension, andB(V1) = B0 exp(?A(V1)ea/Tc). (3.15)This is because compared with the single-phase states, a phase-coexisting state has higherfree energy due to the interface tension, and the amplitude is suppressed by the Boltzmannfactor. If ea = 0, P (E, Tc) is flat between V e1 and V e2. In the limit ea ? ?, P (E, Tc) is1143.3. Finite size scaling modelsthe sum of two delta functions. If we assume the delta function is solved by V? (E), that is,E = V? (E)e1 + (V ? V? (E))e2 + A(V? (E))ea, and assume there is only one solution to thisequation, then (3.14) can be integratedP (E, Tc) =B(V? (E))????e1 ? e2 + eadAdV1???V1=V? (E)????. (3.16)If we keep only the leading order of ea, which is in (3.15), then V? (E) =V e2?Ee2?e1, andP (E, Tc) =B0 exp[?A(V e2?Ee2?e1)ea/Tc]|e2 ? e1|, V e1 ? E ? V e2. (3.17)From this expression, one can see that when V increases while V? (E)/V is fixed, A increasesas V (d?1)/d, and this distribution approaches the sum of two delta functions in the ther-modynamic limit. This confirms the statement that when the system size is large enough,the contribution from the phase-coexisting states can be ignored.Now assume that the variances of energy distribution of the two phase are V ?21 andV ?22, respectively. At Tc, macroscopic states with volume of one phase being any V1 shouldhave the same entropy. The energy distribution of such state is a Gaussian distributionwith mean (V1e1 +V2e2 +Aea), and variance (V1?21 + (V ?V1)?22). The energy distribution(3.14) is generalized toP (E, Tc) =? V0dV1 B(V1)1?2pi?V1?21 + (V ? V1)?22exp[?(E ? (V1e1 + V2e2 +Aea))22(V1?21 + (V ? V1)?22)]=B0?2pi? V0dV11?V1?21 + (V ? V1)?22exp[?(E ? (V1e1 + V2e2 +Aea))22(V1?21 + (V ? V1)?22)?AeaTc](3.18)If ?1 = ?2, this integration can be performed analytically. However, in general, including thecase of the Potts model, ?1 6= ?2, and this integration can only be calculated numerically.For the Potts model at L = 30, the simulation data can fitting relatively well (seeFig. 3.9), with parameters e1 = ?1.72, e2 = ?0.89, ?1 = 1.78, ?2 = 1.53, ea = 0.37, Tc =1.4261, and the area function is taken to be A(V1) = min(?V1,?V ? V1). Compared withthe two-Gaussian model, the addition of the phase-coexisting states contributes to some1153.3. Finite size scaling models?2 ?1.5 ?1 ?0.5 00123456E/L2P(E/L2) L=30 dataL=30 fitL=40 dataL=40 predictionL=50 dataL=50 predictionFigure 3.9: The WHAM result of the Potts model energy distribution for L = 30, 40, 50.For L = 30, the best fit line using (3.18) is shown. Then the values of the fitting parametersfrom L = 30 are used to predict the distributions for L = 40 and 50.additional probability between V e1 and V e2, and can help to explain why the distribution ofone phase has non-zero skewness. In the current FSS model, the values of the parametersshould not scale with L. If the same parameters are used for other sizes, the predicteddistributions do not fit the numerical results well (see Figure 3.9). This indicates that forthe Potts model, there may be other finite size effects that should be incorporated in theFSS model.The dependence of the interface length on the volume of one phase A(V1) was assumedto be A(V1) = min(?V1,?V ? V1) above. The form of A(V1) can also be measured directlyfrom the simulation as follows. For each sample of the Monte Carlo simulation of the Pottsmodel, V1 is measured as the volume of the largest component, where a component is aconnected region with the same spin. A is measured as the length of the interface betweenthe largest component and the rest of the system. For the same value of V1, multiplemeasurements of A are averaged. The result for L = 50 is shown in Figure 3.10, along1163.4. Discussion0 500 1000 1500 2000 2500050100150200250300350400Area of the largest componentAverage length of the interface L=50Figure 3.10: The average interface length is plotted in blue color as a function of the areaof largest component. The three red curves A = 4?V1, A = 4?V ? V1, A = 2?V = 2Lcorrespond to the cases with the ordered phase forming a square region, the complementof a square region, and a cylinder-shaped region.with the three red curves A = 4?V1, A = 4?V ? V1, A = 2?V = 2L, which correspondto the cases with the ordered phase forming a square region, the complement of a squareregion, and a cylinder-shaped region. For intermediate values of V1 (100 < V1 < 2000), theaverage of measured interface length is greater than the smallest of the three cases withregular shapes, which means that for a given V1, the average interface length is greaterthan the smallest possible interface length. This phenomenon can be understood as thatthe interface is frustrated by the entropy associated with it (see also Figure 3.8).3.4 DiscussionIn this chapter, the Potts model, a structure-based model for protein folding, and thegraph model of emergent manifold are considered, and three different fitting functions, as1173.4. Discussionwell as a more physically motivated capillarity model are tested as FSS models. We foundthat to obtain the best fitting result, different physics models need different FSS models.Due to the limitation of available numerical results, the usefulness of these FSS modelremains to be tested on larger system sizes, and on other physics models.We note that the models in Section 3.3.2 and 3.3.4 are both generalizations of the two-Gaussian model in Section 3.3.1. For the Potts model, better fitting result are obtainedwith the generalized models, at the cost of using more fitting parameters. Thus it is aninteresting question whether or not such generalizations actually improve the FSS model.This question can be addressed by considering a set of physics models, and check thestatistical significance of the improvements of the fittings to the numerical results.Another open question is how a different boundary condition (b.c.) can affect the finitesize effects. For the Potts model, the current periodic b.c. can be changed into an openb.c., in which the spins at the boundary have no interaction with the outside, or a closedb.c., in which the spins at the boundary interact with fixed spins in the outside. Amongthese candidates, the periodic b.c. supposedly gives the closest results as the infinite sizesystem. However, the periodic b.c. changes the topology of the system, which can have asignificant effect when using the capillarity model. It is interesting to compare the resultsfrom different b.c.?s, and identify the differences in their finite size effects.118Bibliography[1] S. Chen and S. S. Plotkin, ?Statistical mechanics of graph models and theirimplications for emergent manifolds,? Phys. Rev. D 87, 084011 (2013) ,arXiv:1210.3372 [gr-qc].[2] S. Chen, ?Mapping class group and U(1) Chern-Simons theory on closed orientablesurfaces,? Mod.Phys.Lett. A27 (2012) 1250087, arXiv:1103.2820 [hep-th].[3] P. Erdo?s and A. Re?nyi, ?On random graphs,? Publicationes Mathematicae Debrecen6 (1959) 290?297.[4] G. ?t Hooft, ?A planar diagram theory for strong interactions,? Nucl.Phys. B72(1974) 461.[5] J. Ambj?rn, J. Jurkiewicz, and R. Loll, ?Emergence of a 4-D world from causalquantum gravity,? Phys.Rev.Lett. 93 (2004) 131301, arXiv:hep-th/0404156[hep-th].[6] J. Ambj?rn, J. Jurkiewicz, and R. Loll, ?Reconstructing the universe,? Phys.Rev.D72 (2005) 064014, arXiv:hep-th/0505154 [hep-th].[7] R. Albert and A.-L. Baraba?si, ?Statistical mechanics of complex networks,? Rev.Mod. Phys. 74 (2002) 47?97.[8] D. S. Franzblau, ?Computation of ring statistics for network models of solids,?Phys. Rev. B 44 (Sep, 1991) 4925?4930.119Bibliography[9] U. S. Bhalla and R. Iyengar, ?Emergent properties of networks of biologicalsignaling pathways,? Science 283 no. 5400, (1999) 381?387.[10] J. J. Hopfield, ?Neural networks and physical systems with emergent collectivecomputational abilities,? Proceedings of the National Academy of Sciences 79 no. 8,(1982) 2554?2558, http://www.pnas.org/content/79/8/2554.full.pdf+html.[11] T. Konopka, F. Markopoulou, and L. Smolin, ?Quantum graphity,?arXiv:hep-th/0611197 [hep-th].[12] T. Konopka, F. Markopoulou, and S. Severini, ?Quantum graphity: a model ofemergent locality,? Phys. Rev. D77 (2008) 104029, arXiv:0801.0861 [hep-th].[13] T. Konopka, ?Statistical Mechanics of Graphity Models,? Phys.Rev. D78 (2008)044032, arXiv:0805.2283 [hep-th].[14] A. Hamma, F. Markopoulou, S. Lloyd, F. Caravelli, S. Severini, et al., ?A QuantumBose-Hubbard model with evolving graph as toy model for emergent spacetime,?Phys.Rev. D81 (2010) 104032, arXiv:0911.5075 [gr-qc].[15] F. Caravelli, A. Hamma, F. Markopoulou, and A. Riera, ?Trapped surfaces andemergent curved space in the Bose-Hubbard model,? Phys.Rev. D85 (2012) 044046,arXiv:1108.2013 [hep-th].[16] F. Conrady, ?Space as a low-temperature regime of graphs,? J. Statist. Phys. 142(2011) 898, arXiv:1009.3195 [gr-qc].[17] N. Mermin and H. Wagner, ?Absence of ferromagnetism or antiferromagnetism inone-dimensional or two-dimensional isotropic Heisenberg models,? Phys.Rev.Lett.17 (1966) 1133?1136.[18] P. Hohenberg, ?Existence of Long-Range Order in One and Two Dimensions,?Phys.Rev. 158 (1967) 383?386.120Bibliography[19] S. R. Coleman, ?There are no Goldstone bosons in two-dimensions,?Commun.Math.Phys. 31 (1973) 259?264.[20] A. Malnic? and B. Mohar, ?Generating locally cyclic triangulations of surfaces,? J.Combin. Theory Ser. B 56 no. 2, (1992) 147?164.http://dx.doi.org/10.1016/0095-8956(92)90015-P.[21] M. E. G. Newman and G. T. Barkema, Monte Carlo methods in statistical physics.Clarendon Press, Oxford, 1999.[22] A. M. Ferrenberg and R. H. Swendsen, ?New Monte Carlo technique for studyingphase transitions,? Phys. Rev. Lett. 61 (1988) 2635?2638.[23] S. S. Plotkin and J. N. Onuchic, ?Understanding protein folding with energylandscape theory i: Basic concepts,? Quart. Rev. Biophys. 35 no. 2, (2002) 111?167.[24] S. S. Plotkin and J. N. Onuchic, ?Understanding protein folding with energylandscape theory ii: Quantitative aspects,? Quart. Rev. Biophys. 35 no. 3, (2002)205?286.[25] K. Binder, ?Theory of first-order phase transitions,? Reports on Progress in Physics50 no. 7, (1999) 783.[26] M. Plischke and B. Bergersen, Statistical Physics. World Scientific, Singapore,3rd ed., 2006.[27] E. A. Bender and E. R. Canfield, ?The asymptotic number of labeled graphs withgiven degree sequences,? J. Combinatorial Theory Ser. A 24 no. 3, (1978) 296?307.[28] R. Creswick, H. Farach, and C. Poole, Introduction to renormalization groupmethods in physics. A Wiley-Interscience publication. Wiley, 1992.[29] L. Landau and E. Lifshitz, Statistical physics. Addison-Wesley series in advancedphysics. Pergamon Press, 1958.121Bibliography[30] D. Weingarten, ?EUCLIDEAN QUANTUM GRAVITY ON A LATTICE,?Nucl.Phys. B210 (1982) 229.[31] F. David, ?Planar Diagrams, Two-Dimensional Lattice Gravity and SurfaceModels,? Nucl.Phys. B257 (1985) 45.[32] J. Ambjorn, B. Durhuus, and J. Frohlich, ?Diseases of Triangulated RandomSurface Models, and Possible Cures,? Nucl.Phys. B257 (1985) 433.[33] V. Kazakov, A. A. Migdal, and I. Kostov, ?Critical Properties of RandomlyTriangulated Planar Random Surfaces,? Phys.Lett. B157 (1985) 295?300.[34] D. Boulatov, V. Kazakov, A. A. Migdal, and I. Kostov, ?POSSIBLE TYPES OFCRITICAL BEHAVIOR AND THE MEAN SIZE OF DYNAMICALLYTRIANGULATED RANDOM SURFACES,? Phys.Lett. B174 (1986) 87?93.[35] D. Johnston, ?Gravity and random surfaces on the lattice: A Review,?Nucl.Phys.Proc.Suppl. 53 (1997) 43?55, arXiv:hep-lat/9607021 [hep-lat].[36] M. J. Bowick, ?Random surfaces and lattice gravity,? Nucl.Phys.Proc.Suppl. 63(1998) 77?88, arXiv:hep-lat/9710005 [hep-lat].[37] P. Di Francesco, P. H. Ginsparg, and J. Zinn-Justin, ?2-D Gravity and randommatrices,? Phys.Rept. 254 (1995) 1?133, arXiv:hep-th/9306153 [hep-th].[38] A. M. Polyakov, ?Quantum Geometry of Bosonic Strings,? Phys.Lett. B103 (1981)207?210.[39] D. Oriti, The Group field theory approach to quantum gravity. Cambridge UniversityPress, 2006. arXiv:gr-qc/0607032 [gr-qc].[40] D. Oriti, ?A Quantum field theory of simplicial geometry and the emergence ofspacetime,? J.Phys.Conf.Ser. 67 (2007) 012052, arXiv:hep-th/0612301 [hep-th].122Bibliography[41] A. U?ngo?r, ?Tiling 3D Euclidean space with acute tetrahedra,? in Proc. of the 13thCanadian Conference on Computational Geometry, pp. 169?172. 2001.[42] J. Q. Quach, C.-H. Su, A. M. Martin, and A. D. Greentree, ?Domain structures inquantum graphity,? Phys.Rev. D86 (2012) 044001, arXiv:1203.5367 [gr-qc].[43] F. Markopoulou and L. Smolin, ?Disordered locality in loop quantum gravitystates,? Class.Quant.Grav. 24 (2007) 3813?3824, arXiv:gr-qc/0702044 [gr-qc].[44] L. Pauling, ?The structure and entropy of ice and of other crystals with somerandomness of atomic arrangement,? J. Am. Chem. Soc. 57 (1935) 2680?2684.[45] P. W. Anderson, ?Ordering and antiferromagnetism in ferrites,? Phys. Rev. 102(May, 1956) 1008?1013. http://link.aps.org/doi/10.1103/PhysRev.102.1008.[46] S. T. Bramwell and M. J. P. Gingras, ?Spin ice state in frustrated magneticpyrochlore materials,? Science 294 no. 5546, (2001) 1495?1501,http://www.sciencemag.org/content/294/5546/1495.full.pdf.[47] F. Caravelli and F. Markopoulou, ?Properties of Quantum Graphity at LowTemperature,? Phys.Rev. D84 (2011) 024002, arXiv:1008.1340 [gr-qc].[48] J. B. Kogut, ?An Introduction to Lattice Gauge Theory and Spin Systems,?Rev.Mod.Phys. 51 (1979) 659.[49] J. Ambj?rn, J. Jurkiewicz, and Y. Watabiki, ?On the fractal structure oftwo-dimensional quantum gravity,? Nucl.Phys. B454 (1995) 313?342,arXiv:hep-lat/9507014 [hep-lat].[50] J. Ambj?rn, J. Jurkiewicz, and R. Loll, ?Spectral dimension of the universe,?Phys.Rev.Lett. 95 (2005) 171301, arXiv:hep-th/0505113 [hep-th].[51] G. Giasemidis, J. F. Wheater, and S. Zohren, ?Dynamical dimensional reduction intoy models of 4D causal quantum gravity,? Phys.Rev. D86 (2012) 081503,arXiv:1202.2710 [hep-th].123Bibliography[52] J. Ambj?rn, S. Jordan, J. Jurkiewicz, and R. Loll, ?A Second-order phase transitionin CDT,? Phys.Rev.Lett. 107 (2011) 211303, arXiv:1108.3932 [hep-th].[53] R. Penrose, ?Difficulties with inflationary cosmology,? Annals N.Y.Acad.Sci. 571(1989) 249?264.[54] S. M. Carroll and J. Chen, ?Does inflation provide natural initial conditions for theuniverse?,? Gen.Rel.Grav. 37 (2005) 1671?1674, arXiv:gr-qc/0505037 [gr-qc].[55] E. W. Dijkstra, ?A note on two problems in connexion with graphs,? NumerischeMathematik 1 (1959) 269?271. http://dx.doi.org/10.1007/BF01386390.10.1007/BF01386390.[56] R. W. Floyd, ?Shortest path,? Commun. ACM 5 no. 6, (June, 1962) 345.[57] S. Warshall, ?A theorem on boolean matrices,? Journal of the ACM 9 no. 1, (1962)11?12.[58] A. S. Schwarz, ?The Partition Function of Degenerate Quadratic Functional andRay-Singer Invariants,? Lett.Math.Phys. 2 (1978) 247?252.[59] E. Witten, ?Quantum field theory and the Jones polynomial,? Commun. Math.Phys. 121 (1989) 351.[60] M. Marino, ?Chern-Simons theory and topological strings,? Rev.Mod.Phys. 77(2005) 675?720, arXiv:hep-th/0406005 [hep-th].[61] G. W. Moore and N. Seiberg, ?Taming the conformal zoo,? Phys.Lett. B220 (1989)422.[62] S. Elitzur, G. W. Moore, A. Schwimmer, and N. Seiberg, ?Remarks on the canonicalquantization of the Chern-Simons-Witten theory,? Nucl.Phys. B326 (1989) 108.[63] M. Bos and V. Nair, ?Coherent state quantization of Chern-Simons theory,?Int.J.Mod.Phys. A5 (1990) 959.124Bibliography[64] M. Ban?ados, ?Global charges in Chern-Simons field theory and the (2+1) blackhole,? Phys.Rev. D52 (1996) 5816, arXiv:hep-th/9405171 [hep-th].[65] E. Witten, ?Analytic Continuation Of Chern-Simons Theory,? arXiv:1001.2933[hep-th].[66] C. Nayak, S. H. Simon, A. Stern, M. Freedman, and S. Das Sarma, ?Non-Abeliananyons and topological quantum computation,? Rev.Mod.Phys. 80 (2008)1083?1159.[67] R. Iengo and K. Lechner, ?Anyon quantum mechanics and Chern-Simons theory,?Phys.Rept. 213 (1992) 179?269.[68] U. H. Danielsson, M. Lundgren, and A. J. Niemi, ?Gauge field theory of chirallyfolded homopolymers with applications to folded proteins,? Phys. Rev. E 82 (Aug,2010) 021910. http://link.aps.org/doi/10.1103/PhysRevE.82.021910.[69] A. Achucarro and P. Townsend, ?A Chern-Simons action for three-dimensionalanti-De Sitter supergravity theories,? Phys.Lett. B180 (1986) 89.[70] E. Witten, ?(2+1)-dimensional gravity as an exactly soluble system,? Nucl. Phys.B311 (1988) 46.[71] S. Carlip, ?Quantum gravity in 2+1 dimensions: The case of a closed universe,?Living Rev. Rel. 8 (2005) 1, arXiv:gr-qc/0409039 [gr-qc].[72] E. Witten, ?Three-dimensional gravity revisited,? arXiv:0706.3359 [hep-th].[73] S. Hawking and G. Ellis, The Large Scale Structure of Space-Time. CambridgeMonographs on Mathematical Physics. Cambridge University Press, 1973.[74] G. ?t Hooft and M. Veltman, ?One loop divergencies in the theory of gravitation,?Annales Poincare Phys.Theor. A20 (1974) 69?94.125Bibliography[75] C. Rovelli, ?What is observable in classical and quantum gravity?,?Class.Quant.Grav. 8 (1991) 297?316.[76] C. Isham, ?Canonical quantum gravity and the problem of time,? in Integrablesystems, quantum groups, and quantum field theories, pp. 157?287. KluwerAcademic, 1993. arXiv:gr-qc/9210011 [gr-qc].[77] H.-J. Matschull, ?On the relation between (2+1) Einstein gravity and Chern-Simonstheory,? Class. Quant. Grav. 16 (1999) 2599?2609, arXiv:gr-qc/9903040[gr-qc].[78] E. Buffenoir and K. Noui, ?Unfashionable observations about three-dimensionalgravity,? arXiv:gr-qc/0305079 [gr-qc].[79] B. Farb and D. Margalit, A Primer on Mapping Class Groups. PrincetonMathematical Series. Princeton University Press, 2011.[80] G. V. Dunne, ?Aspects of Chern-Simons theory,? arXiv:hep-th/9902115[hep-th]. Les Houches Lectures 1998.[81] S. S. Chern and J. Simons, ?Characteristic forms and geometric invariants,? Ann. ofMath. (2) 99 (1974) 48?69.[82] R. Dijkgraaf and E. Witten, ?Topological gauge theories and group cohomology,?Commun.Math.Phys. 129 (1990) 393.[83] F. Warner, Foundations of Differentiable Manifolds and Lie Groups. GraduateTexts in Mathematics. Springer, 1971.[84] S. Deser, R. Jackiw, and S. Templeton, ?Three-Dimensional massive gaugetheories,? Phys.Rev.Lett. 48 (1982) 975?978.[85] D. Birmingham, M. Blau, M. Rakowski, and G. Thompson, ?Topological fieldtheory,? Phys. Rept. 209 (1991) 129?340.126Bibliography[86] G. ?t Hooft, ?Quantization of point particles in (2+1)-dimensional gravity andspace-time discreteness,? Class.Quant.Grav. 13 (1996) 1023?1040,arXiv:gr-qc/9601014 [gr-qc].[87] M. Banados, C. Teitelboim, and J. Zanelli, ?The Black hole in three-dimensionalspace-time,? Phys.Rev.Lett. 69 (1992) 1849?1851, arXiv:hep-th/9204099[hep-th].[88] D. Brill, ?Black holes and wormholes in (2+1)-dimensions,? in Mathematical andquantum aspects of relativity and cosmology, pp. 143?179. 1998.arXiv:gr-qc/9904083 [gr-qc].[89] J. Louko, ?Witten?s 2+1 gravity on R x (Klein bottle),? Class. Quant. Grav. 12(1995) 2441?2468, arXiv:gr-qc/9505026 [gr-qc].[90] G. Rham, Differentiable manifolds: forms, currents, harmonic forms. Grundlehrender mathematischen Wissenschaften. Springer-Verlag, 1984.[91] R. Bott and L. W. Tu, Differential forms in algebraic topology, vol. 82 of GraduateTexts in Mathematics. Springer-Verlag, New York, 1982.[92] T. A. Murdoch, Twisted calibrations and the cone over the Veronese surface. PhDthesis, Rice University, 1988.[93] G. T. Horowitz, ?Exactly Soluble Diffeomorphism Invariant Theories,?Commun.Math.Phys. 125 (1989) 417.[94] C. Misner, K. Thorne, and J. Wheeler, Gravitation: Charles W. Misner, Kip S.Thorne, John Archibald Wheeler. Gravitation. W. H. Freeman, 1973.[95] S. Axelrod, S. Della Pietra, and E. Witten, ?Geometric quantization ofChern-Simons gauge theory,? J. Diff. Geom. 33 (1991) 787?902.127Bibliography[96] A. Y. Alekseev, H. Grosse, and V. Schomerus, ?Combinatorial quantization of theHamiltonian Chern-Simons theory,? Commun.Math.Phys. 172 (1995) 317?358,arXiv:hep-th/9403066 [hep-th].[97] A. Y. Alekseev, H. Grosse, and V. Schomerus, ?Combinatorial quantization of theHamiltonian Chern-Simons theory. 2.,? Commun.Math.Phys. 174 (1995) 561?604,arXiv:hep-th/9408097 [hep-th].[98] A. Y. Alekseev and V. Schomerus, ?Representation theory of Chern-Simonsobservables,? arXiv:q-alg/9503016 [q-alg].[99] M. Dehn, Papers on group theory and topology. Springer-Verlag, New York, 1987.http://dx.doi.org/10.1007/978-1-4612-4668-8. Translated from the Germanand with introductions and an appendix by John Stillwell, With an appendix byOtto Schreier.[100] D. Mumford, ?Abelian quotients of the Teichmu?ller modular group,? J. AnalyseMath. 18 (1967) 227?244.[101] W. B. R. Lickorish, ?A finite set of generators for the homeotopy group of a2-manifold,? Proc. Cambridge Philos. Soc. 60 (1964) 769?778.[102] B. Wajnryb, ?A simple presentation for the mapping class group of an orientablesurface,? Israel J. Math. 45 no. 2-3, (1983) 157?174.http://dx.doi.org/10.1007/BF02774014.[103] W. B. R. Lickorish, ?Homeomorphisms of non-orientable two-manifolds,? Proc.Cambridge Philos. Soc. 59 (1963) 307?317.[104] D. R. J. Chillingworth, ?A finite set of generators for the homeotopy group of anon-orientable surface,? Proc. Cambridge Philos. Soc. 65 (1969) 409?430.128Bibliography[105] S. Gukov, E. Martinec, G. W. Moore, and A. Strominger, ?Chern-Simons gaugetheory and the AdS(3) / CFT(2) correspondence,? arXiv:hep-th/0403225[hep-th].[106] C. Meusburger and B. Schroers, ?Mapping class group actions in Chern-Simonstheory with gauge group G x g*,? Nucl.Phys. B706 (2005) 569?597,arXiv:hep-th/0312049 [hep-th].[107] M. Bos and V. Nair, ?U(1) Chern-Simons theory and c=1 conformal blocks,?Phys.Lett. B223 (1989) 61.[108] M. Manoliu, ?Abelian Chern-Simons theory,? J.Math.Phys. 39 (1998) 170?206,arXiv:dg-ga/9610001 [dg-ga].[109] A. P. Polychronakos, ?On the quantization of the coefficient of the AbelianChern-Simons term,? Phys. Lett. B241 (1990) 37.[110] P. Peldan, ?Large diffeomorphisms in (2+1) quantum gravity on the torus,?Phys.Rev. D53 (1996) 3147?3155, arXiv:gr-qc/9501020 [gr-qc].[111] J. S. Birman and H. M. Hilden, ?On the mapping class groups of closed surfaces ascovering spaces,? in Advances in the theory of Riemann surfaces (Proc. Conf., StonyBrook, N.Y., 1969), pp. 81?115. Ann. of Math. Studies, No. 66. Princeton Univ.Press, Princeton, N.J., 1971.[112] J. S. Birman and D. R. J. Chillingworth, ?On the homeotopy group of anon-orientable surface,? Proc. Cambridge Philos. Soc. 71 (1972) 437?448.[113] B. Szepietowski, ?A presentation for the mapping class group of a non-orientablesurface from the action on the complex of curves,? Osaka J. Math. 45 no. 2, (2008)283?326. http://projecteuclid.org/getRecord?id=euclid.ojm/1216151101.129Bibliography[114] B. Szepietowski, ?A presentation for the mapping class group of the closednon-orientable surface of genus 4,? J. Pure Appl. Algebra 213 no. 11, (2009)2001?2016. http://dx.doi.org/10.1016/j.jpaa.2009.02.009.[115] R. Potts, ?Some generalized order - disorder transformations,? Proc.CambridgePhil.Soc. 48 (1952) 106?109.[116] P. C. Whitford, J. K. Noel, S. Gosavi, A. Schug, K. Y. Sanbonmatsu, and J. N.Onuchic, ?An all-atom structure-based potential for proteins: Bridging minimalmodels with all-atom empirical forcefields,? Proteins: Structure, Function, andBioinformatics 75 no. 2, (2009) 430?441.http://dx.doi.org/10.1002/prot.22253.[117] J. K. Noel, P. C. Whitford, K. Y. Sanbonmatsu, and J. N. Onuchic, ?Smog@ctbp:simplified deployment of structure-based models in gromacs,?.http://nar.oxfordjournals.org/cgi/content/short/38/suppl_2/W657.[118] F. Wu, ?The Potts model,? Rev.Mod.Phys. 54 (1982) 235?268.[119] R. Baxter, ?Potts model at critical temperature,? J.Phys. C6 (1973) L445?L448.[120] J. Noel and J. Onuchic, ?The many faces of structure-based potentials: Fromprotein folding landscapes to structural characterization of complex biomolecules,?in Computational Modeling of Biological Systems, N. V. Dokholyan, ed., Biologicaland Medical Physics, Biomedical Engineering, pp. 31?54. Springer US, 2012.http://dx.doi.org/10.1007/978-1-4614-2146-7_2.[121] M. S. Challa, D. Landau, and K. Binder, ?Finite size effects at temperature drivenfirst order transitions,? Phys.Rev. B34 (1986) 1841?1852.[122] J. Rowlinson and B. Widom, Molecular theory of capillarity. The internationalseries of monographs on chemistry. Dover Publications, 2002.130"@en .
"Thesis/Dissertation"@en .
"2013-11"@en .
"10.14288/1.0074162"@en .
"eng"@en .
"Physics"@en .
"Vancouver : University of British Columbia Library"@en .
"University of British Columbia"@en .
"Attribution-NonCommercial-NoDerivatives 4.0 International"@en .
"http://creativecommons.org/licenses/by-nc-nd/4.0/"@en .
"Graduate"@en .
"Emergence of Riemannian manifolds from graphs and aspects of Chern-Simons theory"@en .
"Text"@en .
"http://hdl.handle.net/2429/44920"@en .