Topics in Random Graph Theory

<p dir="ltr">This thesis explores a range of problems in probabilistic combinatorics and random graph theory, with a focus on structural and coloring properties of sparse random graphs. The unifying thread across the chapters is the use of probabilistic techniques such as moment methods and concentration inequalities to analyze the typical behavior of combinatorial structures in random settings. </p><p dir="ltr">We begin by studying the list chromatic number of the square of a random graph <i>G</i>_<em>n,p</em><i> </i>for <i>p = c/n</i> , establishing tight bounds on the number of colors needed in terms of the maximum degree and neighborhood structure. We then investigate the maximum degree in higher powers of sparse random graphs, analyzing how graph powering impacts local density and connectivity.</p><p dir="ltr"> In subsequent chapters, we develop upper and lower bounds on the chromatic number of higher powers of random graphs, extending classical results to this more complex regime. We also examine a graph process variant inspired by the Achlioptas process, showing how even minor changes in edge selection rules can lead to significantly different threshold phenomena. </p><p dir="ltr">The thesis continues with a constructive probabilistic method for embedding large subgraphs with controlled local structure. Specifically, we require K₄ subgraphs to be purchased in an online graph builder setting under bounded budget constraints. Finally, we analyze an edge-coloring of the random graph with two colors, giving rise to ‘zebraic’ color patterns and yielding novel thresholds for connectivity in this setting. </p><p dir="ltr">Together, these results contribute to the growing understanding of how some structural properties in graphs are shaped by randomness, with implications for coloring, network design, and the general behavior of combinatorial objects under uncertainty.</p>