Metric Dimensions of March Madness Brackets Sam Spiro Abstract Say you and some friends decide to make brackets for March Madness and are told how each of your brackets scored. The question we ask is: when can you determine how the actual tournament went given your scores? We determine the exact minimum number of brackets needed to do this for any March Madness-style tournament regardless of the scoring system used, and more generally we prove effective bounds for the problem for arbitrary single-elimination tournaments. 1 Introduction March Madness . One of the biggest events in American sports is March Madness , which is a single-elimination basketball tournament played by the top college teams in March. A popular component of this event is fans filling out brackets of predictions for which teams they think will win each match of the tournament. The ideal goal is to make a bracket where every prediction is correct. However, given that there are 63 matches that need to be guessed correctly, it is unsurprising that no one has ever achieved this 2^{-63} probability event despite tens of millions of brackets being made each year and considerable cash prizes being offered for anyone who could achieve this feat. While it is essentially impossible to construct a perfect bracket, one can still try and make one which is as accurate as possible and, more importantly, which is more accurate than that of any of your friends. To this end, it is common for people to form groups (known as pools) where each participant makes a bracket of predictions. At the end of the tournament, each bracket is given a score based on how accurate their predictions were, and the participant with the highest score is declared the winner of the pool. There is no singular standard way for how brackets are scored, though two common scoring systems are to award some scalar multiple of either i or 2^{i} points for each correct guess made in round i . In this paper we will unfortunately not be able to answer the question of how to make a bracket which scores higher than any of your friends. Instead we ask a different question: if you are given some set of brackets from a pool along with the scores that each of these brackets received, under what conditions can you reconstruct how the tournament actually went? For example, if one of your friends makes a bracket which scores 0 points, then you can immediately determine from this who wins every match in round 1 (namely, every team which your unlucky friend said would lose in round 1), but you can not say anything about what happens in any of the later rounds of the tournament from this information alone. Metric Dimensions . This problem, while whimsical on the surface, lies within the well-studied field of metric dimensions. Given a metric space (X,d) , we say that a set of points \{x_{1},\ldots,x_{t}\}\subseteq X is a resolving set if every x\in X can be uniquely identified by the sequences of distances (d(x,x_{1}),\ldots,d(x,x_{t})) , and the metric dimension of the metric space is the smallest size of a resolving set. In this language, our problem can be restated as asking when a set of brackets is a resolving set for the metric space (X,d) where X is the set of all brackets and where (informally) d(B,B^{\prime}) measures how much the predictions made by brackets B,B^{\prime} differ from each other in terms of the number of points that they score. There is a lot of work in the literature dedicated to metric dimensions and resolving sets. One of the first problems in this field is a coin-weighing problem due to Erdős and Renyi from 1963 [ 4 ] which received a fair amount of attention [ 7 , 11 , 13 ] . However, the most popular area of study for metric dimensions is the setting where X is the vertex set of a graph G and d(u,v) is the distance between the vertices u,v in G . This graphical setting was introduced independently by Slater [ 12 ] and by Harary and Melter [ 8 ] , and since then there has been a tremendous amount of work on these problems, in part due to the many applications of metric dimensions to real-world problems from fields such as chemistry [ 2 ] , robotics [ 9 ] , and network analysis [ 1 ] . We refer the reader to the surveys [ 10 , 16 ] for a more comprehensive overview of metric dimensions and their applications. Other Tournaments . The most common single-elimination tournaments are those like March Madness which have some 2^{r} teams with each team playing the same number of rounds, but there are other kinds that can be considered. Indeed, many single-elimination tournaments rely on bye matches when the number of teams is not a power of two, creating asymmetries between the participants. Some single-elimination tournaments even purposelessly create biases for certain teams, with notable examples being the tournaments appearing in the series Yu Yu Hakusho and Hunter X Hunter by Yoshihiro Togashi. One can also consider tournaments where matches are played by more than two teams, which is typical for games such as Mahjong or Texas hold’em. To capture all of these kinds of tournaments, we need to make some formal definitions. 1.1 Definitions Our definition of single-elimination tournaments is expressed in the language of digraphs. For this we recall that given a digraph \vec{S} and a vertex v of this digraph, N^{+}(v) denotes the set of vertices w such that v\to w is a directed edge of \vec{S} , and N^{-}(v) denotes the set of vertices u such that u\to v is a directed edge. We say that v is a sink if N^{+}(v)=\emptyset and that v is a source if N^{-}(v)=\emptyset . Definition 1 . A single-elimination tournament 1 1 1 We will sometimes colloquially refer to single-elimination tournaments simply as “tournaments”, though we emphasize that this is unrelated to the more usual notion of a tournament in the study of digraphs. \vec{S} is a directed graph on a finite number of vertices with the following properties: (a) \vec{S} contains exactly one sink, (b) |N^{+}(v)|=1 for every vertex v of \vec{S} which is not a sink, (c) \vec{S} contains no directed cycles, i.e. no sequence of distinct vertices (v_{1},\ldots,v_{t}) with t\geq 2 , v_{1}=v_{t} , and v_{i+1}\in N^{+}(v_{i}) for all 1\leq i0} . We also will make use of the following related definitions: • Given two brackets B,B^{\prime} of \vec{S} , we define their \sigma -score by \mathrm{score}_{\sigma}(B,B^{\prime})=\sum_{x\in M(\vec{S}):B(x)=B^{\prime}(x)}\sigma(x). • We say that a set of brackets \mathcal{B}=\{B_{1},\ldots,B_{t}\} is a \sigma -resolving set if for all pairs of distinct brackets B,B^{\prime} , there exists B_{i}\in\mathcal{B} with \mathrm{score}_{\sigma}(B_{i},B)\neq\mathrm{score}_{\sigma}(B_{i},B^{\prime}) . • We let \dim(\vec{S},\sigma) denote the minimum size of a \sigma -resolving set and refer to this quantity as the metric dimension of (\vec{S},\sigma) . We note that the function d(B,B^{\prime}):=\sum_{x\in M(\vec{S})}\sigma(x)-\mathrm{score}_{\sigma}(B,B^{\prime}) defines a metric, and hence a resolving set with respect to \mathrm{score}_{\sigma} is the same as a resolving set with respect to this metric. 1.2 Main Results Metric Dimensions . The first question we tackle is: given a single-elimination tournament \vec{S} and a scoring system \sigma , what is \dim(\vec{S},\sigma) , the smallest size of a \sigma -resolving set? To start, we consider standard single-elimination tournaments \vec{S} like those in March Madness. If such a tournament has n players, then apriori \dim(\vec{S},\sigma) could be as large as the number of brackets 2^{n-1} . Perhaps surprisingly, it turns out that \dim(\vec{S},\sigma) is substantially smaller than this and, even more so, is independent of the choice of the scoring system \sigma . Theorem 1.1 . If \vec{S} is a standard single-elimination tournament on n players with n\geq 2 a power of 2, then for every scoring system \sigma we have \dim(\vec{S},\sigma)=\frac{n}{2}. Moreover, for all n there exists a set of n/2 brackets \mathcal{B} which is \sigma -resolving for every \sigma . Theorem 1.1 follow from more general upper and lower bounds on \dim(\vec{S},\sigma) for arbitrary choices of \vec{S} . Our strongest upper bound Theorem 5.23 is too technical to state here, so we instead record one of its corollaries which says that \dim(\vec{S},\sigma) is always strictly less than the number of players for every choice of \vec{S} and \sigma . Theorem 1.2 . For every single-elimination tournament \vec{S} with n players and any scoring system \sigma , we have \dim(\vec{S},\sigma)\leq n-1. This bound is best possible for arbitrary \vec{S} , as can be seen by considering any tournament with only 1 match. Our general lower bound requires a definition to state, but has the advantage of being tight for every single-elimination tournament \vec{S} for at least one choice of \sigma . Definition 5 . A sequence of vertices (u_{1},\ldots,u_{t}) of a digraph \vec{S} is a directed walk from u_{1} to u_{t} if u_{i+1}\in N^{+}(u_{i}) for all 1\leq i(1-q_{\mathrm{pair}})N. Proof. For two distinct players a,b , let \mathcal{B}_{a,b} be the set of brackets B with B(x_{a,b})\notin\{a,b\} . By Proposition 4.3 , each of the sets \mathcal{B}_{a,b} fails to be a resolving set of \vec{S} for any choice of \sigma , and hence \mathrm{res}(\vec{S},\sigma)>\max_{a,b}|\mathcal{B}_{a,b}|=\max_{a,b}N-\Pr[R(x_{a,b})\in\{a,b\}]N=(1-q_{\mathrm{pair}})N, where the first equality used that the number of brackets with B(x_{a,b})\in\{a,b\} is exactly \Pr[R(x_{a,b})\in\{a,b\}]N since R is uniformly random. ∎ This technical bound turns out to imply our simpler lower for \mathrm{res}(\vec{S},\sigma) given in Theorem 1.4 . Corollary 4.6 . Let \vec{S} be a single-elimination tournament on at least two players with source z . Let R be a uniformly random bracket of \vec{S} and define q_{\max}=\max_{a\in P(\vec{S})}\Pr[R(z)=a] . If there are a total of N brackets for \vec{S} , then for any scoring system \sigma we have \mathrm{res}(\vec{S},\sigma)>(1-2q_{\max})N. Proof. We aim to show that q_{\mathrm{pair}}\leq 2q_{\max} , from which the result will follow by Proposition 4.5 . We claim that there exist distinct players a,b with z=x_{a,b} . Indeed, z has at least two in-neighbors u,u^{\prime} by definition of single-elimination tournaments. Let a\in P(u) and b\in P(u^{\prime}) be arbitrary players, which exist by Proposition 3.3 (i). By Proposition 3.3 (v) we have that u,u^{\prime} are the unique in-neighbors of z which have a,b in their player sets, so taking u_{a}=u and u_{b}=u^{\prime} verifies that z satisfies the conditions of x_{a,b} , proving the claim. With a,b as above, we find q_{\mathrm{pair}}\leq\Pr[R(z)\in\{a,b\}]=\Pr[R(z)=a]+\Pr[R(z)=b]\leq 2q_{\max}, proving the result. ∎ We now establish our lower bound for \dim(\vec{S},\sigma) as stated in Theorem 1.3 . Proposition 4.7 . For every single-elimination tournament \vec{S} and any scoring system \sigma , we have \dim(\vec{S},\sigma)\geq\max_{x\in M(\vec{S})}\left(|P(x)|-\max_{u\in N^{-}(x)}|P(u)|\right). Proof. Let \mathcal{B} be an arbitrary \sigma -resolving set, and assume for contradiction that there exists a match x\in M(\vec{S}) with |\mathcal{B}|<|P(x)|-\max_{u\in N^{-}(x)}|P(u)| . For each u\in N^{-}(x) , let \mathcal{B}_{u}\subseteq\mathcal{B} be the set of brackets B with B(x)=B(u) , noting that the \mathcal{B}_{u} sets partition \mathcal{B} since by definition of being a bracket, B(x)\in\{B(u):u\in N^{-}(x)\} and we have B(u)\neq B(u^{\prime}) for distinct u,u^{\prime}\in N^{-}(x) by Proposition 3.3 (v) and Lemma 3.5 (i). We claim that there exist at least two vertices u\in N^{-}(x) such that |\mathcal{B}_{u}|<|P(u)| . Indeed, if this inequality held for exactly one vertex u^{\prime} then |\mathcal{B}|=\sum_{u\in N^{-}(x)}|\mathcal{B}_{u}|\geq\sum_{u\in N^{-}(x)\setminus\{u^{\prime}\}}|P(u)|=|P(x)|-|P(u^{\prime})|, with this last equality using Proposition 3.3 (v). This contradicts the assumption that |\mathcal{B}|0 by definition of scoring systems. In total we find that \mathrm{score}_{\sigma}(\widehat{B}_{a},B)-\mathrm{score}_{\sigma}(\widehat{B}_{b},B)>\mathrm{score}_{\sigma}(\widehat{B}_{a},B^{\prime})-\mathrm{score}_{\sigma}(\widehat{B}_{b},B^{\prime}), which implies that either \mathrm{score}_{\sigma}(\widehat{B}_{a},B)\neq\mathrm{score}_{\sigma}(\widehat{B}_{a},B^{\prime}) or \mathrm{score}_{\sigma}(\widehat{B}_{b},B)\neq\mathrm{score}_{\sigma}(\widehat{B}_{b},B^{\prime}) , a contradiction to our hypothesis. We conclude the result. ∎ To effectively use this lemma we will need to strengthen Lemma 5.9 as follows. Lemma 5.18 . Let \vec{S} be a single-elimination tournament on at least 2 vertices and u\in V(\vec{S}) . If A\subseteq P(\vec{S})\setminus P(u) is a set of players with the property that for every a\in A there exists b\in A\setminus\{a\} such that b\in P(x) for every match x with a\in P(x) , then for any bracket \widetilde{B} of \vec{S}_{u} there exists a bracket \widehat{B} of \vec{S} such that the following holds: (i) \widehat{B} equals \widetilde{B} when restricted to V(\vec{S}_{u}) and \widehat{B}(x)\notin P(u) for all x\in M(\vec{S})\setminus P(\vec{S}_{u}) , (ii) Condition (i) continues to hold for \widehat{B}_{c} for all c\notin P(u) , and (iii) For every a\in A there exists some b\in A\setminus\{a\} such that the unique out-neighbor x_{a}\in N^{+}(a) has b\in\{\widehat{B}(v):v\in N^{-}(x_{a})\} . Proof. By Lemma 5.9 there exists a bracket \widehat{B}^{0} for \vec{S} which satisfies (i), and moreover Lemma 5.9 shows that any bracket satisfying (i) also satisfies (ii). Letting A=\{a_{1},\ldots,a_{t}\} , we iteratively define \widehat{B}^{i}=\widehat{B}_{a_{i}}^{i-1} and take \widehat{B}:=\widehat{B}^{t} . That is, we define \widehat{B} by taking \widehat{B}^{0} and changing it so that a_{1} wins every match it can, then changing this so that a_{2} wins every match that it can, and so on. Note that Lemma 5.9 guarantees that (i) and (ii) iteratively holds for all \widehat{B}^{i} , so it remains to check (iii). To this end, consider any a\in A . Because a\in P(x_{a}) , we have by hypothesis that there exists some b^{\prime}\in P(x_{a})\setminus\{a\} . By Proposition 3.3 (v) this means there exists some v\in N^{-}(x_{a}) with b^{\prime}\in P(v) and necessarily a\notin P(v) since a\in N^{-}(x_{a}) has b^{\prime}\notin P(a)=\{a\} . Observe that by construction, \widehat{B}(v)=a_{j} for the largest j with a_{j}\in P(v) , noting that such a j must exist because b^{\prime}\in A\cap P(v) and that a_{j}\neq a since a\notin P(v) . We conclude that (iii) holds with b=a_{j} . ∎ We now state our main technical result for this subsection. Proposition 5.19 . Let \vec{S} be a single-elimination tournament, u\in V(\vec{S}) a vertex, \mathcal{B}_{u} a non-empty set of brackets for \vec{S}_{u} , and \mathcal{A} a partition of P(\vec{S})\setminus P(u) such that for every a\in P(\vec{S})\setminus P(u) , the set A\in\mathcal{A} with a\in A has some b\in A\setminus\{a\} such that b\in P(x) for every match x with a\in P(x) . Then there exists a set of brackets \mathcal{B} for \vec{S} with |\mathcal{B}|=|P(\vec{S})\setminus P(u)|+\max\{0,|\mathcal{B}_{u}|-|\mathcal{A}|\}, such that \mathcal{B} is a \sigma -resolving set whenever \mathcal{B}_{u} is a \sigma_{u} -resolving set. Proof. The result is trivial if \vec{S} has a single vertex, so we assume from now on that \vec{S} has at least 2 vertices. Let \mathcal{A}=\{A_{1},\ldots,A_{t}\} and \mathcal{B}_{u}=\{\widetilde{B}^{1},\ldots,\widetilde{B}^{m}\} be as in the hypothesis. For some slight ease of notation we first prove the result under the assumption t\leq m , after which we briefly discuss the minor changes needed to make this argument work for t>m . For each 1\leq i\leq t , let \widehat{B}^{i} denote the bracket obtained by applying Lemma 5.18 with respect to \widetilde{B}=\widetilde{B}^{i} and A=A_{i} , and for each tt , and if i\leq t we let a\in A_{i} be arbitrary and take B=\widehat{B}^{i}_{a}\in\mathcal{B} . This verifies condition (a). It remains then to show condition (c) of Proposition 5.5 . To this end, consider any a\in P(\vec{S})\setminus P(u) , say with a\in A_{i} . By Lemma 5.18 , there exists some b\in A_{i}\setminus\{a\} such that the unique out-neighbor x_{a}\in N^{+}(a) has b\in\{\widehat{B}^{i}(v):v\in N^{-}(x_{a})\} . It follows from Lemma 5.14 that any two brackets B,B^{\prime} with the same \sigma -scores with respect to \widehat{B}^{i}_{a},\widehat{B}^{i}_{b}\in\mathcal{B} have B(x)=a if and only if B^{\prime}(x)=a . We conclude that (c) holds, and hence that \mathcal{B} is \sigma -distinguishing by Proposition 5.5 . We now briefly consider the case m\leq t . For each 1\leq i\leq m , let \widehat{B}^{i} denote the bracket obtained by applying Lemma 5.18 with respect to \widetilde{B}=\widetilde{B}^{i} and A=A_{i} , and for each m