Probability on graphs

Abstract

This is my licentiate thesis, summarizing my first two years as a PhD-student. In general terms, the thesis deals with problems concerning probability models on combinatorial structures. The first paper considers the random assignment problem, the second first-passage percolation. The third paper investigate subgraph relations of the Archimedean and Laves lattices, and has applications in classical percolation, first-passage percolation, and self-avoiding walks. I was introduced to these fields by my supervisor, Sven Erick Alm, when I as an undergraduate was looking for a project for my master thesis. The title of the master thesis became Lower and Upper Bounds for the Time Constant of First-Passage Percolation, which is also the title of the second paper in the present thesis (co-authored with Sven Erick Alm). I am most grateful to him for introducing me to these fascinating subjects, and for his support and help. Special thanks also to John C. Wierman, who is the co-author of the third paper in this thesis, The Subgraph Partial Ordering of Archimedean and Laves Lattices.