User:Krit-tonkla/sandbox

This is the user sandbox of Krit-tonkla. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

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?^[2] 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.

History[edit]

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 Turán's Theorem (1941) were some of the first milestones in the study of extremal graph theory.^[3] 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 (1946).^[1] This result is surprising because it connects the chromatic number with the maximal number of edges in an $H$ -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.^[3]

Topics and concepts[edit]

Forbidden subgraphs[edit]

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

When $G=K_{r}$ is a complete graph, Turán's theorem gives an exact value for $\operatorname {ex} (n,K_{r})$ and characterizes all graphs attaining this maximum; such graphs are known as Turán graphs. For non-bipartite graphs $G$ , the Erdős–Stone theorem gives an asymptotic value of $\operatorname {ex} (n,G)$ . Determining the asymptotics of $\operatorname {ex} (n,G)$ when $G$ is a bipartite graph is open; when $G$ is a complete bipartite graph, this is known as the Zarankiewicz problem.

Homomorphism density[edit]

The homomorphism density $t(H,G)$ of a graph $H$ in a graph $G$ describes the probability that a randomly chosen map from the vertex set of $H$ to the vertex set of $G$ is also a graph homomorphism. It is closely related to the subgraph density, which describes how often a graph $H$ is found as a subgraph of $G$ . The homomorphism density can also be extended to graph limits, which are objects that arise as a limit of dense graphs.

The forbidden subgraph problem can be restated as maximizing the edge density of a graph with $G$ -density zero, and this naturally leads to generalization in the form of graph homomorphism inequalities, which are inequalities between $t(H,G)$ for various graphs $H$ .

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 $G$ in terms of the edge density of $G$ .

Graph regularity[edit]

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] 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.

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, such as the graph removal lemma and the hypergraph removal lemma.

Graph coloring[edit]

A proper (vertex) coloring of a graph $G$ is a coloring of the vertices of $G$ such that no two adjacent vertices have the same color. The minimum number of colors needed to properly color $G$ is called the chromatic number of $G$ , denoted $\chi (G)$ . 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. Computationally, it is known that determining whether a given graph has a coloring with a prescribed number of colors is NP-hard.

References[edit]

^ ^a ^b Diestel 2010
^ ^a ^b Alon, Noga; Krivelevich, Michael (2008). "Extremal and Probabilistic Combinatorics". In Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.). The Princeton Companion to Mathematics. Princeton, New Jersey: Princeton University Press. pp. 562–575. doi:10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR j.ctt7sd01. LCCN 2008020450. MR 2467561. OCLC 227205932. OL 19327100M. Zbl 1242.00016.
^ ^a ^b Bollobás 1998, p. 104

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]

[:0-1] Diestel 2010

[pcm-2] Alon, Noga; Krivelevich, Michael (2008). "Extremal and Probabilistic Combinatorics". In Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.). The Princeton Companion to Mathematics. Princeton, New Jersey: Princeton University Press. pp. 562–575. doi:10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR j.ctt7sd01. LCCN 2008020450. MR 2467561. OCLC 227205932. OL 19327100M. Zbl 1242.00016.

[b104-3] Bollobás 1998, p. 104

[1]

[2]

[3]