Extremal graph theory

Extremal graph theory is a branch of mathematics.

In the narrow sense, extremal graph theory studies the graphs which are "extremal" among graphs with a certain property. There are various meanings for the word "extremal": with the largest number of edges, the largest minimum degree, the smallest diameter, etc. In a broader sense, various other related questions can be included into extremal graph theory. In that case, the term extremal graph theory can encompass a large part of graph theory.

A typical result in extremal graph theory is Turán's theorem. It answers the following question. What is the maximum possible number of edges in an undirected graph "G" with "n" vertices which does not contain "K"_"3" (three vertices "A", "B", "C" with edges "AB", "AC", "BC"; i.e. a triangle) as a subgraph? The bipartite graph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains:$leftlfloor\; frac\{n^2\}\{4\}\; ight\; floor$ edges. Similar questions have been studied with various other subgraphs "H" instead of "K"_"3"; for instance, the Zarankiewicz problem concerns the largest graph that does not contain a fixed complete bipartite graph as a subgraph. Turán also found the (unique) largest graph not containing "K"_"k" which is named after him, namely Turán graph. This graph has :$leftlfloor\; frac\{(k-2)\; n^2\}\{2(k-1)\}\; ight\; floor\; =\; leftlfloor\; left(\; 1-\; frac\{1\}\{k-1\}\; ight)\; frac\{n^2\}\{2\}\; ight\; floor$ edges. For "C"_"4", the largest graph on "n" vertices not containing "C"_"4" has :$left(frac\{1\}\{2\}+o(1)\; ight)\; n^\{3/2\}$ edges.

ee also

*Ramsey's theorem

References

# Béla Bollobás. "Extremal Graph Theory". New York: Academic Press, 1978.
# Béla Bollobás. "Modern Graph Theory", chapter 4: Extremal Problems. New York: Springer, 1998.
#
# M. Simonovits, Slides from the Chorin summer school lectures, 2006. [http://www.renyi.hu/~miki/BerlinG.pdf]