Optimal Graphs for Connectedness under Random Edge Deletion

Typ
Examensarbete för masterexamen
Program
Publicerad
2021
Författare
Landgren, Lorents
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
random graph theory, percolation on finite graphs, connected outcome, combinatorics and graph theory, Erdos–Rényi model, stability ordering, optimal graph
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material