## Optimal Graphs for Connectedness under Random Edge Deletion

 dc.contributor.author Landgren, Lorents dc.contributor.department Chalmers tekniska högskola / Institutionen för matematiska vetenskaper sv dc.contributor.examiner Steif, Jeffrey dc.contributor.supervisor Steif, Jeffrey dc.date.accessioned 2021-08-19T12:10:07Z dc.date.available 2021-08-19T12:10:07Z dc.date.issued 2021 sv dc.date.submitted 2020 dc.description.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 Pc(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. sv dc.identifier.coursecode MVEX03 sv dc.identifier.uri https://hdl.handle.net/20.500.12380/303914 dc.language.iso eng sv dc.setspec.uppsok PhysicsChemistryMaths dc.subject random graph theory, percolation on finite graphs, connected outcome, combinatorics and graph theory, Erdos–Rényi model, stability ordering, optimal graph sv dc.title Optimal Graphs for Connectedness under Random Edge Deletion sv dc.type.degree Examensarbete för masterexamen sv dc.type.uppsok H
##### Original bundle
Visar 1 - 1 av 1
Hämtar...
Namn:
Master Thesis_Lorents Landgren.pdf
Storlek:
2 MB
Format: