One sample suffices for matroid prophet inequalities

OpenAI's theorem (2026) that one independent sample per element suffices for a constant-competitive prophet inequality on every finite matroid, even when the arrival order is chosen by an adversary who sees all samples, values and the rule's random seed; through density expansions, guarded paths of flats, reverse exposure and a marked-pivot count.

Nine lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Prophets, matroids and an almighty adversary
2. Rounding, a maximum rule and candidates
3. Density expansions and paths of flats
4. Layers and a rank bound for every order
5. Disjoint certificates
6. Reverse exposure and safe samples
7. Marked pivots and sign patterns
8. From safe samples to unrevealed rank
9. The final count and a secretary rule

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Finite probability: independence, conditional expectation and the union bound; the course proves the matroid facts it uses.