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 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 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 Eleven vertices, no triangle, four colours. Grötzsch graph: 11 vertices, 20 edges, triangle-free; 3-colouring search 27 nodes, none; 4-colouring 10120121230; proper 4-colourings 12480 (520 up to relabelling).

No triangle, and four colours

A graph that contains four mutually joined points needs four colours. The converse looks obvious — a graph needing four colours should contain something like that — and it is false. Grötzsch's graph has eleven points, no three of them mutually joined, and needs four colours. Mycielski found a step that adds one colour to any graph without creating a triangle, so graphs with no triangle can need any number of colours, and their need is spread through the whole graph, with no part to point at.

discrete · Graph colouring

Named alongside it

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

Exhaustive searchCliqueExtremal graphTuran graphChromatic numberComplete bipartiteEdge countEdge densityGraph colouringIndependent setInequality

All concepts