Extremal Graph Theory

Extremal graph theory is the study of graphs which have a critical behaviour with respect to some graph parameter within a certain class characterized by some graph property. The typical example that we will consider in this chapter consists in finding the maximum number of edges that a graph can have within the class of graphs which do not contain a fixed subgraph H. The main result in this area is the Erdős–Stone theorem. This theorem provides an asymptotic expression for the maximum number of edges a graph can have which has no subgraph H. This expression depends only on the chromatic number of the graph H. The theorem is not informative when H is bipartite, and the last part of the chapter is devoted to study this case in which finite geometries will reappear.