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

Connectivity — where it appears

Whether every vertex of a graph can be reached from every other by following edges. Deciding it takes a traversal that reads every edge in the worst case, and a spanning tree certifies a yes while a set of vertices with no edge leaving it certifies a no.

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

Also named here as evasiveness — the same set of essays touches all of them, so they are one junction rather than several.

with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

The adversary who hides the edge

The floor under comparison sorting comes from counting outputs — n! of them, so log₂(n!) comparisons. Connectivity has two outputs, so the same argument gives a floor of one comparison, which is useless. A different kind of argument gives Ω(E), and having both on the site is the point: lower bounds are not one technique.

floors · Floor probe 1: 0–1 absent9 still to ask10 of 10 as good as anyprobe 2: 0–2 absent8 still to ask9 of 9 as good as anyprobe 3: 0–3 absent7 still to ask8 of 8 as good as anyprobe 4: 0–4 present6 still to ask7 of 7 as good as anyprobe 5: 1–2 absent5 still to ask6 of 6 as good as anyprobe 6: 1–3 absent4 still to ask5 of 5 as good as anyprobe 7: 1–4 present3 still to ask4 of 4 as good as anyprobe 8: 2–3 absent2 still to ask3 of 3 as good as anyprobe 9: 2–4 present1 still to ask2 of 2 as good as anyprobe 10: 3–4 absentdecided1 of 1 as good as any5 vertices · 10 pairs · 59,049 states solvedsolid: present · dotted: absent · coloured: this probe

Every pair must be asked

Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.

floors · Floor

Named alongside it

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

AdjacencyAdversary argumentDecision treeEvasivenessLower boundAdjacency listAverage caseCounting argumentDistributionExhaustive searchHonest limitInvariant

All concepts