|
Graphs are fairly simple objects with extremely complex properties, which show up in applications from optimization to coding theory and from networks to sampling. Colorability, planarity, connectivity: these are all very important properties which describe the "neighborhood" structure of a graph, and speak about the "closeness" of the vertices. This class will take a look at some of these properties, together with their applications. We will start with simple ones, like planarity (with the K_5 and K(3,3) theorem), and toward the end of the course we will introduce the random graph G(n,p), one of the most celebrated discrete models and a wondeful tool in graph theory. |