| The maximum (or minimum) weight matching in a complete bipartite graph is an object of great importance in combinatorial optimization. The Assignment Problem---which is the problem of finding these extremal matchings, has many applications, for example, in switch scheduling and manufacturing systems. A lot of research has been devoted to its study in the general areas of Network Flow and Matching Problems.; In many situations it is of interest to study the properties of extremal matchings under a random weight model, that is, where the costs of the edges of the bipartite graph are drawn from some distribution. A central question in the probabilistic study of the Random Assignment Problem is the determination of the expected value of the extremal matching under different cost assumptions.; In this thesis we consider weighted complete bipartite graphs and study the probabilistic and combinatorial properties of extremal matchings in special subgraphs. Specifically, we analyze extremal matchings of size (n - 1) in the weighted complete bipartite graph K n-1,n. These matchings play a crucial role in the resolution of Parisi's conjecture for the Random Assignment Problem. It turns out that a beautiful structure emerges indicating the existence of a certain kind of minimal redundancy in this family of submatchings.; Further, assuming rate 1 exponential random weights, we study the asymptotic behavior of the patterns of elements that participate in these extremal matchings for an interesting special placement of the weights and prove convergence to an elegant limiting pattern. |
