Balanced graphs, threshold functions of random graphs and their co-occurrence

Abstract: Our main goal with this dissertation is to create a solid base on balanced and unbalanced graphs, as well as threshold functions of random graphs for future reference. We begin by performing an in depth study on balanced and unbalanced graphs as well as the two variations strictly balanced and strongly balanced as these graphs occur quite frequently in the literature of Random Graph Theory. Our purpose is to define each of these graphs and then to prove a few important results that will be used later on in the dissertation and for future reference. A very important result that we will prove here is that any graph has a balanced extension, and then we take this result even further by determining the least number of vertices and edges that are required to form a balanced extension. Thereafter we define and study threshold functions of random graphs. We begin by determining when a threshold function will exist and whether this function is unique. A step by step approach is given for the two methods of determining a threshold function, namely the First and Second Moment Method and the Grading Method, and then the first method is illustrated for both uniform random graphs and binomial random graphs. The relationship between the threshold functions of the uniform random graphs and those of the binomial random graphs are also discussed, followed by a comparison between threshold function values and extremal values...M.Sc. (Mathematics