Asymptotic structure of random graphs: Rank, distance and satisfiability

In the study of complex networks, random graphs serve as fundamental models for understanding the typical structure of large-scale graph-based systems. They are also of great theoretical interest and have numerous applications in other fields, such as computer science. This thesis explores several fundamental questions concerning global properties of random graphs and related models, including the rank of the adjacency matrix, the typical distance between vertices, and the number of solutions to random 2-SAT instances. Although the methods employed vary across chapters, they share a common focus on precise asymptotic analysis and a strong reliance on combinatorial and probabilistic techniques. Throughout the thesis, the local structure of the underlying graph plays a central role. The main innovation throughout this thesis lies in extending local intuitions and results to derive rigorous conclusions about the global behavior of the graph models under consideration. In the first part of this thesis, we investigate the rank of the adjacency matrix of sparse Erdös-Rényi random graphs. The study of the asymmetric case is particularly relevant for applications in low-density parity-check (LDPC) codes. From a mathematical perspective, our main objective is to examine whether the asymptotic behavior of the rank exhibits a universal pattern across different settings. Aside from introducing a novel permutation matrix, the key idea in our proof is to reduce the global structure of the random graph, namely its rank, to a simple property called the type of a vertex, as explained in Chapter 2. This has two main advantages. First, w.h.p., the vertex type remains stable when a single vertex is added, as shown in Chapter 3. Second, w.h.p., the type of a vertex can be inferred from the types of its neighbors, a result we establish in Chapter 4. These features suggest that vertex types behave as an almost local property. Based on this locality, we derive a set of fixed-point equations that describe the distribution of vertex types in the graph. These equations ultimately allow us to estimate the rank of the adjacency matrix. In the second part of this thesis, we investigate the typical distance in preferential attachment model with finite variance degrees, a problem that has been open for 15 years. In Chapters 5, 7 and 8, we make extensive use of the path-counting technique, in which we analyze the expectation and variance of the number of self-avoiding paths of a given length between two vertices. Using the first- and second-moment methods, we establish sharp lower and upper bounds on the typical distances. This analysis is made tractable by leveraging the Pólya urn representation of the preferential attachment model. As discussed in Chapter 5, the path-counting technique originates from the study of the exponential growth of local neighborhoods around individual vertices. Specifically, when the sizes of the neighborhoods of two uniformly chosen vertices are much smaller than the square root of the graph size, these neighborhoods are disjoint w.h.p. On the other hand, if we grow the neighborhoods such that their sizes exceed the square root of the graph size, it becomes likely that they intersect. To make this argument rigorous, we also apply a truncation to the model and give a proof for the exponential growth of neighborhoods in the truncated setting, as presented in Chapter 6. It is also worth noting that, when the path length is close to the typical graph distance, most contributing paths are self-avoiding. This observation plays a central role in the first- and second-moment analyses carried out in Chapters 7 and 8.In the final part of this thesis, we investigate the fluctuations of the number of solutions to random 2-SAT formulas below the satisfiability threshold. To eliminate unsatisfiable instances, we apply the Unit Clause Propagation procedure to prune the formula. The analysis of the resulting pruned formula is presented in Chapter 10, where we show that, aside from always being satisfiable, it can be roughly treated as the original formula. In Chapter 11, we study the behavior of Belief Propagation (BP) on Galton-Watson trees, which resemble the local structure of the factor graph associated with random 2-SAT formulas. We establish a correspondence between the BP marginals and the solution marginals of 2-SAT instances defined on the truncated tree. This connection is extended to the full random 2-SAT formula via the concept of Gibbs uniqueness, which allows us to transfer local marginal information from trees to the original random formula. Building on this connection, we then construct a martingale that captures the fluctuations in the number of solutions via two correlated random formulas. The martingale differences are estimated using the aforementioned marginals, and the central limit behavior is established via a martingale central limit theorem.