Neste trabalho estudamos o problema relacionado à construção de uma teoria quântica para uma partícula, se movendo não relativisticamente num espaço curvo, tratado como uma subvariedade de outro Euclideano, talvez dando maior ênfase ao aspecto geométrico envolvido nesta abordagem, uma vez que os demais trabalhos relacionados ao mesmo tema não o fazem. Além de mostrarmos que o consequente uso de uma teoria de sistemas vinculados não contribui para remover as ambiguidades da formulação quântica, relacionados diretamente ao ordenamento de operadores, também apresentamos, através de uma quantização específica feita sob a prescrição de Dirac, elementos que permitem não apenas construir um formalismo quântico covariante, mas também liberto de qualquer correção quântica. Em adição, fazemos alguns comentários gerais no que se refere às outras abordagens clássicas possíveis para o mesmo problema, intentando construir teorias quânticas associadas ao sistema sob consideração. / In this work we study the problem related to the construction of a quantum theory for a particle, moving non-relativistically in a curved space, treated as submanifold of the other Euclidean, maybe putting more emphasis on the geometric aspect envolved in this approach, since the rest of the works related to the subject do not. Besides showing that the consequent use of a theory of constrained systems not contributes for remove the ambiguities in the quantum formulation, related directly to the ordering of operators, we also showing, through a specific quantization made in the prescription of Dirac, elements that offers resources not only to construct a covariant quantum formalism, but also free from any quantum correction. In addition, we make some general comments in relation to other classical approaches possible for the same problem, attempting to build quantum theories associated with the system under consideration.

Neste trabalho estudamos o problema relacionado à construção de uma teoria quântica para uma partícula, se movendo não relativisticamente num espaço curvo, tratado como uma subvariedade de outro Euclideano, talvez dando maior ênfase ao aspecto geométrico envolvido nesta abordagem, uma vez que os demais trabalhos relacionados ao mesmo tema não o fazem. Além de mostrarmos que o consequente uso de uma teoria de sistemas vinculados não contribui para remover as ambiguidades da formulação quântica, relacionados diretamente ao ordenamento de operadores, também apresentamos, através de uma quantização específica feita sob a prescrição de Dirac, elementos que permitem não apenas construir um formalismo quântico covariante, mas também liberto de qualquer correção quântica. Em adição, fazemos alguns comentários gerais no que se refere às outras abordagens clássicas possíveis para o mesmo problema, intentando construir teorias quânticas associadas ao sistema sob consideração. / In this work we study the problem related to the construction of a quantum theory for a particle, moving non-relativistically in a curved space, treated as submanifold of the other Euclidean, maybe putting more emphasis on the geometric aspect envolved in this approach, since the rest of the works related to the subject do not. Besides showing that the consequent use of a theory of constrained systems not contributes for remove the ambiguities in the quantum formulation, related directly to the ordering of operators, we also showing, through a specific quantization made in the prescription of Dirac, elements that offers resources not only to construct a covariant quantum formalism, but also free from any quantum correction. In addition, we make some general comments in relation to other classical approaches possible for the same problem, attempting to build quantum theories associated with the system under consideration.

Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès. / A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique. / In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon.

MASTER THESIS Petr Lukeš Emergence of space geometries from quantum entanglement Institute of Theoretical Physics Supervisor of the master thesis: Mgr. Martin Scholtz, Ph.D. Study programme: Physics Study branch: Theoretical physics Prague 2019 Abstract: Connecting the field of Quantum Physics and General Relativity is one of the main interests of contemporary Theoretical Physics. This work attempts to find solution to simplified version of this problem. Firstly entropy is shown to be a good meeting point between the two different theories. Then some of entropy's less intuitive properties are shown, namely its dependence on area, not volume. This relation is studied from both Relativistic and Quantum viewpoint. After- wards there is a short description of a quantum model interpretable as geometry based on the information between its subsystems. Lastly, results of computations within this model are presented.