Extremal graph theory

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory.

In essence, extremal graph theory studies how global properties of a graph influence local substructure.

[1] Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?

Extremal graph theory is closely related to fields such as Ramsey theory, spectral graph theory, computational complexity theory, and additive combinatorics, and frequently employs the probabilistic method.

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

Mantel's Theorem (1907) and Turán's Theorem (1941) were some of the first milestones in the study of extremal graph theory.

An alternative proof of Erdős–Stone was given in 1975, and utilised the Szemerédi regularity lemma, an essential technique in the resolution of extremal graph theory problems.

[4] A proper (vertex) coloring of a graph

Determining the chromatic number of specific graphs is a fundamental question in extremal graph theory, because many problems in the area and related areas can be formulated in terms of graph coloring.

[2] Two simple lower bounds to the chromatic number of a graph

is the independence number, because the set of vertices with a given color must form an independent set.

A greedy coloring gives the upper bound

is not an odd cycle or a clique, Brooks' theorem states that the upper bound can be reduced to

is a planar graph, the four-color theorem states that

is the minimum number of colors in a proper edge-coloring of a graph, and Vizing's theorem states that the chromatic index of a graph

, the forbidden subgraph problem asks for the maximal number of edges

is a complete graph, Turán's theorem gives an exact value for

is a complete bipartite graph, this is known as the Zarankiewicz problem.

describes the probability that a randomly chosen map from the vertex set of

It is closely related to the subgraph density, which describes how often a graph

The forbidden subgraph problem can be restated as maximizing the edge density of a graph with

-density zero, and this naturally leads to generalization in the form of graph homomorphism inequalities, which are inequalities relating

By extending the homomorphism density to graphons, which are objects that arise as a limit of dense graphs, the graph homomorphism density can be written in the form of integrals, and inequalities such as the Cauchy-Schwarz inequality and Hölder's inequality can be used to derive homomorphism inequalities.

A major open problem relating homomorphism densities is Sidorenko's conjecture, which states a tight lower bound on the homomorphism density of a bipartite graph in a graph

Szemerédi's regularity lemma states that all graphs are 'regular' in the following sense: the vertex set of any given graph can be partitioned into a bounded number of parts such that the bipartite graph between most pairs of parts behave like random bipartite graphs.

[2] This partition gives a structural approximation to the original graph, which reveals information about the properties of the original graph.

The regularity lemma is a central result in extremal graph theory, and also has numerous applications in the adjacent fields of additive combinatorics and computational complexity theory.

Applications of graph regularity often utilize forms of counting lemmas and removal lemmas.

In simplest forms, the graph counting lemma uses regularity between pairs of parts in a regular partition to approximate the number of subgraphs, and the graph removal lemma states that given a graph with few copies of a given subgraph, we can remove a small number of edges to eliminate all copies of the subgraph.

Related fields Techniques and methods Theorems and conjectures (in addition to ones mentioned above)