Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

First-Passage Percolation on the Complete Graph with Weight-Zero Edges

Henderson, Nikolas

Abstract Details

2024, Doctor of Philosophy, Ohio State University, Mathematics.
Given any graph, one can generate a random metric on the vertices by assigning random weights to the edges, then letting the distance d(x, y) between any two vertices x and y be the total weight of the lightest path from x to y. This model started off on the integer lattice Zn under the name first-passage percolation, calling to mind a fluid percolating through a porous medium. More recently, however, the model has transitioned to the complete graph Kn, the Erdos-Renyi graph G(n, p), and other less geometric graph models, starting with [14] in 1999. While the theory has developed over the last 25 years, it has maintained a significant blind spot, namely that of weight-zero edges. Indeed, weightless edges have been what connected FPP on Zn with classical bond percolation, and the equivalent connections have not been explored on even Kn, where the theory of G(n, p) serves as a natural bond percolation analogue. We seek to begin building this connection by investigating the effects of weight-zero edges on the first passage model on Kn, examining the typical distance and radius of these random environments and seeing how the theory of G(n, p) can shed light on the behavior of these metrics.
David Sivakoff (Advisor)
Matthew Kahle (Committee Member)
Cesar Cuenca (Committee Member)
Arthur Burghes (Other)
65 p.

Recommended Citations

Citations

  • Henderson, N. (2024). First-Passage Percolation on the Complete Graph with Weight-Zero Edges [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1721299211219112

    APA Style (7th edition)

  • Henderson, Nikolas. First-Passage Percolation on the Complete Graph with Weight-Zero Edges. 2024. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1721299211219112.

    MLA Style (8th edition)

  • Henderson, Nikolas. "First-Passage Percolation on the Complete Graph with Weight-Zero Edges." Doctoral dissertation, Ohio State University, 2024. http://rave.ohiolink.edu/etdc/view?acc_num=osu1721299211219112

    Chicago Manual of Style (17th edition)