Matpic
mathematics, in pictures
Concept

Turan graph

The complete multipartite graph whose vertices are split into a given number of parts as equal in size as possible. Turán's theorem says it has the most edges of any graph on those vertices without a clique one larger than the number of parts.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

The most triangle-free edges on 6 points. A graph on 6 points carrying 9 edges and no triangle, found by examining every graph on those points, with the two sides its edges cross between drawn apart.

The edge that forces a triangle

A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.

discrete · Extremal graphs Zykov's moves, from 10 edges to 16. 6 panels showing a graph on 7 points with no complete graph on 4, changed one move at a time; the edge count rises 10, 11, 12, 13, 14, 16 and ends at Turán's graph.

Moves that only ever add edges

Turán's theorem says the densest graph avoiding a complete graph on r + 1 points is the balanced r-part graph. Zykov's proof finds it by a sequence of moves — turn a point into a copy of a better-connected one it is not joined to — each of which adds edges and none of which can create the forbidden clique. A second proof spreads a unit of weight over the points and gets the same bound from a maximum.

discrete · Extremal graphs The fewest triangles a graph can have at each edge density. Razborov's minimum triangle density: 0.55: 0.0730, 0.6: 0.1415, 0.7: 0.2871, 0.75: 0.3750, 0.8: 0.4800, 0.9: 0.7200; it equals Goodman's bound at 1 − 1/t.

The fewest triangles an edge density allows

Half of all possible edges can be drawn without a single triangle. One more, and triangles appear — not one but several at once. Push the density further and the question becomes a curve: for every share of edges, the fewest triangles a large graph can hold. The answer is a string of scallops, touching a simple parabola at the densities of the balanced multipartite graphs and bulging above it between them. It was guessed in the 1980s and proved in 2008 by a method that turns counting into positive-definite matrices.

discrete · Extremal graphs

Named alongside it

The objects these essays reach for when they reach for this one.

Extremal graphCliqueComplete bipartiteEdge countExhaustive searchTriangle-freeConvexityEdge densityGraphIndependent setInequalityInvariant

All concepts