Featured News

Moon Duchin and Dylan Thurston (erstwhile KAP and UCD faculty child respectively) brought the following question arising from gerrymandering:

Identify the subset $P_n$ of the simplex $\Delta$ in $\mathbb{R}^{n!}$ (viewed as all probability measures on permutations) obtained by fixing $n$ (typically different) probability measures on $\mathbb{R}$, sampling one point from each and recording the resulting permutation.

For example the midpoint or corners of $\Delta$ result if the measures are equal or each have distinct one point support respectively.

On the other hand $P_n$ is not all of $\Delta$. In particular a global quadratic inequality follows from the correlation between the conditions $a<b$ and $a<c$. Already for $n=3$ if $[abc]$ is the probability that $a<b<c$ then $[abc][cba]\leq([acb]+[cab])([bac]+[bca])$ so for instance the midpoint of the edge in $\Delta$ between $[abc]$ and $[cba]$ is not in $P_3$. Many such global quadratics have been written down by Fontain, Kasteleyn and Ginibre.

This ostensibly measure related problem becomes algebra upon noting that it suffices to consider measures of finite support and that for each fixed collection $\sigma=(\sigma_i)|_{i\in[n]}$ of disjoint finite support sets the associated region $P_\sigma\subseteq P_n$ is the image of the positive real points of a rational variety in $\mathbb{P}^{n!-1}$. For example with $n=3$ and $\sigma=(\{1,5\},\{2,4\},\{3\})$ there is a square of possible measures with these supports indexed by the probability $x$ for $1$ (rather than $5$) in the first measure and $y$ for $2$ in the second. The image $P_\sigma$ of this square in $\Delta$ is the ruled surface given by $[bac]=[cab]=0$ and $[abc][cab]=[acb][bca]$ and is the positive part of the Segre embedding of $\mathbb{P}^1\times\mathbb{P}^1$ into $\mathbb{P}^3$. More commonly the initial product of projective spaces will require some resolution away from the positive part before the rational map becomes algebraic.

A second connection to algebra is that when viewing $\sigma$ as a sequence of numbers from $[n]$ so that the example above becomes $abcba$ a braid move such as to $acbca$ does not change $P_\sigma$ though it does change the associated coordinatization. Thus it suffices to consider $\sigma$ indexed by elements of the $K_n$ Coxeter group. For $n=2$ this is affine type A and there are up to the action of $S_3$ only $\lceil\frac{k}{2}\rceil$ words of length $k$ required to get all of the sets $P_\sigma$ so for $k=5$ there are only $abcba$, $abcac$ and $abcab$.

Even for three measures there is more to the story. $P_3$ is full (five) dimensional in $\Delta$ and covered by the four $S_3$ orbits of $\{P_\sigma\}$ with $\sigma$ of length eight. The boundaries of these $P_\sigma$ besides the linear positivity requirements and the above FKG quadratics are defined by two other $S_3$ orbits of divisors (of degrees three and four) which we only found by computer and which do not give global inequalities for $P_3$. The analogs for higher $n$ remain quite mysterious.

The case of three measures is also essentially Efron's nontransitive or ro-cham-bo dice problem: Find three weighted dice (rock, paper and scissors) with various face values (these are the three measures) for which the probabilities that paper beats rock, scissors beats paper and rock beats scissors are all more than half. For example if you ask that all three of these probabilities agree and be as large as possible this will be a boundary point of $P_3$ along a diagonal line and contained in $P_{abcabca}$ which is a four dimensional divisor satisfying the quartic. (Since there are only two b's and c's the paper and scissors dice can be replaced with coins.)