View source for Extremal graph theory

[[File:Turan 13-4.svg|thumb|The [[Turán graph|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''&nbsp;+&nbsp;1)-[[Clique (graph theory)|cliques]]. This is ''T''(13,4).]]
'''Extremal graph theory''' is a branch of [[Combinatorics|combinatorics]], itself an area of [[Mathematics|mathematics]], that lies at the intersection of [[Extremal combinatorics|extremal combinatorics]] and [[Graph theory|graph theory]]. In essence, extremal graph theory studies how global properties of a graph influence local substructure.
<ref name=":0">
{{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url=http://diestel-graph-theory.com/index.html/ | publisher=Springer-Verlag | location=Berlin, New York | edition=4th | isbn=978-3-642-14278-9 | year=2010 | pages=169–198 | access-date=2013-11-18 | archive-url=https://web.archive.org/web/20170528023122/http://diestel-graph-theory.com/index.html | archive-date=2017-05-28 | url-status=dead }}
</ref>
Results in extremal graph theory deal with quantitative connections between various [[Graph property|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?
<ref name="pcm" >
{{Princeton Companion to Mathematics 
  |article=Extremal and Probabilistic Combinatorics 
  |pages=562-575 
  |author1-surname=Alon 
  |author1-given=Noga
  |author2-surname=Krivelevich
  |author2-given=Michael
}}
</ref>
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|spectral graph theory]], [[Computational complexity theory|computational complexity theory]], and [[Additive combinatorics|additive combinatorics]], and frequently employs the [[Probabilistic method|probabilistic method]].

==History==

{{Quote box|quote=Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians.|source=
Bollobás (2004)
<ref>
{{Citation | last1=Bollobás | first1=Béla |  title=Extremal Graph Theory | publisher=[[Social:Dover Publications|Dover Publications]] | location=New York | isbn=978-0-486-43596-1 | year=2004}}
</ref>
|width=300px}}

Mantel's Theorem (1907) and [[Turán's theorem|Turán's Theorem]] (1941) were some of the first milestones in the study of extremal graph theory.
<ref name="b104">
{{Citation | last1=Bollobás | first1=Béla |  title=Modern Graph Theory | publisher=[[Physics:Springer-Verlag|Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98491-9 | year=1998 | pages=103–144}}
</ref> 
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).<ref name=":0" /> This result is surprising because it connects the chromatic number with the maximal number of edges in an <math>H</math>-free graph. 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.<ref name="b104" />
{{-}}

==Topics and concepts==

===Graph coloring===
{{main|Graph coloring}}

[[File:Petersen graph 3-coloring.svg|thumb|right|The [[Petersen graph|Petersen graph]] has chromatic number 3.]]

A '''proper (vertex) coloring''' of a graph <math>G</math> is a coloring of the vertices of <math>G</math> such that no two adjacent vertices have the same color. The minimum number of colors needed to properly color <math>G</math> is called the '''chromatic number''' of <math>G</math>, denoted <math>\chi(G)</math>. 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.<ref name="pcm" />

Two simple lower bounds to the chromatic number of a graph <math>G</math> is given by the [[Clique number|clique number]] <math>\omega(G)</math>—all vertices of a clique must have distinct colors—and by <math>|V(G)|/\alpha(G)</math>, where <math>\alpha(G)</math> is the independence number, because the set of vertices with a given color must form an [[Independent set (graph theory)|independent set]].

A [[Greedy coloring|greedy coloring]] gives the upper bound <math>\chi(G) \le \Delta(G) + 1</math>, where <math>\Delta(G)</math> is the maximum degree of <math>G</math>. When <math>G</math> is not an odd cycle or a clique, [[Brooks' theorem]] states that the upper bound can be reduced to <math>\Delta(G)</math>. When <math>G</math> is a [[Planar graph|planar graph]], the four-color theorem states that <math>G</math> has chromatic number at most four.

In general, determining whether a given graph has a coloring with a prescribed number of colors is known to be NP-hard.

In addition to vertex coloring, other types of coloring are also studied, such as [[Edge coloring|edge colorings]]. The '''chromatic index''' <math>\chi'(G)</math> of a graph <math>G</math> 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 <math>G</math> is either <math>\Delta(G)</math> or <math>\Delta(G)+1</math>.

===Forbidden subgraphs===
{{main|Forbidden subgraph problem}}

The '''forbidden subgraph problem''' is one of the central problems in extremal graph theory. Given a graph <math>G</math>, the forbidden subgraph problem asks for the maximal number of edges <math>\operatorname{ex}(n,G)</math> in an <math>n</math>-vertex graph that does not contain a subgraph isomorphic to <math>G</math>. 

When <math>G = K_r</math> is a complete graph, [[Turán's theorem]] gives an exact value for <math>\operatorname{ex}(n,K_r)</math> and characterizes all graphs attaining this maximum; such graphs are known as [[Turán graph|Turán graphs]]. 
For non-bipartite graphs <math>G</math>, the [[Erdős–Stone theorem]] gives an asymptotic value of <math>\operatorname{ex}(n, G)</math> in terms of the chromatic number of <math>G</math>. 
The problem of determining the asymptotics of <math>\operatorname{ex}(n, G)</math> when <math>G</math> is a [[Bipartite graph|bipartite graph]] is open; when <math>G</math> is a complete bipartite graph, this is known as the [[Zarankiewicz problem]].

===Homomorphism density===
{{main|Homomorphism density}}

The '''homomorphism density''' <math>t(H, G)</math> of a graph <math>H</math> in a graph <math>G</math> describes the probability that a randomly chosen map from the vertex set of <math>H</math> to the vertex set of <math>G</math> is also a [[Graph homomorphism|graph homomorphism]]. It is closely related to the '''subgraph density''', which describes how often a graph <math>H</math> is found as a subgraph of <math>G</math>.

The forbidden subgraph problem can be restated as maximizing the edge density of a graph with <math>G</math>-density zero, and this naturally leads to generalization in the form of '''graph homomorphism inequalities''', which are inequalities relating <math>t(H, G)</math> for various graphs <math>H</math>.
By extending the homomorphism density to [[Graphon|'''graphons''']], which are objects that arise as a limit of [[Dense graph|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 <math>G</math> in terms of the edge density of <math>G</math>.

===Graph regularity===
{{main|Szemerédi regularity lemma}}

[[File:Epsilon regular partition.png|alt=regularity partition|thumb|200x200px|The edges between parts in a regular partition behave in a "random-like" fashion.]]

'''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 graph|random bipartite graphs]].<ref name="pcm" />
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|additive combinatorics]] and [[Computational complexity theory|computational complexity theory]]. In addition to (Szemerédi) regularity, closely related notions of graph regularity such as strong regularity and Frieze-Kannan weak regularity have also been studied, as well as extensions of regularity to hypergraphs. 

Applications of graph regularity often utilize forms of counting lemmas and removal lemmas. In simplest forms, the [[Graph removal lemma#graph counting lemma|graph counting lemma]] uses regularity between pairs of parts in a regular partition to approximate the number of subgraphs, and the [[Graph removal lemma|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.

{{-}}

==See also==

'''Related fields'''
* [[Ramsey theory]]
* [[Ramsey-Turán theory]]
* [[Spectral graph theory]]
* [[Additive combinatorics]]
* [[Computational complexity theory]]
* Probabilistic combinatorics

'''Techniques and methods'''
* [[Probabilistic method]]
* [[Dependent random choice]]
* [[Container method]]
* [[Hypergraph regularity method]]

'''Theorems and conjectures''' (in addition to ones mentioned above)
* [[Ore's theorem]]
* [[Ruzsa–Szemerédi problem]]

==References==
<references/>

[[Category:Extremal graph theory| ]]

{{Sourceattribution|Extremal graph theory}}