Every pair must be asked

The adversary who hides the edge proved that connectivity cannot be decided without reading every edge, and then said that a sharper statement holds in the adjacency-matrix model: an algorithm that learns about a graph only by asking “are these two vertices joined?” must, in the worst case, ask about every one of the $\binom{V}{2}$ pairs. It said that this is called evasiveness, that the Aanderaa–Karp–Rosenberg conjecture extends it to every non-trivial monotone property of graphs, and that the conjecture is open. It proved none of that, and could not have at the size it drew.

At small sizes none of it has to be argued. The probing game has finitely many positions. At each one every pair is unknown, known absent or known present, so five vertices give $3^{10} = 59{,}049$ positions and six give $3^{15} = 14{,}348{,}907$. For each position the fewest questions that still guarantee an answer can be computed from the positions after it: the algorithm picks the question, the adversary picks the answer, and the value is one more than the best question’s worse outcome. Filled from the fully known graphs backwards, that is the exact decision-tree depth. It is the floor over every algorithm that could ever be written, found by solving the game rather than by bounding it. Two floors that can be added checked a selection floor the same way, by minimax over every set of orderings at sizes where that is possible. The difference here is that the positions are few enough to store, so the solve runs to six vertices rather than a handful of elements.

The line the solver plays has a recognisable shape. The adversary says “absent” to every question unless absent would make the graph impossible to connect, and then it says “present”. Vertices 0, 1 and 2 each get one spoke to vertex 4, every other pair is refused, and the tenth question, whether 3 joins 4, is the one that decides. That is the classical strategy from the proof. The computation did not know the proof. It found the strategy because the strategy is optimal.

The panels’ bottom line says more than the pairs do. At the first question all ten pairs were equally good and at the fifth all six remaining were, and the ties never break. A pair that looks informative, one that could join two separate groups, costs exactly as much as one that looks useless. The questions a sort asks twice found comparisons that were new and still nearly worthless. Here every question is worth the same, and all of them are needed. For an evasive property the order of questions is not a lever at all. Nothing a cleverer algorithm does to its order changes the worst case, because every order reaches it. That is the adaptive counterpart of the sort whose count has no distribution: a sorting network fixes its questions before it sees any answers and pays the same on every input. An algorithm here may adapt to every answer, and on its worst graph adapting gains it nothing.

Fifteen of fifteen, and the two that stop early #

Six vertices is the largest size where every position still fits comfortably in memory, at two bytes a position, and it is enough to ask the question a conjecture is about.

Seven properties of the unlabelled graph and seven fifteens. The list was not chosen to make a point. It includes two that are monotone upward (adding an edge never destroys them), two that are monotone downward (removing one never does), a fifth that is monotone upward for a less obvious reason, since a perfect matching survives any added edge, and two that are not monotone at all. “Every vertex has the same degree” can be created and destroyed by adding a single edge, and so can “an even number of edges”. The conjecture says nothing about those two, and they are evasive anyway.

The last two rows are the controls, and their job is to show that the solver can find a small number when one exists. “Vertex 0 is joined to every other” is monotone and non-trivial, which are two of the conjecture’s three hypotheses. It misses the third: it is not a property of the unlabelled graph, because relabelling vertex 0 changes the answer. The solver gives it five questions, one per pair touching vertex 0, and an algorithm told which vertex matters asks exactly those five and stops at the first absent one. “Vertices 0 and 1 are joined” takes one question, as it should.

If the solver had printed fifteen for those two, every fifteen above them would mean nothing. It printed five and one, and a second implementation checks the result. The same game solved by plain recursion over lists of known pairs, with no position numbering and no table, agrees on every property at three and four vertices. The flags on each property (monotone up or down, invariant or not) are checked the same way, against every graph and every relabelling at four vertices, rather than trusted as typed.

Put that panel beside the connectivity panel and the difference between the two games is visible. On connectivity every question ties. On the labelled property four of ten are optimal and six are mistakes, and the ties shrink from four of ten to one of seven as the line goes on. An evasive property is one on which an algorithm cannot make a mistake that matters, because it cannot make a choice that matters. The labelled property rewards knowing where to look, and it rewards it because knowing where to look is information that the unlabelled graph, by definition, withholds.

Where the square comes from #

The conjecture is usually stated as a lower bound, and at these sizes the bound can be drawn against the thing it bounds.

The two monotone curves separate from the first point, and nothing except the third hypothesis separates them. The labelled property can ignore every pair that does not touch its vertex, and that is $\binom{V-1}{2}$ pairs of the $\binom{V}{2}$. The invariant property has no such pairs, since whatever holds for one vertex holds for all of them. That symmetry drives every proof in the subject. A property that treats all vertices alike cannot let an algorithm write off any region of the matrix, because an adversary can move the one pair that matters anywhere the algorithm has not yet looked.

The floor depends on the model as much as on the question, which is the point the floor moves when the question does made across four questions. With adjacency lists, counting on a graph measured traversals that read a list per vertex and never ask about a pair that is absent. In the matrix model an absent pair has to be asked about like any other.

What has been proved in general stops well short of the square. In 1976 Rivest and Vuillemin showed that every non-trivial monotone property of the unlabelled graph needs a fixed fraction of all pairs, first a sixteenth, a constant later work has raised without reaching one. In 1984 Kahn, Saks and Sturtevant proved full evasiveness whenever the number of vertices is a prime power, with an argument from topology. Three, four and five are all prime powers. Six is the smallest vertex count the theorem does not cover. So the fifteens above, for the five monotone properties in the list, are facts about those properties at six vertices and not an instance of a theorem. They say nothing about the monotone properties that were not asked. Nothing at six vertices is the conjecture. It is seven properties, each settled.

Every property there is, at four vertices #

A list, however varied, is a sample. At four vertices a sample is unnecessary.

A property that renaming cannot change is a set of unlabelled graphs, and there are eleven unlabelled graphs on four vertices, from the empty graph to the complete one. So there are $2^{11} = 2{,}048$ such properties. Two of them are constant, always true or always false, and need no questions. That leaves 2,046, and each game is solved in a fraction of a millisecond.

All 2,046 are evasive. Monotone or not, natural or arbitrary (“is either a triangle plus an isolated vertex, or a path on three edges, or complete”), every one needs all six pairs on its worst graph. Only 44 of them are monotone in either direction. The conjecture covers those 44, and the enumeration finds that the other 2,002 behave the same way.

That is a statement about four vertices, and it is where the enumeration has to stop being exhaustive. Five vertices have 34 unlabelled graphs and so $2^{34}$ properties, about seventeen billion. Checked instead: every property made of one or two unlabelled graphs (595 of them) and 2,000 seeded random sets of unlabelled graphs drawn at five densities. None of the 2,595 is decided in fewer than ten questions. A floor one pass cannot get under could perform its pigeonhole argument completely because the objects were small. This one cannot. The sample is evidence rather than a proof, and the difference matters here, because properties that escape exist. They are not monotone, and known constructions need far more vertices than these.

The parity count is the most useful thing in the figure, because it replaces a search with one sum. It is also Rivest and Vuillemin’s. Take any algorithm that stops before asking every pair. Each place it stops is a set of graphs with some pairs fixed and at least one free. Flipping one free pair pairs each graph in that set with a graph one edge away, so the set holds as many even-edged graphs as odd-edged ones. The property’s graphs are a union of such sets, so its even and odd counts must be equal. If they differ, no early-stopping algorithm exists, and the proof is arithmetic.

At four vertices the arithmetic proves 1,976 of 2,046 properties evasive before any game is played. For connectivity at five vertices the connected graphs number 24 more with an even edge count than with an odd one, so connectivity at five is evasive by subtraction. The 70 silent cases are what the exact solve is for, and they are also the reason the topological proofs exist. The signed count is one number computed from a shape associated with the property. Kahn, Saks and Sturtevant used a much stronger fact about the same shape, one that still holds when this number happens to be zero.

The worst case cannot tell them apart, and the average can #

Every property on the last plate has the same worst case. That is the content of the result, and it is also why the worst case is a poor way to compare them.

The spread is wide. “Has an edge” costs $1.969 = 63/32$ questions on average, because on a random graph the first question has an even chance of finding an edge and ending the search. “An even number of edges” costs exactly six on every graph, because the last pair always changes the answer. Between them sit two thousand properties, all evasive, whose typical costs differ by a factor of three.

The monotone properties sit mostly at the cheap end. One plausible reason, which four vertices cannot confirm, is that a monotone property is certified by a small witness in either direction. A spanning tree proves connected and a closed group proves not connected, as the adversary who hides the edge observed for adjacency lists. An algorithm on a random graph tends to find one of those witnesses long before it has asked everything. A property like “every vertex has the same degree” has no such witness for “yes”. The only certificate is the whole degree sequence, and that takes most of the matrix.

A random graph is not the adversary #

Evasiveness is a worst-case statement, and the worst case here is a single graph an adversary builds one answer at a time. A graph that comes from anywhere else is almost never that graph.

The peaks sit where the answer is most in doubt. At a 40% edge chance a five-vertex graph is connected with probability 0.490, as near an even split as the sweep gets, and that is where connectivity’s optimum average peaks at 6.63 questions of ten. “Has an edge” peaks at the sparse end, where edges are hard to find, and falls towards one question as the first pair asked becomes almost certain to be present. None of the four curves comes within a question and a half of the worst case at any density.

The gap between average and worst grows with size. At an even edge chance the best algorithm for connectivity asks 2.500 of three questions at three vertices, 4.375 of six at four, 6.527 of ten at five and 8.828 of fifteen at six: 83%, 73%, 65% and 59% of the pairs. Evasiveness says the worst case is every pair at each of those sizes. A random graph needs a falling share of them.

That is the same separation a count over every input found for sorting, where the worst ordering of eight elements is one of 40,320 and the benchmark inputs miss it. The difference is in how the worst input is found. For a sort it has to be searched for, and the worst case found by climbing showed how hard that search gets. For an evasive property the adversary constructs it on the fly, against whichever algorithm is playing, which is why no ordering of questions can dodge it.

What the enumeration settles and what it does not #

Five things are established here without any appeal to a proof.

At three, four, five and six vertices, every named property of the unlabelled graph that was solved needs every pair, including properties that are not monotone. At four vertices that holds for every property there is, all 2,046. The two labelled controls come out at $V - 1$ and $1$ at every size, so the solver distinguishes evasive from non-evasive where the distinction exists. A second implementation that shares no code with the sweep agrees at three and four vertices. And the check that refuses “monotone is enough” does refuse it: “vertex 0 is joined to every other” is monotone and needs four of ten at five vertices.

Three things are not established.

The conjecture at six vertices. Seven properties were solved, five of them monotone, out of a space of properties with $2^{156}$ members, one for each set of the 156 unlabelled graphs on six vertices. Six is a size the prime-power theorem does not reach, so each fifteen there is a fact about one property. Proving every monotone property at six evasive would take a search nothing here attempts.

Anything about five vertices beyond the properties checked. 2,595 checked properties out of seventeen billion is a sample, not an enumeration. The parity count applies to each property individually, which is the right way to extend the search. Doing so would mean enumerating properties by their signed count, and the space is too large to enumerate directly.

The randomised floor. Every number here is the best deterministic algorithm, either against an adversary or against one fixed distribution of graphs. A randomised algorithm is a third game, since the adversary must now commit to a graph without knowing the coin flips. The adversary who hides the edge named Yao’s principle as the way to bound it. That principle says the randomised worst case equals the hardest distribution’s deterministic average. The density plate shows one family of distributions, independent edges, and none of them comes near the worst case. Whether some other distribution does is a different question.

Two floors, compared honestly #

The floors field now has two exact floors of different kinds, and the contrast is sharper with both computed.

The floor under every comparison sort comes from counting outcomes: $n!$ orderings, so $\log_2(n!)$ questions, and merge sort gets within a few per cent. It is information-theoretic, and it is loose exactly when a single question cannot halve the remaining possibilities. The probing floor for connectivity has two outcomes and so an information floor of one question, and its true value is every pair. That value comes from the symmetry of the question and not from counting the answers.

What makes the second kind unusual is that it is exactly tight and yet useless as a guide to practice. The average on a random graph is 59% of the pairs at six vertices and falling, and no order of questions reduces the worst case. How close anything gets to the floor measured distance to a floor as a quality of an algorithm. Under an evasive property that distance is zero for every algorithm, so it measures nothing. Algorithms differ only on average, and an average needs a distribution named beside it.

Still open: the distribution that makes the average as bad as the worst #

The randomised question has a concrete form that fits the sizes used here. Yao’s principle says the best randomised algorithm’s worst-case expected cost equals the largest, over all distributions of graphs, of the best deterministic algorithm’s expected cost. For a fixed distribution the second number is exactly what the density plate computes: the same game, averaged instead of maximised. So the randomised floor is a maximisation over distributions of a quantity that is already computable.

At four vertices there are 64 graphs, so a distribution is 64 numbers. The best deterministic algorithm’s expected cost is the smallest of a finite set of linear functions of those numbers, one per decision tree, which makes the maximisation a linear program. It can be solved by adding the tree that is currently best as a new constraint, one at a time, with each tree read off the game solved under the current distribution.

The measurement that follows does that for connectivity, for “has an edge”, and for one property from the silent 70. It asks how far below six the randomised floor sits, and what the hardest distribution looks like. The prediction from this page is that “has an edge” loses nothing: its hardest distribution puts all its weight near the empty graph, where every pair must be asked whatever the coin says. Connectivity should lose something, because no single graph is hard for every ordering of questions at once. The size of that loss at four and five vertices is the first measured value of a quantity the conjecture’s randomised version is about.