An introduction to the theory of random graphs

[摘要] This thesis provides an introduction to the fundamentals of random graph theory. The study starts introduces the two fundamental building blocks of random graph theory, namely discrete probability and graph theory. The study starts by introducing relevant concepts probability commonly used in random graph theory- these include concentration inequalities such as Chebyshev's inequality and Chernoff's inequality. Moreover we proceed by introducing central concepts in graph theory, which will underpin the later discussion. In particular we provide results such as Mycielski's construction of a family of triangle-free graphs with high chromatic number and results in Ramsey theory. Next we introduce the concept of a random graph and present two of the most famous proofs in graph theory using the theory random graphs. These include the proof of the fact that there are graphs with arbitrarily high girth and chromatic number, and a bound on the Ramsey number \(R\)(\(k\); \(k\)). Finally we conclude by introducing the notion of a threshold function for a monotone graph property and we present proofs for the threhold functions of certain properties.

[发布机构] University:University of Birmingham;Department:School of Mathematics

[关键词] Q Science;QA Mathematics