Extremal graph theory

Extremal graph theory is a branch of mathematics that studies how global properties of a graph influence local substructure. It encompasses a vast number of results that describe how do certain graph properties - number of vertices (size), edge density, chromatic number, and diameter (girth), for example - guarantee the existence of certain local substructures.

The Turán graph T(n,r) is an example of an extremal graph. It has the maximum possible number of edges for a graph on n vertices without (r + 1)-cliques. This is T(13,4).

One of the main objects of study in this area of graph theory are extremal graphs, which are maximal or minimal with respect to some global parameter, and such that they contain (or do not contain) a local substructure- such as a clique, or an edge coloring.

Examples

Extremal graph theory can be motivated by questions such as the following:

Question 1. What is the maximum possible number of edges in a graph on $n$ vertices such that it does not contain a cycle?

If a graph on $n$ vertices contains at least $n$ edges, then it must also contain a cycle. Moreover, any tree with $n$ vertices contains $n-1$ edges and does not contain cycles. Therefore, the answer to this question is $n-1$, and trees are the extremal graphs.

Question 2. If a graph on $n$ vertices does not contain any triangle subgraph, what is the maximum number of edges it can have?

Mantel's Theorem provides that the answer to this question is $\lfloor n^{2}/4\rfloor$. The corresponding extremal graph is a complete bipartite graph on $(\lceil n/2\rceil ,\lfloor n/2\rfloor )$vertices, namely, such that each of the sets differ in size in at most 1.

A generalization of Question 2 follows:

Question 3. Let $r$ be a positive integer. How many edges must there be in a graph $G$ on $n$ vertices in order to guarantee that, no matter how the edges are arranged, the clique $K_{r}$ can be found as a subgraph?

The answer to this question is ${\frac {r-2}{r-1}}\cdot {\frac {n^{2}}{2}}+1$ and it is given by Turán's Theorem. A consequence is that if a graph $G$ on $n$ vertices is $K_{r+1}$-free, it can have at most $\left\lfloor {\frac {(r-2)n^{2}}{2(r-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1}{r-1}}\right){\frac {n^{2}}{2}}\right\rfloor$ edges; the extremal graph satisfying this is the Turán graph, shown in the figure above. It is the complete join of $r-1$ independent sets (with sizes as equal as possible).

The following question is a generalization of Question 3 for not-complete graphs:

Question 4. Let $r$ be a positive integer, and $H$ a non-complete graph. How many edges must there be in a graph $G$ on $n$ vertices in order to guarantee that, no matter how the edges are arranged, $H$ is embedded as a subgraph?

The answer to this question is given by the Erdős–Stone theorem.

Several foundational results in extremal graph theory answer questions which follow this general formulation:

Question 5. Given a graph property $P$, an invariant $u$, and a set of graphs ${\mathcal {S}}$, we wish to find the minimum possible value of a global graph parameter $m$ such that every graph in ${\mathcal {S}}$ with $u>m$ possess property $P$.

In Question 1, for instance, $H$ corresponds to the set of $n$-vertex graphs, $P$ to the property of being cyclic, $u$ to the count of edges parameter, and $m=n-1$.

History

Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians.

Bollobás (2004)

Mantel's Theorem (1907) and Turan's Theorem (1941) were some of the first milestones in the study of Extremal graph theory. In particular, Turan's theorem would later on become a motivation for the finding of results such as the Ërdos-Stone-Simonovits Theorem (1946). This result is surprising because it connects the chromatic number parameter with the maximal number of edges in an $H$-free graph. An alternative proof of Ërdos-Stone-Simonovits was given in 1975, and utilised Szemerédi's Theorem, an essential technique in the resolution of extremal graph theory problems.

Density results and density inequalities

A global parameter which has a pivotal role in extremal graph theory is edge density; for a graph $G=(V,E)$, its edge density is defined as

$t(K_{2},G)=|E|/{\binom {|V|}{2}}$.

In general, for a graph $H$, its density is defined as $t(H,G)=({\text{number of copies of }}H{\text{ in }}G)/{\binom {n}{|v(H)|}}$

The theorems mentioned above can be rephrased in terms of edge density. For instance, Mantel's Theorem implies that the edge density of a triangle-free subgraph is at most $1/2$. Turan's theorem implies that edge density of $K_{r+1}$-free graph is at most $(r-1/r)+o(1)$.

Moreover, Ërdos-Stone-Simonovits Theorem states that

${\mbox{ex}}(n;H)=\left(1-{\frac {1}{\chi (H)-1}}+o(1)\right){n \choose 2},$

where $ex(n;H)$ is the maximal number of edges that an $H$-free graph on $n$ vertices can have and $\chi (H)$ is the chromatic number of $H$. A quantitative implication of this result is that the edge density of an $H$-free graph is asymptotically $1-(1/\chi (H)-1)$.

Another result by Ërdos, Reyni and Sós (1966) shows that graph on $n$ vertices not containing $C_{4}$ as a subgraph has at most the following amount of edges.

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

For more information,

Minimum degree conditions

The preceding theorems give conditions for a small object to appear within a (perhaps) very large graph. Another kind of extremal graph problems consist in looking for conditions that guarantee the existence of a structure that covers every vertex. Note that it is even possible for a highly dense graph in $n$ vertices and

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

edges to have an isolated vertex, even though almost every possible edge is present in the graph.

Edge counting conditions give no indication as to how the edges in the graph are distributed, leading to results which only find bounded structures on very large graphs. It is then more useful in some occasions to consider the minimum degree parameter, which is defined by

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

A large minimum degree removes the possibility of having some '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).

An extremal graph theory result related to this graph parameter 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
• Graph Density Inequalities

Open questions

Even though many important observations have been made in the field of extremal graph theory, several questions still remain unanswered. For instance, Zarankiewicz problem asks what is the maximum possible number of edges in a bipartite graph on $n$ vertices which does not have complete bipartite subgraphs of size $m$ and still remains open.

References

• Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1.
• Bollobás, Béla (1998), Modern Graph Theory, Berlin, New York: Springer-Verlag, pp. 103–144, ISBN 978-0-387-98491-9.
• Diestel, Reinhard (2010), Graph Theory (4th ed.), Berlin, New York: Springer-Verlag, pp. 169–198, ISBN 978-3-642-14278-9, archived from the original on 2017-05-28, retrieved 2013-11-18.
• M. Simonovits, Slides from the Chorin summer school lectures, 2006. [1]