Graph theory & combinatorial proof — flashcards

A sign-reversing pairing on partitions that cancels almost every term, leaving the pentagonal number theorem's sparse recurrence. The general principle: a recurrence needing little memory is not an easier problem, it is a harder theorem — the near-total cancellation has to be proved.

In an antipodally-labelled triangulation of the n-ball, with labels ±1,…,±n and antipodal boundary vertices carrying opposite-signed labels, some edge joins two vertices with the same value and opposite sign. The combinatorial, Sperner-style statement equivalent to Borsuk–Ulam.

A necklace with k types of jewels, each present in an even number of beads, can be fairly split between two thieves using at most k cuts — and k is tight: arranged as k contiguous blocks, one per type, every block needs an internal cut, so 'at most k' cannot be improved in general.

Finding a fair two-thief split of a necklace is PPA-complete already at the simplest case — two thieves, the friendliest group action a proof by Borsuk–Ulam could ask for. Filos-Ratsikas & Goldberg, 2018 (arXiv:1805.12559). This refutes the hypothesis that k-thief difficulty tracks the availability of free ℤ/k actions on spheres: hardness is present at the friendliest case there is, so it is an artefact of the topological proof route rather than an obstruction inherent to the problem.

Two results, and the 2026-09 mining pass corrected the statement of both. (1) THE ONE-SIDED LEMMA. The bound is A_c(t) <= ceil(t*rho_c): no color ever runs more than one bead ahead of its proportional share. It is ONE-SIDED, and the natural two-sided version — a matching lower bound A_c(t) >= floor(t*rho_c) — is FALSE, with an explicit counterexample at x >= 4 reaching a deficit of 23/22. Earlier filings named the lemma 'one-sided' without stating the inequality or recording that the symmetric version fails, which left the asymmetry looking like a proof artifact rather than a fact about the construction. (2) THE MIDPOINT-EXACTNESS THEOREM. At the checkpoint t = y/2 the split is exactly fair. (3) 'GREEDY' NAMES AN INVARIANT CLASS, NOT AN ALGORITHM. The result does not depend on the argmax tie-break — it holds for ANY rule that only ever serves a color with non-negative deficit. The argmax largest-remainder rule is one member of that class and was previously filed as if it were the hypothesis; the tie-break question was explicitly asked in lemma-harvest-prompt.md section 3, the answer came back as the broader class, and this entry did not move until the 2026-09 mining pass. Corrected 2026-08 (retained): an earlier version wrongly conditioned this on a discrepancy statistic D <= 4/3. That statistic was never computed for greedy-built arrangements at all — only for independent random ones, in a separate, unrelated, single-batch numerical experiment (400 trials, three colors, twelve beads, not reproduced or tested at other sizes) with no completed proof behind it. The two results were conflated in translation from a summary and are unrelated.

For 3-color, 12-bead balanced necklace arrangements (4 beads of each color), exhaustive enumeration of all 34,650 distinct arrangements shows c(w)=1 ⟹ D ≤ 4/3, with no exceptions, and the bound is tight — 4/3 is achieved. The converse, once believed and stated on this map, is false: D ≤ 4/3 does not imply c(w)=1. 10,584 of the 34,650 arrangements (about 30%) have D ≤ 4/3 yet require two or three cuts, and fixing D at exactly 1 does not even determine c(w) — it splits close to evenly between one cut and two. D is necessary but far from sufficient.

The Bak–Tang–Wiesenfeld sandpile model (1987), run on an L=60 lattice with threshold 4 over 40,000 grain drops, produces avalanches spanning four orders of magnitude (sizes 1 to 11,194) with no external tuning. Dhar's abelian sandpile group (D. Dhar, 1990) identifies recurrent sandpile configurations with spanning trees of the underlying graph via the Matrix-Tree theorem — verified directly on a 2×2 grid, where brute-force enumeration gives 192 recurrent configurations, exactly matching the determinant of the reduced graph Laplacian (192) computed independently via linear algebra. Separately, a fixed-energy (undriven, periodic-boundary) variant locates a genuine absorbing-to-active phase transition at ζ_c≈2.1–2.2, and the driven sandpile's self-organized density (ζ≈2.10) lands on that independently-located transition point.

Fabian Franklin, 1881.

Albert W. Tucker, 1946.

Charles Goldberg and Douglas West, 1985.

Aris Filos-Ratsikas and Paul Goldberg, 2018.

The stolen-necklace argument solves the continuous division problem first — cuts anywhere on a real interval — and recovers the discrete, integer-bead necklace by sliding each cut to the nearest bead boundary. The discrete problem is an un-arbitrary restriction of the continuous one, arrived at from outside the transcript this schema was originally admitted from.

A discrete, antipodally-labelled triangulation of the ball (Tucker, 1946) is the combinatorial equivalent of a continuous antipodal map on the sphere (Borsuk–Ulam, 1933) — the same relation Sperner's lemma has to Brouwer's fixed point theorem. The via is the whole edge: encode a necklace cut as a point on Sⁿ so that the antipodal map exactly swaps the two thieves, and the topological theorem hands back a fair division for free.

Partial. No direct interpretation the way binomial coefficients count something outright, but one step removed — through the Genocchi and zigzag numbers, both of which do have direct combinatorial meanings. A correspondence that holds once you're willing to go via an intermediate object.

Recorded as conjectural: expected, not proved.

REFUTED at the level asked. Checked against Maynard's actual definition of an admissible tuple, and the objects are not the same. A real connection was found one level up instead — at the level of technique (moment methods), not of the objects themselves. The surface-level naming match was the wrong place to look.

Recorded as refuted: this edge was drawn and then withdrawn.

Counting and structure on discrete objects; proof techniques native to finite mathematics.