Matpic
mathematics, in pictures
The collection

Every essay — page 26

Page 26 of 26, continuing through the fields in the same order.

Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search

Applied

A rule for choosing, stated exactly, and what it forces on whoever adopts it.

The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance.

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

7 figures The duality theorem's four cases, counted over 6,561 small programs. A three-by-three table crossing the status of a linear program — optimal, unbounded or infeasible — with the status of its dual, counting every small program with coefficients from minus one to one. Five of the nine cells are empty.

When one of the two numbers is missing

The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.

5 figures The optimum as the lowest of 3 lines, one per dual vertex. The optimal value of a linear program plotted against one right-hand side, drawn over a family of straight lines, one for each vertex of the dual feasible region. The optimum follows the lowest line throughout.

The lines the optimum lies under

Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.

6 figures The nearest consistent verdict: a 3-way tie at distance 4. A table of the 4 consistent judgement sets on the agenda p, q, and p and q, each with its number of disagreements with each of 3 judges and the total; the smallest total is marked.

The nearest consistent verdict

When a court's majorities contradict each other, one repair is to announce the consistent verdict that disagrees with the judges least. It treats the premises and the conclusion alike, which neither of the two standard procedures does. On the classic case it returns a three-way tie; on five judges, with every question weighted equally, it never returns a single answer on a troubled profile at all — and what breaks the tie is a decision about which question matters more.

5 figures · new Which agendas majority can vote on safely. A table of 7 agendas with the size of their largest minimally inconsistent set and the count of inconsistent majority outcomes over all profiles of three and five judges.

Agendas that cannot contradict themselves

A court voting on two unconnected questions never contradicts itself, and neither does one voting on a chain of thresholds. A court voting on two premises and their conjunction sometimes does. What separates them is the size of the smallest sets of judgements that cannot all be true: pairs are harmless, because two majorities always share a judge, and triples are not. The same count says exactly how large a supermajority has to be to stay consistent on any agenda.

6 figures · new