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