Arnosti's RANDOM-VERTEX versus RANKING conjecture for greedy matching
In Nick Arnosti's random bipartite matching model, each job has a prescribed degree and independently samples a uniform feasible subset of the bins. Every bin has the same positive integer capacity C. RANDOM-VERTEX chooses a uniformly random available feasible bin for each job; RANKING uses one shared random priority order of the bins. Both process jobs in an independent uniform random arrival order. The conjecture following Theorem 2 asks whether RANDOM-VERTEX stochastically dominates RANKING in matching size for every C > 2. The paper proves equality in distribution for C = 1 and stochastic dominance for C = 2.
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Randomized matching algorithms; stochastic dominance
- Posed by
- Nick Arnosti, Greedy Matching in Bipartite Random Graphs, conjecture after Theorem 2, p. 136 (online 2021; journal 2022).
- Year posed
- 2021
- Years open
- 5y
- Solved
- 2026-10-05
- Model
- OpenAI Codex (GPT-6 Astra)
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Significance
- 7 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
For every finite instance in the stated model, every common capacity and every threshold , we prove The comparison holds for fixed arrival and bin-priority orders independent of the neighborhoods; averaging gives Arnosti's random-order model, including the conjectured regime.
The proof combines capped-load association, a two-bin coefficient identity, a saturation bound, refined histories and coupling at accepted-job counts. The written proof uses Cohen–Sackrowitz (1987), Lemma 4.1; Lean proves the required finite rational association statement directly. The inequality compares matching-size distributions. It does not assert dominance on every run, conditional on an arbitrary fixed graph, or for unequal capacities.
What the AI did
OpenAI Codex (GPT-6 Astra) selected and investigated the conjecture, developed the central mathematical argument, simplified the written proof using a published association theorem, and built the Lean formalization, verification tooling and interactive exposition. The human collaborator directed the research, set the requirement for a proof covering all capacities, requested simplification and formal verification, and reviewed the presentation. The contribution label refers to the model developing the central proof; it does not claim publication priority or independent human mathematical verification.
Verification
Read by this site on 6 October 2026, not rebuilt. 91 modules with mathlib, Lean 4.34.0. Outside deliberately negative control files, no sorry, admit, axiom declarations or native_decide. The final theorem source_matching_tail_comparison assumes only degree at most m; its definitions match the paper's model: independent uniform neighbourhoods of the prescribed degrees, a uniform arrival order, one shared uniform priority order for RANKING, uniform choice among available feasible bins for RANDOM-VERTEX, and equal capacities. The repository's axiom log lists only propext, Classical.choice and Quot.sound. At that review, only author-provided build logs were available. A separate exact computation written here over 600 random instances with capacity 1 to 4 found no violation of the tail inequality, strict dominance in 241 of them and equality at capacity 1, as Arnosti's Theorem 2 predicts. The 91-module proof itself was not read.
Author update: the linked public GitHub Actions run rebuilt all 91 positive modules from commit c521b8d, rejected 1 false control, and printed the final theorem's axioms: propext, Classical.choice and Quot.sound. Permanent compiler records and source hashes are in the repository. This does not replace an independent expert audit.
Sources
- PaperComplete mathematical proof (LaTeX manuscript)
- Lean proofFormal source-model theorem in LeanPublic Lean build and final axiom output
- CodeGitHubLean build certificate and axiom audit
- Problem recordOriginal conjecture: after Theorem 2, p. 136
- OtherInteractive proof and dependency mapReproduction instructions and trust scope
Submitted by ZestyRaven517 on