Organização estrutural e geométrica de redes: grafos acíclicos e árvores críticas

Abstract

In this thesis, we study the structural and geometric properties of random graph models through two interconnected investigations. First, we analyze the structural phase transition in random acyclic graphs, providing fundamental insights into the topological properties of networks. By exploiting the exact combinatorial enumeration possible for acyclic structures, we derive an expression for the entropy and determine critical transition points and critical exponents. Our results, validated by Monte Carlo simulations, establish connections with mean-field percolation theory, offering new perspectives on the subcritical regime of random acyclic graphs. Subsequently, we investigate scaling properties in critical percolation clusters through various constructions of spanning trees (MPT, DFS, RFS, MST) embedded in these clusters. We reveal universal scaling laws governing the relationship between chemical and Euclidean distances, characterized by critical exponents dependent on the tree topology. Our analysis shows that MPTs reflect fractal dimensions of the shortest path, while MSTs correspond to dimensions of the optimal path. For DFS and RFS trees, we identify dimension-dependent behaviors, including a new critical exponent (θ1 = 1.575) for DFS in d = 3. We establish fundamental relations among the scaling exponents θ1, θ2, the fractal dimension df, and the spreading dimension dℓ, demonstrating that θ1 = 1/θ2 must hold for scaling consistency. Together, these results provide comprehensive insights both into structural transitions in graph ensembles and the geometric organization of critical clusters, with implications for network science and transport in disordered systems.