Presentation av examensarbete

​Lorents Landgren: Optimal Graphs for Connectedness under Random Edge Deletion


Abstract: Performing percolation on a finite graph G means independently keeping or discarding each edge according to a probability parameter p.
The focus is the probability P_c(G, p) that a percolation outcome turns out to be a connected graph. Specifically, if we fix p, the number of vertices n and the number of edges $m$, we try to find the graph(s) with the highest such probability. We call such graphs the most stable or the (n, m, p)-optimal graphs.
It is shown that any (n, m, p)-optimal graph consists of a single so-called block.

For m = n, m = n + 1 and m = n + 2 respectively, we show the existence of a unique optimal graph, which is actually independent of p.
However, in general, the relative stability of two (n, m)-graphs is p-dependent. We make some investigations into when this is the case.

Handledare: Jeff Steif

​Zoom länk: https://chalmers.zoom.us/j/8923791780

Password: 333222

Kategori Studentarbete
Plats: Online
Tid: 2021-05-21 10:30
Sluttid: 2021-05-21 11:30

Sidansvarig Publicerad: to 20 maj 2021.