## Threshold functions of colorings of random graphs

 dc.contributor.author Lucas, Kim dc.date.accessioned 2024-02-06T08:26:04Z dc.date.available 2024-02-06T08:26:04Z dc.date.issued 2024 dc.description A research report submitted in partial fulfilment of the requirements for the degree Master of Science to the Faculty of Science, School of Mathematics, University of the Witwatersrand, Johannesburg, 2023 dc.description.abstract Threshold Functions of Colorings of Random Graphs By Elizabeth Jonck, Kim Lucas, and Ronald Maartens. Let Fn,p be the set of all graphs with n vertices, m edges and with probability p = p(n) of an edge occurring independently. Each graph G ∈ Fn,p has probability P[G] = p m(1 − p) ( n 2)−m of occurring. This is called the Binomial Random Graph Model, denoted G(n, p). Let G now be a connected graph. A rainbow colored graph is when every two vertices of V (G) are connected by a path where each edge has a unique color. If Q is an increasing property, then a function t = t(n) is called the threshold function for Q if (i) p << t so that limn→∞(P[G has property Q]) = 0, and (ii) p >> t so that limn→∞(P[G has property Q]) = 1. A function f(n) is called the sharp threshold function for the property Q if there exists constants C and c such that G satis es Q almost surely for p ≥ Cf(n), and G almost surely does not satisfy Q for p ≤ cf(n). In this dissertation, we investigate threshold functions and sharp threshold functions of random graphs to be rainbow colored. dc.description.librarian TL (2024) dc.faculty Faculty of Science dc.identifier.uri https://hdl.handle.net/10539/37512 dc.language.iso en dc.school Mathematics dc.subject Colorings dc.subject Random graphs dc.title Threshold functions of colorings of random graphs dc.type Dissertation
##### Original bundle
Now showing 1 - 1 of 1
Name:
602808_K_Lucas_MSc_Final_Submission.pdf
Size:
881.91 KB
Format: