Let $A=\{a_1,\ldots,a_m\}.$ Let a choice function $f:\mathcal{P}(A) \mapsto A,$ be such that, for all $B \in \mathcal{P}(A),$ $f(B)=x$ for some $x\in B.$ For instance, with $A=\{a_1,a_2,a_3\}$ one such function is $f(\{a_1,a_2,a_3\})=a_1, f(\{a_1,a_2\})=a_1, f(\{a_1,a_3\})=a_1, f(\{a_2,a_3\})=a_2.$ [$\mathcal{P}(A)$ is the set of all non-empty subsets of $A.$]

Let us restrict our attention to all $B\subseteq A$ of cardinality $r,$ i.e., $|B|=r.$ Let $x_i=|\{B|B \subseteq A, |B|=r, f(B)=a_i\}|.$ And suppose $x_{(1)},x_{(2)},\ldots, x_{(m)}$ are these frequencies in non-decreasing order. Let us call this vector $x^{m,r,f}=(x_{(m)},x_{(m-1)},\ldots, x_{(1)})$ and $x^{m,r}=\{x^{m,r,f}|f \text{ is a choice function }\}.$

Thus, $x^{3,2}=\{(2,1,0),(1,1,1)\},$ and $x^{4,2}=\{(3,2,1,0),(2,2,2,0),(2,2,1,1),(3,1,1,1)\}.$

My question is: Is there any general characterization of the vectors in $x^{m,r}?$ Or at least for $r=2?$ Some partial results will be also be very helpful.

Note: For $r=2,$ let $\Gamma=(E,A)$ be the directed graph where $A$ is the set of nodes. $(a_i,a_j)\in E \iff f(\{a_i,a_j\})=a_i.$ Therefore, $x_i$ can be interpreted as out-degree of the node $a_i.$


1 Answer 1


This shows up in the literature under the name score sequence. For the $r=2$ case you can find more information on MathWorld and on the page of A000571 in the OEIS.

For general values of $r$ a characterization is given in On Score Sequences of $k$-Hypertournaments by Zhou Guofei, Yao Tianxing, and Zhang Kemin. In the notation of the post we have that $(x_{(1)}, \dots, x_{(m)}) \in x^{m,r}$ if and only if $$ \sum_{i = 1}^j x_{(i)} \geq \binom{j}{r}$$ for all $j$ with equality when $j=m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.