Optimal Graphs for Connectedness under Random Edge Deletion

dc.contributor.authorLandgren, Lorents
dc.contributor.departmentChalmers tekniska högskola / Institutionen för matematiska vetenskapersv
dc.contributor.examinerSteif, Jeffrey
dc.contributor.supervisorSteif, Jeffrey
dc.date.accessioned2021-08-19T12:10:07Z
dc.date.available2021-08-19T12:10:07Z
dc.date.issued2021sv
dc.date.submitted2020
dc.description.abstractPerforming 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.coursecodeMVEX03sv
dc.identifier.urihttps://hdl.handle.net/20.500.12380/303914
dc.language.isoengsv
dc.setspec.uppsokPhysicsChemistryMaths
dc.subjectrandom graph theory, percolation on finite graphs, connected outcome, combinatorics and graph theory, Erdos–Rényi model, stability ordering, optimal graphsv
dc.titleOptimal Graphs for Connectedness under Random Edge Deletionsv
dc.type.degreeExamensarbete för masterexamensv
dc.type.uppsokH
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
Master Thesis_Lorents Landgren.pdf
Storlek:
2 MB
Format:
Adobe Portable Document Format
Beskrivning:
License bundle
Visar 1 - 1 av 1
Bild saknas
Namn:
license.txt
Storlek:
1.51 KB
Format:
Item-specific license agreed upon to submission
Beskrivning: