WorksMathematics
Suspense and surprise in matroid bingo
Abstract
We present the game of Matroid Bingo and prove that it gets more suspenseful the longer the game goes on.
Consider the following minimalist version of the game of bingo. Each of the players gets a card on which is printed a subset of . The bingo caller has a box filled with balls, on which the numbers from 1 to inclusive are written (without duplications). The caller repeatedly draws a uniformly random ball from among those remaining in the box, without replacement, and reads out its number. Each player who has that number on their card crosses it out. The caller continues this process, selecting balls at random until someone calls out “Bingo!”, signifying that they have crossed out all the numbers on their card.
The company printing the cards wants the game to be mathematically elegant, so it imposes the following three rules:
No bingo card is empty. In other words, no one shouts “Bingo!” before the game even starts.
Every player has a nonzero chance of winning. In other words, no card is a proper subset of another one.
There can never be a tie. Equivalently, for every possible ordering of the balls, there is a unique card that is completed first.
One can check that the deck of cards shown in Figure 1 satisfies all three rules. Call such a deck of cards a mathematical bingo deck. Our first surprise is that mathematical bingo decks are the same thing as matroids.

Figure 1. A mathematical bingo deck: each of the six cards is a subset of .
Three examples
Before defining what a matroid actually is, let us look at three examples. (Note that we previously identified with , but now it is convenient to allow more general labels for the elements of .)
In graphic bingo, the balls are the edges of a connected finite graph and the cards are the cycles of . As the caller chooses edges at random, we imagine adding those
edges to the graph one at a time. The first player to complete a cycle on their card shouts “Bingo!” The game continues exactly when the set of edges that have been called so far forms a forest.1
In cographic bingo, we again start with a finite graph , but now the cards are the bonds of : minimal sets of edges whose removal disconnects the graph. If we assume that is connected and think of called edges as being removed from the graph, rather than added, then the game ends as soon as connectivity is broken. Thus, graphic bingo asks when a random edge process first creates a cycle, while cographic bingo asks when random edge deletion first disconnects the graph.
In vector bingo, the balls are distinct non-zero vectors in a finite-dimensional vector space over some field. The cards are the minimal linearly dependent subsets, and the game ends whenever some set of called-out vectors is linearly dependent.
Matroids were invented to capture the common structure behind examples like these.
Matroids as mathematical bingo decks
With those examples in mind, here is a precise definition of matroids.
Definition 0.1. A matroid on a finite set is a collection of subsets of , called circuits, satisfying three axioms:
(C1) .
(C2) If and , then .
(C3) If , , and , there exists such that .
The first two axioms are precisely the first two bingo rules: the empty set is not a card, and no card contains another. The third axiom (called the circuit elimination axiom) is the no-tie rule in disguise. Indeed, suppose and are two different cards sharing a label . Imagine that the caller first calls every label in and then calls . If no other card had already been completed, then calling would complete both and at the same moment, creating a tie. So the no-tie rule says that before is called, some other card must already have been completed. In other words, , which is exactly axiom (C3). Conversely, suppose that the first bingo is a tie between distinct cards and , both completed when is called. Axiom (C3) produces a circuit . But every element of was called before , so was already complete — a contradiction.
In other words, a mathematical bingo deck is the same thing as the collection of circuits of a matroid. Matroid theorists call this a cryptomorphism: a different-looking axiom system which nevertheless defines the same object. Matroids have many cryptomorphic definitions—in terms of independent sets, bases, rank functions, flats, closure operators, and more. Mathematical bingo (which from now on we will refer to as Matroid Bingo) provides a particularly intuitive cryptomorphism.
The game clock
Now let us ask the question:
How long should we expect the game to last?
Let be a matroid on , with , and suppose the bingo cards are the circuits of .2
A set in a matroid is called independent if it contains no circuit. In bingo language, this means that if only the labels in have been called so far, then no one has won the game yet. The largest possible size of an independent set is called the rank of , denoted (or just when the context is clear). Our assumption that there is at least one circuit is equivalent to the statement that .
Let
and let be the round on which the first bingo occurs. After calls, the called set is a uniformly random -element subset of . The game has not ended by then exactly when that subset is independent. Therefore
Thus the expected length of the game is
So the whole game-clock distribution depends only on , , and the independent-set numbers .
These numbers are among the most widely studied numerical invariants of a matroid.
For , define the suspense level just before the call to be
Thus is the probability that the call ends the game, conditional on the game having survived the first calls. (Probabilists call this a hazard rate, but “suspense” feels better suited to a non-lethal game like bingo.) Using (1), we find that
for .
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| .000 | .000 | .024 | .081 | .186 | .397 | 1 |
Table 1. The suspense levels for the bingo deck of Figure 1, which has rank on elements. Note that the sequence is weakly increasing.
We now ask the question:
Does bingo get more suspenseful as time goes on?
And now for another surprise: to answer this question, we must turn to a deep recent advance in matroid theory which is connected to both June Huh’s 2022 Fields Medal and Shayan Oveis Gharan’s 2026 Abacus Medal.
Combinatorial Hodge theory
A sequence of nonnegative real numbers is called log-concave if
for . When the ’s are all positive, this is equivalent to saying that the ratios are weakly decreasing.
The strong version of Mason’s conjecture, which was proved independently in [5 Theorem 4.14] and [2 Theorem 1.2], says:
Theorem 0.2 (Mason’s conjecture, strong form). If is a matroid of rank on elements, then the sequence is log-concave for .
Equivalently, for all ,
The proof of the strong Mason theorem is part of one of the most exciting recent stories in algebraic combinatorics, namely the emergence of Hodge-theoretic methods in matroid theory. While the margins of this manuscript are too small to fit the proof, we can at least explain precisely what Mason’s theorem says about our game of bingo.
The main result
Set
If , then for and for all . Formula (2) says
for , while (since every -element set is dependent).
The strong Mason theorem tells us that is log-concave, and thus the ratios are weakly decreasing for . Hence the sequence is weakly increasing. We have thus proved:
Theorem 0.3 (Increasing Suspense Theorem). In any legal game of mathematical bingo, conditional on the game not having ended yet, the probability that the next call ends the game never decreases.
In other words: the longer the game lasts, the more suspense the next ball holds.
Why Hodge theory?
Hodge theory originated in algebraic geometry and topology, where it gives powerful constraints on the cohomology of smooth projective varieties. Among its central consequences are the Hard Lefschetz theorem and the Hodge–Riemann relations, which force certain numerical sequences to be log-concave. Over the last decade, June Huh and his collaborators discovered that matroids possess analogous Hodge-theoretic structures. For example, Adiprasito, Huh, and Katz constructed a Chow ring for matroids and proved Hodge–Riemann relations for it, settling several long-standing log-concavity conjectures [1]. Later developments, including Brändén and Huh’s theory of Lorentzian polynomials [5] and the closely related work of Anari, Liu, Oveis Gharan, and Vinzant on completely log-concave polynomials [2], led to the strong form of Mason’s conjecture used above.
Individual cards
The Increasing Suspense Theorem is purely about the game clock and says nothing about which player is most likely to win. That question is a bit subtler. For example, if one card has fewer numbers on it than another, should you always choose the smaller card?
Our final surprise is that the answer to this question is typically yes, but occasionally no. In joint work with Hope Dobbelaere, Brennan Fullmer, and Patrik Gajdoš, we studied the winning probabilities of individual cards in Matroid Bingo [3]. We found that longer cards can sometimes be more likely to win than shorter ones; we called this a monotonicity violation. Such violations exist, but they are surprisingly rare: among the 385,360 isomorphism classes of matroids on at most nine elements that have at least one circuit — and hence define a nonempty bingo game — exactly 11 exhibit a monotonicity violation. One of these monotonicity violations is depicted in Figure 1: if given a choice between and , it turns out that you are better off choosing the latter. Indeed,
since and .
Our paper also proves that, for any fixed card , the probability that wins in round is log-concave and has no internal zeroes, and in particular it is unimodal. This also requires an application of the strong Mason theorem.
Credits
Matroid Bingo was introduced by Dima Fon-Der-Flaass and is mentioned, for example, in a book by Borovik, Gelfand, and White [4]. It was further explored in [3]. The Increasing Suspense Theorem is new to this note.
Acknowledgments
We thank Hope Dobbelaere, Brennan Fullmer, and Patrik Gajdoš for helpful discussions. The author was supported by NSF grant DMS-2154224 and a Simons Fellowship in Mathematics.
Statement of AI usage
We thank GPT-5.5 Pro for assistance with polishing the exposition in this note, and GPT-5.6 Pro for creating the TikZ figure and proofreading the manuscript.
Email address: [email protected]
School of Mathematics, Georgia Institute of Technology, Atlanta, USA
References
- [1]Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, Annals of Mathematics 188 (2018), 381–452.arxiv.org/abs/1511.02888
- [2]Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, Log-concave polynomials III: Manson’s ultra-log-concavity conjecture for independent sets of matroids, Proceedings of the American Mathematical Society 152 (2024), 1969–1981.arxiv.org/abs/1811.01600
- [3]Matthew Baker, Hope Dobbelæere, Brennan Fullmer, and Patrik Gajdoš, Matroid bingo, arXiv:2509.02832, 2025.arxiv.org/abs/2509.02832
- [4]Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser, 2003.
- [5]Petter Brändén and June Huh, Lorentzian polynomials, Annals of Mathematics 192 (2020), 821–891.arxiv.org/abs/1902.03719
- [6]Philippe Flajolet, Donald E. Knuth, and Boris Pittel, The first cycles in an evolving graph, Discrete Mathematics 75 (1989), no. 1–3, 167–215.