The voter basis and the admissibility of tree characters (Q2665833): Difference between revisions

Given a total order on the power set of a finite set $[n]$, a subset $S$ of $[n]$ is separable when for any subsets $X$, $Y$ of $S$ and any subset $Z$ of $[n]-S$, the ordering of $X$ and $Y$ is the same as the ordering of $X'$ and $Y'$, where $X'$ (or $Y'$) is the union of $X$ (or $Y$) and $Z$. The character of a total order is the collection of all its separable subsets. A collection $\mathcal{H}$ of subsets of $[n]$ is admissible when there exists a total order on the power set of $[n]$ such that the character of this total order is $\mathcal{H}$. A tree collection is a collection of subsets of $[n]$ containing the empty set and $[n]$, and such that every pair of its members is either nested or disjoint. The main result of the paper states that every tree collection is admissible. The proof is constructive; a linear algebraic technique to construct total orders on $[n]$ is introduced.