Extremal graph theory

Last updated March 31, 2022

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.

History

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

Bollobás (2004) ^[3]

Mantel's Theorem (1907) and Turán's Theorem (1941) were some of the first milestones in the study of extremal graph theory. ^[4] 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).^[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 was given in 1975, and utilised the Szemerédi regularity lemma, an essential technique in the resolution of extremal graph theory problems.^[4]

Topics and concepts

Graph coloring

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

Two simple lower bounds to the chromatic number of a graph $G$ is given by the clique number $\omega (G)$ —all vertices of a clique must have distinct colors—and by $|V(G)|/\alpha (G)$ , where $\alpha (G)$ 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 $\chi (G)\leq \Delta (G)+1$ , where $\Delta (G)$ is the maximum degree of $G$ . When $G$ is not an odd cycle or a clique, Brooks' theorem states that the upper bound can be reduced to $\Delta (G)$ . When $G$ is a planar graph, the four-color theorem states that $G$ 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 colorings. The chromatic index $\chi '(G)$ of a graph $G$ 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 $G$ is either $\Delta (G)$ or $\Delta (G)+1$ .

Forbidden subgraphs

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)$ in terms of the chromatic number of $G$ . The problem of 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

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 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 relating $t(H,G)$ for various graphs $H$ . 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 $G$ in terms of the edge density of $G$ .

Graph regularity

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. 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 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 Research Articles

In combinatorial mathematics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling of a sufficiently large complete graph. To demonstrate the theorem for two colours, let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

The Turán graph, denoted by $, is a complete multipartite graph; it is formed by partitioning a set of vertices into subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where and are the quotient and remainder of dividing by, the graph is of the form, and the number of edges is$

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Perfect graph Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph $is perfect if and only if for all we have .$

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

Kőnigs theorem (graph theory) Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an H-free graph for a non-complete graph H. It is named after Paul Erdős and Arthur Stone, who proved it in 1946, and it has been described as the “fundamental theorem of extremal graph theory”.

In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure S satisfies some property P satisfies a "global" property P, or is "far" from having this property meaning an ε-fraction of the representation of S need be modified in order to make S satisfy P, using only a small number of "local" queries to the object.

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges in an -vertex graph which does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.$

In graph theory and statistics, a graphon is a symmetric measurable function $, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.$

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph $equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.$

In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of crossings of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number $e$ of edges is sufficiently larger than the number $n$ of vertices, the crossing number is at least proportional to $e 3 / n 2$ .

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.

In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number of edges in a balanced bipartite graph whose edges can be partitioned into a linear number of induced matchings, or the maximum number of triples one can choose from $points so that every six points contain at most two triples. The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who first proved that its answer is smaller than by a slowly-growing factor.$

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph $is a parameter that is associated to each graph in the following manner:$

References

1 2 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
1 2 3 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.
↑ Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1
1 2 Bollobás, Béla (1998), Modern Graph Theory, Berlin, New York: Springer-Verlag, pp. 103–144, ISBN 978-0-387-98491-9

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 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

[pcm-2] 1 2 3 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.

[3] Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1

[b104-4] 1 2 Bollobás, Béla (1998), Modern Graph Theory, Berlin, New York: Springer-Verlag, pp. 103–144, ISBN 978-0-387-98491-9

[1]

[2]

[3]

[4]