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 |