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, number of edges, edge density, chromatic number, and girth, for example - guarantee the existence of certain local substructures. T is an example of an extremal graph. It has the maximum possible number of edges for a graph on n vertices without -cliques. This is T.
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 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 vertices such that it does not contain a cycle?
If a graph on vertices contains at least edges, then it must also contain a cycle. Moreover, any tree with vertices contains edges and does not contain cycles; trees are the only graphs with edges and no cycles. Therefore, the answer to this question is, and trees are the extremal graphs.
Question 2. If a graph on vertices does not contain any triangle subgraph, what is the maximum number of edges it can have?
Mantel's Theorem answers this question – the maximal number of edges is. The corresponding extremal graph is a complete bipartite graph on vertices, i.e., the two parts differ in size by at most 1.
A generalization of Question 2 follows:
Question 3. Let be a positive integer. How many edges must there be in a graph on vertices in order to guarantee that, no matter how the edges are arranged, the clique can be found as a subgraph?
The answer to this question is and it is answered by Turán's Theorem. Therefore, if a graph on vertices is -free, it can have at most
many edges; the corresponding extremal graph with that many edges is the Turán graph, shown in the figure above. It is the complete join of independent sets.
The following question is a generalization of Question 3, where the complete graph is replaced by any graph :
Question 4. Let be a positive integer, and any graph on vertices. How many edges must there be in a graph on vertices in order to guarantee that, no matter how the edges are arranged, is a subgraph of ?
This question is mostly answered by the Erdős–Stone theorem. The main caveat is that for bipartite, the theorem does not satisfactorily determine the asymptotic behavior of the extremal edge count. For many particular bipartite graphs, determining the asymptotic behavior remains an open problem.
Several foundational results in extremal graph theory answer questions which follow this general formulation:
Question 5. Given a graph property, a parameter describing a graph, and a set of graphs, we wish to find the minimal possible value such that every graph with has property. Additionally, we might want to describe graphs which are extremal in the sense of having close to but which do not satisfy the property.
In Question 1, for instance, is the set of -vertex graphs, is the property of containing a cycle, is the number of edges, and the cutoff is. The extremal examples are trees.

History

Mantel's Theorem and Turán's Theorem were some of the first milestones in the study of Extremal graph theory. In particular, Turán's theorem would later on become a motivation for the finding of results such as the Erdős-Stone-Simonovits Theorem. This result is surprising because it connects the chromatic number with the maximal number of edges in an -free graph. An alternative proof of Erdős-Stone-Simonovits was given in 1975, and utilised the Szemerédi regularity lemma, an essential technique in the resolution of extremal graph theory problems.

Density results and inequalities

A global parameter which has an important role in extremal graph theory is subgraph density; for a graph and a graph, its subgraph density is defined as
.
In particular, edge density is the subgraph density for :
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. Turán's theorem implies that edge density of -free graph is at most.
Moreover, the Erdős-Stone-Simonovits theorem states that
where is the maximal number of edges that an -free graph on vertices can have, and is the chromatic number of. An interpretation of this result is that the edge density of an -free graph is asymptotically.
Another result by shows that graph on vertices not containing as a subgraph has at most the following number of edges.

Minimum degree conditions

The theorems stated above give conditions for a small object to appear within a very large graph. Another direction in extremal graph theory is looking for conditions that guarantee the existence of a structure that covers every vertex. Note that it is even possible for a graph with vertices and 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. This provides motivation for considering the minimum degree parameter, which is defined as
A large minimum degree eliminates 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.
An extremal graph theory result related to the minimum degree parameter is Dirac's theorem, which states that every graph with vertices and minimum degree at least contains a Hamilton cycle.
Another theorem says that if the minimum degree of a graph is, and the girth is, then the number of vertices in the graph is at least

Some 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 vertices which does not have complete bipartite subgraphs of size.
Another important conjecture in extremal graph theory was formulated by . It is conjectured that if is a bipartite graph, then its graphon density is at least.