betaFeedback

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 mm players gets a card on which is printed a subset of E:={1,…,n}E := \{1,\ldots,n\}. The bingo caller has a box filled with nn balls, on which the numbers from 1 to nn 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:

  1. No bingo card is empty. In other words, no one shouts “Bingo!” before the game even starts.

  2. Every player has a nonzero chance of winning. In other words, no card is a proper subset of another one.

  3. 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.

A mathematical bingo deck showing six cards

Figure 1. A mathematical bingo deck: each of the six cards is a subset of E={1,2,3,4,5,6,7,8,9}E = \{1,2,3,4,5,6,7,8,9\}.

Three examples

Before defining what a matroid actually is, let us look at three examples. (Note that we previously identified EE with {1,…,n}\{1,\ldots,n\}, but now it is convenient to allow more general labels for the elements of EE.)

  • In graphic bingo, the balls are the edges of a connected finite graph GG and the cards are the cycles of GG. 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 GG, but now the cards are the bonds of GG: minimal sets of edges whose removal disconnects the graph. If we assume that GG 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 v1,…,vnv_1,\ldots,v_n 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 MM on a finite set EE is a collection C\mathcal{C} of subsets of EE, called circuits, satisfying three axioms:

(C1) ∅∉C\varnothing\notin\mathcal{C}.

(C2) If C1,C2∈CC_1,C_2\in\mathcal{C} and C1⊆C2C_1\subseteq C_2, then C1=C2C_1=C_2.

(C3) If C1,C2∈CC_1,C_2\in\mathcal{C}, C1≠C2C_1\ne C_2, and e∈C1∩C2e\in C_1\cap C_2, there exists C3∈CC_3\in\mathcal{C} such that C3⊆(C1∪C2)∖{e}C_3\subseteq(C_1\cup C_2)\setminus\{e\}.

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 C1C_1 and C2C_2 are two different cards sharing a label ee. Imagine that the caller first calls every label in (C1∪C2)∖{e}(C_1\cup C_2)\setminus\{e\} and then calls ee. If no other card had already been completed, then calling ee would complete both C1C_1 and C2C_2 at the same moment, creating a tie. So the no-tie rule says that before ee is called, some other card C3C_3 must already have been completed. In other words, C3⊆(C1∪C2)∖{e}C_3\subseteq(C_1\cup C_2)\setminus\{e\}, which is exactly axiom (C3). Conversely, suppose that the first bingo is a tie between distinct cards C1C_1 and C2C_2, both completed when ee is called. Axiom (C3) produces a circuit C3⊆(C1∪C2)∖{e}C_3\subseteq(C_1\cup C_2)\setminus\{e\}. But every element of C3C_3 was called before ee, so C3C_3 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 MM be a matroid on EE, with ∣E∣=n|E| = n, and suppose the bingo cards are the circuits of MM.2

A set I⊆EI \subseteq E in a matroid MM is called independent if it contains no circuit. In bingo language, this means that if only the labels in II 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 MM, denoted r(M)r(M) (or just rr when the context is clear). Our assumption that there is at least one circuit is equivalent to the statement that r(M)<nr(M) < n.

Let

it(M):=#{I⊆E:∣I∣=t, I is independent},i_t(M) := \#\{I \subseteq E : |I| = t,\ I\text{ is independent}\},

and let TT be the round on which the first bingo occurs. After tt calls, the called set is a uniformly random tt-element subset of EE. The game has not ended by then exactly when that subset is independent. Therefore

Pr⁡(T>t)=it(M)(nt)(1)\Pr(T > t) = \frac{i_t(M)}{\binom{n}{t}} \tag*{(1)}

Thus the expected length of the game is

E[T]=∑t≥0t⋅Pr⁡(T=t)=∑t≥0Pr⁡(T>t)=∑t=0r(M)it(M)(nt).\begin{aligned} \mathbb{E}[T] &= \sum_{t\ge0} t\cdot\Pr(T=t) \\ &= \sum_{t\ge0} \Pr(T>t) \\ &= \sum_{t=0}^{r(M)} \frac{i_t(M)}{\binom{n}{t}}. \end{aligned}

So the whole game-clock distribution depends only on nn, rr, and the independent-set numbers i0(M),i1(M),…,ir(M)i_0(M),i_1(M),\ldots,i_r(M).

These numbers are among the most widely studied numerical invariants of a matroid.

For t≥1t\ge1, define the suspense level just before the ttht^{\text{th}} call to be

ht:=Pr⁡(T=t∣T>t−1).h_t := \Pr(T=t\mid T>t-1).

Thus hth_t is the probability that the ttht^{\text{th}} call ends the game, conditional on the game having survived the first t−1t-1 calls. (Probabilists call this a hazard rate, but “suspense” feels better suited to a non-lethal game like bingo.) Using (1), we find that

ht=1−Pr⁡(T>t)Pr⁡(T>t−1)=1−it(M)/(nt)it−1(M)/(nt−1)(2)h_t = 1-\frac{\Pr(T>t)}{\Pr(T>t-1)} =1-\frac{i_t(M)/\binom{n}{t}}{i_{t-1}(M)/\binom{n}{t-1}} \tag*{(2)}

for 1≤t≤r+11\le t\le r+1.

tt1234567
hth_t.000.000.024.081.186.3971

Table 1. The suspense levels for the bingo deck of Figure 1, which has rank r=6r=6 on n=9n=9 elements. Note that the sequence hth_t 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 a0,a1,a2,…,ada_0, a_1, a_2, \ldots, a_d of nonnegative real numbers is called log-concave if

at2≥at−1at+1a_t^2 \ge a_{t-1}a_{t+1}

for t=1,…,d−1t = 1, \ldots, d-1. When the ata_t’s are all positive, this is equivalent to saying that the ratios at/at−1a_t/a_{t-1} 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 MM is a matroid of rank rr on nn elements, then the sequence it(M)(nt)\frac{i_t(M)}{\binom{n}{t}} is log-concave for t=0,…,nt = 0, \ldots, n.

Equivalently, for all 1≤t≤n−11 \le t \le n - 1,

(it(M)(nt))2≥(it−1(M)(nt−1))(it+1(M)(nt+1)).\left(\frac{i_t(M)}{\binom{n}{t}}\right)^2 \ge\left(\frac{i_{t-1}(M)}{\binom{n}{t-1}}\right)\left(\frac{i_{t+1}(M)}{\binom{n}{t+1}}\right).

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

S(t):=Pr⁡(T>t)=it(M)(nt).S(t) := \Pr(T > t) = \frac{i_t(M)}{\binom{n}{t}}.

If r=r(M)r = r(M), then S(t)>0S(t) > 0 for 0≤t≤r0 \le t \le r and S(t)=0S(t) = 0 for all t>rt > r. Formula (2) says

ht=1−S(t)S(t−1)h_t = 1 - \frac{S(t)}{S(t-1)}

for 1≤t≤r1 \le t \le r, while hr+1=1h_{r+1} = 1 (since every (r+1)(r+1)-element set is dependent).

The strong Mason theorem tells us that S(0),S(1),…,S(r+1)S(0), S(1), \ldots, S(r+1) is log-concave, and thus the ratios S(t)/S(t−1)S(t)/S(t-1) are weakly decreasing for 1≤t≤r+11 \le t \le r+1. Hence the sequence h1,h2,…,hr+1h_1, h_2, \ldots, h_{r+1} 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 {2,5,7,9}\{2,5,7,9\} and {3,4,6,8,9}\{3,4,6,8,9\}, it turns out that you are better off choosing the latter. Indeed,

Pr⁡(34689 wins)=37252>1390=Pr⁡(2579 wins)\operatorname{Pr}(34689\ \text{wins}) = \frac{37}{252} > \frac{13}{90} = \operatorname{Pr}(2579\ \text{wins})

since 37252≈0.1468\frac{37}{252} \approx0.1468 and 1390≈0.1444\frac{13}{90} \approx0.1444.

Our paper also proves that, for any fixed card CC, the probability that CC wins in round tt 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. [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. [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. [3]Matthew Baker, Hope Dobbelæere, Brennan Fullmer, and Patrik Gajdoš, Matroid bingo, arXiv:2509.02832, 2025.arxiv.org/abs/2509.02832
  4. [4]Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser, 2003.
  5. [5]Petter Brändén and June Huh, Lorentzian polynomials, Annals of Mathematics 192 (2020), 821–891.arxiv.org/abs/1902.03719
  6. [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.

Paper details

vlnc:W_2sp9dqkv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents