In this thesis, I examine the asymptotic behavior of optimal values and optimal configurations of certain random graphical models. In particular, I propose a general framework for analyzing the asymptotic behavior for optimization problems that includes the Maximum Weight Independent Set (MWIS), Maximum Weight Partial Coloring (MWPC), and Maximum Weight Coloring (MWC) problems. I apply this framework to graphs that are generated from branching processes and Erdos-Renyi graphs.;Many of the results are inspired by Gamarnik, Nowicki, and Swirscsz (2005). They showed that if a particular fixed point equation had a unique solution, then the scaled MWIS value on Erdos-Renyi graphs converges in probability. The highlight of my thesis is in Chapter 4 where I give surprisingly weak conditions that shows that the optimal value converges almost surely when the underlying graph is given by a branching process. This includes cases where the fixed point equation has non-unique solutions.;In addition, in the case of uniqueness, I strengthen many of the techniques by Gamarnik, Nowicki, and Swirscsz (2005) to get stronger convergence results of the optimal configurations on branching processes. I also show how their techniques can be used to show convergence results on Erdos-Renyi graphs for a wider class of problems that include the MWPC problem. Finally, I introduce a new method of relating the branching process results to Erdos-Renyi graphs. This leads to new convergence results on Erdos-Renyi graphs.
展开▼
