## Threshold functions of colorings of random graphs

##### Date

2024

##### Authors

##### Journal Title

##### Journal ISSN

##### Volume Title

##### Publisher

##### 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.

##### 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

##### Keywords

Colorings, Random graphs