Extremal graph theory

EN Texto em inglês Ainda não há artigo no teu idioma: trecho em inglês.

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. 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 can a parameter of a graph be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory. 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) giving the maximum number of edges in a triangle-free graph, and Turán's theorem (1941) extending this to graphs without any clique of some fixed size, 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 theorem (1946), on the number of edges in graphs with a forbidden subgraph of any type. This result is surprising because it connects the chromatic number with the maximal number of edges in an H {\displaystyle H} -free graph. An alternative proof of the Erdős–Stone theorem was given in 1975, and utilised the Szemerédi regularity lemma, an essential technique in the resolution of extremal graph theory problems.