0
$\begingroup$

This is a follow-up question to an older one.

Let $\mathbb{N}$ denote the set of the positive integers and let $n\in\mathbb{N}$. If $w:\{1,\ldots,n\}\to \mathbb{N}$ is a function (the letter $w$ stands for "weight function") and $S\subseteq \{1,\ldots,n\}$ we say that the score of $S$ with respect to $w$ is $$\text{sc}_w(S) = \sum_{k\in S}w(k).$$ We say that a family ${\cal A}$ of subsets of $\{1,\ldots,n\}$ is freely rankable if for any bijective map $\varphi:\{1,\ldots,|{\cal A}|\}\to{\cal A}$, it is possible to find a weight function $w:\{1,\ldots,n\}\to \mathbb{N}$ such that for all $k\in\{1,\ldots,|{\cal A}|-1\}$ we have $$\text{sc}_w(\varphi(k)) > \text{sc}_w(\varphi(k+1)).$$ (Clearly, any freely rankable family has the property that no member is a subset of another member of the family.)

Question. In terms of $n$, what is the maximum size of a freely rankable family ${\cal A}$ on $\{1,\ldots,n\}$?

$\endgroup$
  • 1
    $\begingroup$ Pretty small, actually. Any $n+2$ points in $\mathbb R^n$ are affine dependent, so no chance to separate them in some way by a linear functional. $n+1$ would be possible if you had allowed negative weights (the empty set and all one-element sets) but since your weights are required to be positive, I wouldn't be surprised if the answer is actually $n$ (though I wouldn't bet on it either) $\endgroup$ – fedja Jun 5 '18 at 18:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.