A lower bound on the concentration of χ(G_{n,1/2})

Behr, Ewa (2022) A lower bound on the concentration of χ(G_{n,1/2}). Bachelor's Thesis, Mathematics.

Preview	Text bMATH_2022_BehrEM.pdf Download (468kB) | Preview
	Text toestemming.pdf Restricted to Registered users only Download (125kB)

Abstract

Graph theory is a field within discrete mathematics, which is concerned with graphs and their properties. A graph whose set of edges is determined randomly is called a random graph. Such graphs are researched in the field of random graph theory, which lies at an intersection of graph theory and probability theory. The central concept of this paper is the chromatic number. The chromatic number of a graph is the minimum number of colors which one needs to use to color the vertices of the graph in such a way that whenever a pair of vertices is connected by an edge, those two vertices are assigned different colors. Clearly, in case of a random graph, its chromatic number is a random variable. This thesis explains Annika Heckel's article ``Non-concentration of the chromatic number of a random graph". The article provides a revolutionary result on the lower bound on the concentration of the chromatic number of the binomial random graph $G_{n, 1/2}$. While the majority of research has been focused on finding an upper bound on the length of the interval where the chromatic number lies with high probability, Heckel is the first to provide a non-trivial lower bound. In this thesis, we provide an introduction into graph theory and random graph theory, followed by the history of research into the bounds on the chromatic number of random graphs. Finally, we walk the reader through Annika Heckel's proof and raise some open questions related to the chromatic number of random graphs.

Item Type:	Thesis (Bachelor's Thesis)
Supervisor name:	Muller, T.
Degree programme:	Mathematics
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	15 Jul 2022 12:14
Last Modified:	15 Jul 2022 12:14
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/27863

Actions (login required)

View Item