Extreme graph theory

The Turan graph T (n, r) is an example of an extremal graph. The graph has the maximum possible number of edges for graphs with n vertices without (r + 1) - click . The figure shows the graph T (13,4).

Extreme graph theory is a branch of graph theory . Extreme graph theory studies the extremal (maximal or minimal) properties of graphs satisfying certain conditions. Extremeness can refer to different invariants of graphs , such as order, size, or girth. In a more abstract sense, the theory studies how the global properties of a graph affect the local substructures of a graph ^[1] .

Content

Examples

For example, the simple question of extremal graph theory is the question “Which acyclic graphs with n vertices have the maximum number of edges?” Extreme graphs for this question are trees with n vertices that have n - 1 edges ^[2] . A more general, typical question is the following: If a property is given to a graph P , an invariant u ^[3], and a set of graphs H , we want to find a minimal value m , such that any graph from H that has u greater than m has the property P. In the example above, H was a set of graphs with n vertices, P was the property of being a cycle, and u was the number of edges in the graph. Thus, any graph with n vertices and more than n - 1 edges must contain a cycle.

Some functional results in extremal graph theory are questions of the types mentioned above. For example, the question of how many edges of a graph with n vertices must be in the graph, so that it necessarily contains a clique of size k as a subgraph, corresponds to the Turan theorem . If instead of a click in a similar question one asks about complete multipartite graphs, the answer is given by .

History

Extreme graph theory, in the strictest sense, is a branch of graph theory that is loved and developed in Hungary.

- Bollobás, 2004

Extreme graph theory arose in 1941 when Turan proved his theorem , defining graphs of order n , not containing a complete graph K _{k of} order k, and extremal with respect to size (that is, with as few edges as possible) ^[4] . The next key year was 1975, when Szemerédi proved his theorem , an important tool for attacking extreme problems ^[4] .

Graph density

A typical result of extremal graph theory is the theorem of Turan . The theorem answers the following question. What is the maximum possible number of edges in an undirected graph G with n vertices that does not contain K ₃ (three vertices A , B , C with edges AB , AC , BC , that is, a triangle) as a subgraph? A full bipartite graph , in which the lobes differ by a maximum of 1, is the only extremal graph with this property. Count contains

\left\lfloor {\frac {n^{2}}{4}}\right\rfloor

{\ displaystyle \ left \ lfloor {\ frac {n ^ {2}} {4}} \ right \ rfloor}

ribs. Similar questions were posed for various other subgraphs H instead of K ₃ . For example, the Zarankievich problem asks about the largest (by the number of edges) graph that does not contain a fixed full bipartite graph as a subgraph, and asks about the largest graph that does not contain even cycles of a fixed length. Turan also found the (unique) largest graph that does not contain K _k , which is named after him, namely the Count of Turan . This graph is the complete union of "k-1" independent sets and has a maximum

\left\lfloor {\frac {(k-2)n^{2}}{2(k-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1}{k-1}}\right){\frac {n^{2}}{2}}\right\rfloor

{\ displaystyle \ left \ lfloor {\ frac {(k-2) n ^ {2}} {2 (k-1)}} \ right \ rfloor = \ left \ lfloor \ left (1 - {\ frac {1 } {k-1}} \ right) {\ frac {n ^ {2}} {2}} \ right \ rfloor}

ribs. The largest graph with n vertices that does not contain C ₄ has

\left({\frac {1}{2}}+o(1)\right)n^{3/2}

{\ displaystyle \ left ({\ frac {1} {2}} + o (1) \ right) n ^ {3/2}}

ribs.

Minimum grade conditions

The mentioned theorems give conditions for the appearance of small objects inside a (possibly) large graph. As opposite extremes, we can search for a condition that forces the existence of a structure that covers all vertices. But count with

{\binom {n-1}{2}}

{\ displaystyle {\ binom {n-1} {2}}}

edges may have isolated vertices, although almost all possible edges are present in the graph, which means that even very dense graphs may not have the structure of interest to us, covering all the vertices. A simple condition based on the calculation of the ribs does not provide information on how the edges are distributed in the graph, so often such a condition gives uninteresting results for very large structures. Instead, we introduce the concept of a minimal degree. The minimum degree of the graph G is defined as

\delta (G)=\min _{v\in G}d(v).

{\ displaystyle \ delta (G) = \ min _ {v \ in G} d (v).}

The task of a large minimum degree removes the objection that there may be "pathological" vertices. If the minimal degree of a graph G is 1, for example, then there cannot be isolated vertices (even if G contains very few edges).

The classic result is the Dirac theorem , which states that any graph G with n vertices and a minimal degree not less than n / 2 contains a Hamiltonian cycle .

Notes

↑ Diestel, 2010 .
↑ Bollobás, 2004 , p. 9.
↑ Generally speaking, the property of a graph and an invariant are one and the same.
↑ ¹ ² Bollobás, 1998 , p. 104

Literature

Béla Bollobás. Extremal Graph Theory. - New York: Dover Publications , 2004. - ISBN 978-0-486-43596-1 .
Béla Bollobás. Modern Graph Theory. - Berlin, New York: Springer-Verlag , 1998. - p. 103–144. - ISBN 978-0-387-98491-9 .
Reinhard Diestel. Graph Theory . - 4th. - Berlin, New York: Springer-Verlag, 2010. - p. 169–198. - ISBN 978-3-642-14278-9 . Archived copy of May 28, 2017 on Wayback Machine
- Reinhard Distel. Graph theory. - Novosibirsk: Publishing house of the Inst. Of Mathematics, 2002. - ISBN 5-86134-101-X UDC 519.17.
M. Simonovits. Slides from the Chorin summer school lectures, 2006 ..

[_75381c2735966a06-1] Diestel, 2010 .

[_0098d045eca55d0b-2] Bollobás, 2004 , p. 9.

[3] Generally speaking, the property of a graph and an invariant are one and the same.

[_cdeebdb7e8a56b3a-4] ¹ ² Bollobás, 1998 , p. 104