Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Degeneracy — where it appears

The largest d for which every subgraph of a graph contains a vertex of degree at most d. It is computed in linear time by repeatedly removing a least-connected vertex, and it bounds the work of any enumeration that first points each edge at its busier endpoint.

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

sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

structures · Structure busiest vertexuniform pairsbusiest 16 · Σd² 43,104 · degeneracy 4attachmentbusiest 114 · Σd² 90,296 · degeneracy 4pairs of neighbours examineduniform pairs — every pair18,480uniform pairs — oriented4,090attachment — every pair42,076attachment — oriented3,339V = 1,024, E = 3,072 on both30 triangles and 249 — the answers, which also differ

Two parameters are not enough either

Two graphs on 1,024 vertices with 3,072 edges each — identical in both numbers every bound in this field is written in. Enumerating every pair of neighbours of every vertex costs 18,480 examinations on one and 42,076 on the other. The quantity that separates them is a third parameter, it is computable in linear time, and it appears in no statement of the problem.

graphs · Graph ordered by degreedegeneracy orderthe degeneracy024681012largest out-degreeuniform pairs, degree 452 above duniform pairs, degree 6136 above duniform pairs, degree 1083 above dpreferential attachment, degree 414 above dpreferential attachment, degree 622 above dpreferential attachment, degree 1058 above d1,024 verticesdashed: the degeneracy

A bound right for the wrong reason

Orient every edge of a graph towards its higher-degree endpoint and count triangles among out-neighbours, and the work is O(E·d), where d is the graph's degeneracy. The usual reason given is that the orientation keeps every out-degree at most d. On a graph of 1,024 vertices with degeneracy four, 136 vertices have more than four out-neighbours and one has seven. The bound survives by a different argument, and the orientation that does keep every out-degree at most d does less work.

graphs · Graph

Named alongside it

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

Counted primitiveDegree distributionHonest limitMeasured countOrientationPreferential attachmentSparse graphTriangle countingWorst caseAmortised analysisBalanceBinary search

All concepts