Search for: All records

In this paper, we study the total displacement statistic of parking functionsfrom the perspective of cooperative game theory. We introduce parking games,which are coalitional cost-sharing games in characteristic function formderived from the total displacement statistic. We show that parking games aresupermodular cost-sharing games, indicating that cooperation is difficult(i.e., their core is empty). Next, we study their Shapley value, whichformalizes a notion of fair cost-sharing and amounts to charging each car forits expected marginal displacement under a random arrival order. Our maincontribution is a polynomial-time algorithm to compute the Shapley value ofparking games, in contrast with known hardness results on computing the Shapleyvalue of arbitrary games. The algorithm leverages the permutation-invariance oftotal displacement, combinatorial enumeration, and dynamic programming. Weconclude with open questions around an alternative solution concept forsupermodular cost-sharing games and connections to other areas incombinatorics. 

In mathematics, counter narratives can be used to fight the dominant narrative of who is good at mathematics and who can succeed in mathematics. Eight mathematicians were recruited to co-author a larger NSF project (RAMP). In part, they were asked to create author stories for an undergraduate audience. In this article, we use narrative analysis to present five polarities identified in the author stories. We present various quotations from the mathematicians’ author stories to highlight their experiences with home and school life, view of what mathematics is, experiences in growth in mathematics, with collaboration, and their feelings of community in mathematics. The telling of these experiences contributes towards rehumanizing mathematics and rewriting the narrative of who is good at and who can succeed in mathematics. 

Let $$G$$ be a graph with vertex set $$\{1,2,\ldots,n\}$$. Its bond lattice, $BL(G)$, is a sublattice of the set partition lattice. The elements of $BL(G)$ are the set partitions whose blocks induce connected subgraphs of $$G$$. In this article, we consider graphs $$G$$ whose bond lattice consists only of noncrossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley's map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions.