Matpic
mathematics, in pictures
Concept

Independent set

A set of vertices in a graph no two of which are joined by an edge. Counting them by size gives the independence polynomial, and finding the largest is one of the standard hard problems of combinatorial optimisation.

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 A spider's matchings have real roots and its independent sets do not. Spider with legs 3, 3, 3: matching polynomial 1, 9, 27, 32, 12, roots -0.5000, -0.2324, -0.5000, -1.4343; independence polynomial 1, 10, 36, 57, 38, 9, 1, 4 non-real roots.

The roots every matching polynomial keeps real

Count a graph's matchings by size and make the counts the coefficients of a polynomial. On every one of 35,664 graphs tested, that polynomial has only real roots — a theorem of Heilmann and Lieb from 1972. Count independent sets instead and the roots wander off the axis on a growing share of graphs, but never on a graph without a claw, and matchings are the independent sets of a graph that never has one.

discrete · Generating functions

Named alongside it

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

CliqueComplete bipartiteEdge countExhaustive searchExtremal graphGenerating functionInterlacingLog-concavityPerfect matchingReal rooted polynomialTriangle-freeTuran graph

All concepts