Extremal graph theory

Extremal graph theory is a branch of mathematics, more specifically of graph theory. In a narrow sense, extremal graph theory studies extremal graphs with a certain property. Extremality can be taken with respect to different parameters of graphs, such as order, size or girth. Foundational results in extremal graph theory include Turán's theorem and the Erdős–Stone theorem.

History

Extremal graph theory started in 1941 when Turán proved his theorem determining those graphs of order n, not containing the complete graph K_k of order k, and extremal with respect to size (that is, with as many edges as possible). Another crucial year for the subject was 1975 when Szemerédi proved his result a vital tool in attacking extremal problems.

Basic example

The following are equivalent: G is tree, G is minimally connected, and G is maximally acyclic.

Density results

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₃ (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

$\left\lfloor {\frac {n^{2}}{4}}\right\rfloor$

edges. Similar questions have been studied with various other subgraphs H instead of K₃; 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

$\left\lfloor {\frac {(k-2)n^{2}}{2(k-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1}{k-1}}\right){\frac {n^{2}}{2}}\right\rfloor$

edges. For C₄, the largest graph on n vertices not containing C₄ has

$\left({\frac {1}{2}}+o(1)\right)n^{3/2}$

edges.

Minimum degree conditions

The preceding theorems give conditions for a small object to appear within a (perhaps) very large graph. At the opposite extreme, one might search for conditions which force the existence of a structure which covers every vertex. But it is possible for a graph with

${\binom {n-1}{2}}$

edges to have an isolated vertex - even though almost every possible edge is present in the graph - which means that even a graph with very high density may have no interesting structure covering every vertex. Simple edge counting conditions, which give no indication as to how the edges in the graph are distributed, thus often tend to give uninteresting results for very large structures. Instead, we introduce the concept of minimum degree. The minimum degree of a graph G is defined to be

$\delta (G)=\min _{v\in G}d(v).$

Specifying a large minimum degree removes the objection that there may be a few 'pathological' vertices; if the minimum degree of a graph G is 1, for example, then there can be no isolated vertices (even though G may have very few edges).

A classic result is Dirac's theorem, which states that every graph G with n vertices and minimum degree at least n/2 contains a Hamilton cycle.

See also

• Ramsey theory

References

1. Béla Bollobás. Extremal Graph Theory. New York: Academic Press, 1978.
2. Béla Bollobás. Modern Graph Theory, chapter 4: Extremal Problems. New York: Springer, 1998.
3. Weisstein, Eric W. "Extremal Graph Theory". MathWorld.
4. M. Simonovits, Slides from the Chorin summer school lectures, 2006. [1]