Overview

This dissertation consists of work done on two disjoint problems. In the first two chapters I discuss fractal properties of average-case solutions to the random minimal spanning tree (MST) problem: given a graph with costs on the edges, the MST is the spanning tree minimizing the sum of the total cost of the chosen edges. In the random version the costs are quenched random variables. I solve the random MST problem on the Bethe lattice with appropriate boundary conditions and use the results to infer fractal dimensions in the mean-field approximation. I find that connected components of the MST in a window have dimension D=6, which establishes the upper critical dimension dc=6. This contradicts a value dc=8 proposed previously in the literature; I correct the argument that led to this value. I then develop an exact low-density expansion for the random MST on a finite graph and use it to develop an expansion for the MST on critical percolation clusters. I prove this perturbation expansion is renormalizable around dc=6. Using a renormalization-group approach, I calculate the fractal dimension Dp of paths on the latter MST to first order in epsilon=6-d for d

Full Product Details

9781243793362

Table of Contents

Reviews

Author Information

Tab Content 6

Customer Reviews

Recent Reviews

Countries Available