Dans cette thèse nous explorons différentes facettes des modèles de tenseurs aléatoires. Les modèles de tenseurs aléatoires ont été introduits en physique dans le cadre de l'étude de la gravité quantique. En effet les modèles de matrices aléatoires, qui sont un cas particuliers de modèles de tenseurs, en sont une des origines. Ces modèles de matrices sont connus pour leur riche combinatoire et l'incroyable diversité de leurs propriétés qui les font toucher tous les domaines de l'analyse, la géométrie et des probabilités. De plus leur étude par les physiciens ont prouvé leur efficacité en ce qui concerne l'étude de la gravité quantique à deux dimensions. Les modèles de tenseurs aléatoires incarnent une généralisation possible des modèles de matrices. Comme leurs cousins, les modèles de matrices, ils posent questions dans les domaines de la combinatoire (comment traiter les cartes combinatoires d dimensionnelles ?), de la géométrie (comment contrôler la géométrie des triangulations générées ?) et de la physique (quel type d'espace-temps produisent-ils ? Quels sont leurs différentes phases ?). Cette thèse espère établir des pistes ainsi que des techniques d'études de ces modèles. Dans une première partie nous donnons une vue d'ensemble des modèles de matrices. Puis, nous discutons la combinatoire des triangulations en dimensions supérieures ou égales à trois en nous concentrant sur le cas tridimensionnelle (lequel est plus simple à visualiser). Nous définissons ces modèles et étudions certaines de leurs propriétés à l'aide de techniques combinatoires permettant de traiter les cartes d dimensionnelles. Enfin nous nous concentrons sur la généralisation de techniques issues des modèles de matrices dans le cas d'une famille particulières de modèles de tenseurs aléatoires. Ceci culmine avec le dernier chapitre de la thèse donnant des résultats partiels concernant la généralisation de la récurrence topologique de Eynard et Orantin à cette famille de modèles de tenseurs. / In this thesis manuscript we explore different facets of random tensor models. These models have been introduced to mimic the incredible successes of random matrix models in physics, mathematics and combinatorics. After giving a very short introduction to few aspects of random matrix models and recalling a physical motivation called Group Field Theory, we start exploring the world of random tensor models and its relation to geometry, quantum gravity and combinatorics. We first define these models in a natural way and discuss their geometry and combinatorics. After these first explorations we start generalizing random matrix methods to random tensors in order to describes the mathematical and physical properties of random tensor models, at least in some specific cases.

In this thesis, questions of navigation, planning and control of real-world mobile robotic systems are addressed. Chapter II contains the first contribution in this thesis, which is a modification of the canonical two-layer hybrid architecture: deliberative planning on top, with reactive behaviors underneath. Deliberative is used to describe higher-level reasoning that includes experiential memory and regional or global objectives. Alternatively, reactive describes low-level controllers that operate on information spatially and temporally immediate to the robot. In the traditional architecture, information is passed top down, with the deliberative layer dictating to the reactive layer. Chapter II presents our work on introducing feedback in the opposite direction, allowing the behaviors to provide information to the planning module(s). The path planning problem, particularly as it as solved by the visibility graph, is addressed first in Chapter III. Our so-called oriented visibility graph is a combinatorial planner with emphasis on dynamic re-planning in unknown environments at the expensive of guaranteed optimality at all times. An example of single source planning -- where the goal location is known and static -- this approach is compared to related approaches (e.g. the reduced visibility graph). The fourth chapter further develops the work presented in the Chapter III; the oriented visibility graph is extended to the hierarchical oriented visibility graph. This work directly addresses some of the limitations of the oriented visibility graph, particularly the loss of optimality in the case where obstacles are non-convex and where the convex hulls of obstacles overlap. This results in an approach that is a kind of middle-ground between the oriented visibility graph which was designed to handle dynamic updates very fast, and the reduced visibility graph, an old standard in path planning that guarantees optimality. Chapter V investigates path planning at a higher level of abstraction. Given is a weighted colored graph where vertices are assigned a color (or class) that indicates a feature or quality of the environment associated with that vertex. The question is then asked, ``what is the globally optimal path through this weighted colored graph?' We answer this question with a mapping from classes and edge weights to a real number, and use Dijkstra's Algorithm to compute the best path. Correctness is proven and an implementation is highlighted.

A simplicial cell complex K is the face poset of a regular CW complex W such that the boundary complex of each cell is isomorphic to the boundary complex of a simplex of same dimension. If a topological space X is homeomorphic to W then we say that K is a pseudotriangulation of X. For d 1, a (d + 1)-colored graph is a graph = (V; E) with a proper edge coloring : E ! f0; : : : ; dg. Such a graph is called contracted if (V; E n 1(i)) is connected for each color A contracted graph = (V; E) with an edge coloring : E ! f0; : : : ; dg determines a d-dimensional simplicial cell complex K( ) whose vertices have one to one correspondence with the colors 0; : : : ; d and the facets (d-cells) have one to one correspondence with the vertices in V . If K( ) is a pseudotriangulation of a manifold M then ( ; ) is called a crystallization of M. In [71], Pezzana proved that every connected closed PL manifold admits a crystallization. This thesis addresses many important results of crystallization theory in combinatorial topology. The main contributions in this thesis are the followings. We have introduced the weight of a group which has a presentation with number of relations is at most the number of generators. We have shown that the number of vertices of any crystallization of a connected closed 3-manifold M is at least the weight of the fundamental group of M. This lower bound is sharp for the 3-manifolds RP3, L(3; 1), L(5; 2), S1 S1 S1, S2 S1, S2 S1 and S3=Q8, where Q8 is the quaternion group. Moreover, there is a unique such vertex minimal crystallization in each of these seven cases. We have also constructed crystallizations of L(kq 1; q) with 4(q + k 1) vertices for q 3, k 2 and L(kq +1; q) with 4(q + k) vertices for q 4, k 1. In [22], Casali and Cristofori found similar crystallizations of lens spaces. By a recent result of Swartz [76], our crystallizations of L(kq + 1; q) are vertex minimal when kq + 1 are even. In [47], Gagliardi found presentations of the fundamental group of a manifold M in terms of a crystallization of M. Our construction is the converse of this, namely, given a presentation of the fundamental group of a 3-manifold M, we have constructed a crystallization of M. These results are in Chapter 3. We have de ned the weight of the pair (hS j Ri; R) for a given presentation hS j R of a group, where the number of generators is equal to the number of relations. We present an algorithm to construct crystallizations of 3-manifolds whose fundamental group has a presentation with two generators and two relations. If the weight of (hS j Ri; R) is n then our algorithm constructs all the n-vertex crystallizations which yield (hS j Ri; R). As an application, we have constructed some new crystallization of 3-manifolds. We have generalized our algorithm for presentations with three generators and a certain class of relations. For m 3 and m n k 2, our generalized algorithm gives a 2(2m + 2n + 2k 6 + n2 + k2)-vertex crystallization of the closed connected orientable 3-manifold Mhm; n; ki having fundamental group hx1; x2; x3 j xm1 = xn2 = xk3 = x1x2x3i. These crystallizations are minimal and unique with respect to the given presentations. If `n = 2' or `k 3 and m 4' then our crystallization of Mhm; n; ki is vertex-minimal for all the known cases. These results are in Chapter 4. We have constructed a minimal crystallization of the standard PL K3 surface. The corresponding simplicial cell complex has face vector (5; 10; 230; 335; 134). In combination with known results, this yields minimal crystallizations of all simply connected PL 4-manifolds of \standard" type, i.e., all connected sums of CP2, CP2, S2 S2, and the K3 surface. In particular, we obtain minimal crystallizations of a pair 4-manifolds which are homeomorphic but not PL-homeomorphic. We have also presented an elementary proof of the uniqueness of the 8-vertex crystallization of CP2. These results are in Chapter 5. For any crystallization ( ; ) the number f1(K( )) of 1-simplices in K( ) is at least d+1 . It is easy to see that f1(K( )) = d+1 if and only if (V; 1(A)) is connected for each d 2 2 1)-set A called simple. All the crystallization in Chapter 5 (. Such a crystallization is are simple. Let ( ; ) be a crystallization of M, where = (V; E) and : E ! f0; : : : ; dg. We say that ( ; ) is semi-simple if (V; 1(A)) has m + 1 connected components for each (d 1)-set A, where m is the rank of the fundamental group of M. Let ( ; ) be a connected (d +1)-regular (d +1)-colored graph, where = (V; E) and : E ! f0; : : : ; dg. An embedding i : ,! S of into a closed surface S is called regular if there exists a cyclic permutation ("0; "1; : : : ; "d) (of the color set) such that the boundary of each face of i( ) is a bi-color cycle with colors "j; "j+1 for some j (addition is modulo d+1). Then the regular genus of ( ; ) is the least genus (resp., half of genus) of the orientable (resp., non-orientable) surface into which embeds regularly. The regular genus of a closed connected PL 4-manifold M is the minimum regular genus of its crystallizations. For a closed connected PL 4-manifold M, we have provided the following: (i) a lower bound for the regular genus of M and (ii) a lower bound of the number of vertices of any crystallization of M. We have proved that all PL 4-manifolds admitting semi-simple crystallizations, attain our bounds. We have also characterized the class of PL 4-manifolds which admit semi-simple crystallizations. These results are in Chapter 6.

This work analyses properties of relational structures that imply a high degree of symmetry. A structure is called homogeneous if every mapping from any finite substructure can be extended to a mapping over the whole structure. The various types of these mappings determine corresponding types of homogeneity. A prominent position belongs to ultrahomogeneity, for which every local isomorphism can be extended to an automorphism. In contrast to graphs, the classification of ultrahomogeneous relational struc- tures is still an open problem. The task of this work is to characterize "the distance" to homogeneity using two approaches. Firstly, the classification of homogeneous structures is studied when the "complexity" of a structure is increased by introducing more relations. This leads to various classifications of homomorphism-homogeneous L-colored graphs for different L, where L- colored graphs are graphs having sets of colors from a partially ordered set L assigned to vertices and edges. Moreover a hierarchy of classes of ho- mogeneous structures defined via types of homogeneity is studied from the viewpoint of classes coincidence. The second approach analyses for fixed classes of structures the least way to extend their language so as to achieve homogeneity. We obtain results about relational complexity for finite...

Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1. / In this thesis, we investigate the extraction of trees from edge-colored graphs. We focus on finding trees with properties based on coloring. Namely, we deal with proper and weak proper spanning trees, denoted PST and WST.- We show the optimization versions of these problems to be NP-hard in the general case of edge-colored graphs and we provide algorithms to find these trees in the case of edge-colored graphs without properly edge-colored cycles. We also provide some nonapproximability bounds.- We investigate the existence of a PST in the case of edge-colored graphs under certain conditions on the graph, both structural and related to the coloration. We consider sufficient conditions that guarantee the existence of a PST in edge-colored (not necessarily proper) graphs with any number of colors. The conditions we consider are combinations ofvarious parameters such as : total number of colors, number of vertices, connectivity and the number of incident edges of different colors to the vertices.- We then consider properly edge-colored Hamiltonian paths in the edge-colored multigraphs, which are relevant to our study since they are also PST. We establish sufficient conditions for a multigraph to contain a proper edge-colored Hamiltonian path, depending on several parameters such as the number of edges, the degree of edges, etc.- Since one of the sufficient conditions for the existence of proper spanning trees is connectivity, we prove several upper bounds for the smallest number of colors needed to color a graph such that it is k-proper-connected. We state several conjectures for general and bipartite graphs, and we prove them for k = 1.

Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$. / In this thesis, we study different problems in edge-colored graphs and edge-colored multigraphs, such as proper connection, strong edge colorings, and proper hamiltonian paths and cycles. Finally, we improve the known $O(n^4)$ algorithm to decide the behavior of a graph under the biclique operator, by studying bicliques in graphs withoutfalse-twin vertices. In particular: 1) We first study the $k$-proper-connection number of graphs, this is, the minimum number of colors needed to color the edges of a graph such that between any pair of vertices there exist $k$ internally vertex-disjoint paths. We denote this number $pc_k(G)$. We prove several upper bounds for $pc_k(G)$. We state some conjectures for general and bipartite graphs, and we prove all of them for the case $k=1$. 2) Then, we study the existence of proper hamiltonian paths and proper hamiltonian cycles in edge-colored multigraphs. We establish sufficient conditions, depending on several parameters such as the number of edges, the rainbow degree, the connectivity, etc. 3) Later, we showthat the strong chromatic index is linear in the maximum degree for any $k$-degenerate graph where $k$ is fixed. As a corollary, our result leads to considerable improvement of the constants and also gives an easier and more efficient algorithm for this familly of graphs. Next, we consider outerplanar graphs. We give a formula to find exact strong chromatic index for bipartite outerplanar graphs. We also improve the upper bound for general outerplanar graphs from the $3\Delta-3$ bound. 4) Finally, we study bicliques in graphs without false-twin vertices and then we present an $O(n+m)$ algorithm to recognize convergent and divergent graphs improving the $O(n^4)$ known algorithm.

This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions. We studied algorithmic questions for these problems, for certain graph classes, to yield efficient algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded. We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs. Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs. n−1 3 Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs. It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position. Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G). We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.

On considère, en deux dimensions, une version euclidienne discrète de l’action d’Einstein-Hilbert, qui décrit la gravité en l’absence de matière. À l’intégration sur les géométries se substitue une sommation sur des surfaces triangulées aléatoires. Dans la limite physique de faible gravité, seules les triangulations planaires survivent. Leur limite en distribution, la carte brownienne, est une surface fractale continue dont l’importance dans le contexte de la gravité quantique en deux dimensions a été récemment précisée. Cet espace est interprété comme un espace-temps quantique, obtenu comme limite à grande échelle d’un ensemble statistique de surfaces discrètes aléatoires. En deux dimensions, on peut donc étudier les propriétés fractales de la gravité quantique via une approche discrète. Il est bien connu que les généralisations directes en dimensions supérieures échouent à produire des espace-temps quantiques aux propriétés adéquates : en dimension D>2, la limite en distribution des triangulations qui survivent dans la limite de faible gravité est l’arbre continu aléatoire, ou polymères branchés en physique. Si en deux dimensions on parvient aux mêmes conclusions en considérant non pas des triangulations, mais des surfaces discrètes aléatoires obtenues par recollements de 2p-gones, nous savons depuis peu que ce n’est pas toujours le cas en dimension D>2. L’apparition de nouvelles limites continues dans le cadre de théories de gravité impliquant des espaces discrets aléatoires reste une question ouverte. Nous étudions des espaces obtenus par recollements de blocs élémentaires, comme des polytopes à facettes triangulaires. Dans la limite de faible gravité, seuls les espaces qui maximisent la courbure moyenne survivent. Les identifier est cependant une tâche ardue dans le cas général, pour lequel les résultats sont obtenus numériquement. Afin d’obtenir des résultats analytiques, une coloration des (D-1)-cellules, les facettes, a été introduite. En toute dimension paire, on peut trouver des familles d’espaces discrets colorés de courbure moyenne maximale dans la classe d’universalité des arbres – convergeant vers l’arbre continu aléatoire, des cartes planaires – convergeant vers la carte brownienne, ou encore dans la classe de prolifération des bébé-univers. Cependant, ces résultats sont obtenus en raison de la simplicité de blocs élémentaires dont la structure uni ou bidimensionnelle ne rend pas compte de la riche diversité des blocs colorés en dimensions supérieures. Le premier objectif de cette thèse est donc d’établir des outils combinatoires qui permettraient une étude systématique des blocs élémentaires colorés et des espaces discrets qu’ils génèrent. Le principal résultat de ce travail est l’établissement d’une bijection entre ces espaces et des familles de cartes combinatoires, qui préserve l’information sur la courbure locale. Elle permet l’utilisation de résultats sur les surfaces discrètes et ouvre la voie à une étude systématique des espaces discrets en dimensions supérieures à deux. Cette bijection est appliquée à la caractérisation d’un certain nombre de blocs de petites tailles ainsi qu’à une nouvelle famille infinie. Le lien avec les modèles de tenseurs aléatoires est détaillé. Une attention particulière est donnée à la détermination du nombre maximal de (D-2)-cellules et de l’action appropriée du modèle de tenseurs correspondant. Nous montrons comment utiliser la bijection susmentionnée pour identifier les contributions à un tout ordre du développement en 1/N des fonctions à 2n points du modèle SYK coloré, et appliquons ceci à l’énumération des cartes unicellulaires généralisées – les espaces discrets obtenus par recollement d’un unique bloc élémentaire – selon leur courbure moyenne. Pour tout choix de blocs colorés, nous montrons comment réécrire la théorie d’Einstein-Hilbert discrète correspondante comme un modèle de matrices aléatoires avec traces partielles, dit représentation en champs intermédiaires. / In two dimensions, the Euclidean Einstein-Hilbert action, which describes gravity in the absence of matter, can be discretized over random triangulations. In the physical limit of small Newton's constant, only planar triangulations survive. The limit in distribution of planar triangulations - the Brownian map - is a continuum fractal space which importance in the context of two-dimensional quantum gravity has been made more precise over the last years. It is interpreted as a quantum continuum space-time, obtained in the thermodynamical limit from a statistical ensemble of random discrete surfaces. The fractal properties of two-dimensional quantum gravity can therefore be studied from a discrete approach. It is well known that direct higher dimensional generalizations fail to produce appropriate quantum space-times in the continuum limit: the limit in distribution of dimension D>2 triangulations which survive in the limit of small Newton's constant is the continuous random tree, also called branched polymers in physics. However, while in two dimensions, discretizing the Einstein-Hilbert action over random 2p-angulations - discrete surfaces obtained by gluing 2p-gons together - leads to the same conclusions as for triangulations, this is not always the case in higher dimensions, as was discovered recently. Whether new continuum limit arise by considering discrete Einstein-Hilbert theories of more general random discrete spaces in dimension D remains an open question.We study discrete spaces obtained by gluing together elementary building blocks, such as polytopes with triangular facets. Such spaces generalize 2p-angulations in higher dimensions. In the physical limit of small Newton's constant, only discrete spaces which maximize the mean curvature survive. However, identifying them is a task far too difficult in the general case, for which quantities are estimated throughout numerical computations. In order to obtain analytical results, a coloring of (D-1)-cells has been introduced. In any even dimension, we can find families of colored discrete spaces of maximal mean curvature in the universality classes of trees - converging towards the continuous random tree, of planar maps - converging towards the Brownian map, or of proliferating baby universes. However, it is the simple structure of the corresponding building blocks which makes it possible to obtain these results: it is similar to that of one or two dimensional objects and does not render the rich diversity of colored building blocks in dimensions three and higher.This work therefore aims at providing combinatorial tools which would enable a systematic study of the building blocks and of the colored discrete spaces they generate. The main result of this thesis is the derivation of a bijection between colored discrete spaces and colored combinatorial maps, which preserves the information on the local curvature. It makes it possible to use results from combinatorial maps and paves the way to a systematical study of higher dimensional colored discrete spaces. As an application, a number of blocks of small sizes are analyzed, as well as a new infinite family of building blocks. The relation to random tensor models is detailed. Emphasis is given to finding the lowest bound on the number of (D-2)-cells, which is equivalent to determining the correct scaling for the corresponding tensor model. We explain how the bijection can be used to identify the graphs contributing at any given order of the 1/N expansion of the 2n-point functions of the colored SYK model, and apply this to the enumeration of generalized unicellular maps - discrete spaces obtained from a single building block - according to their mean curvature. For any choice of colored building blocks, we show how to rewrite the corresponding discrete Einstein-Hilbert theory as a random matrix model with partial traces, the so-called intermediate field representation.