Matpic
mathematics, in pictures
Concept

Triangle-free

The property of a graph that no three of its points are joined in pairs. A triangle-free graph on n points has at most a quarter of n squared edges, reached only by two equal halves joined completely, and every denser graph is forced to contain a triangle.

Named by 2 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 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.

Exhaustive searchExtremal graphTuran graphCliqueComplete bipartiteEdge countEdge densityIndependent setInequality

All concepts