4
$\begingroup$

For a finite set $S$ of $n$ elements, say a weight function is a function $f \colon S \to \mathbb{R}$. For any subset $T \subseteq S$, define $f(T) = \sum _{x \in T} f(x)$. Define two weight functions $f_1, f_2$ on the same set $S$ to be equivalent if $f_1(T_1) \leq f_1(T_2) \Leftrightarrow f_2(T_1) \leq f_2(T_2)$ for all sets $T_1, T_2 \subseteq S$.

How many non-equivalent weight functions are there on a set of $n$ elements, asymptotically as a function of $n$? It follows from a result of Frank and Tardos (Thm 3.3) that there are at most $2^{O(n^4)}$ distinct weight functions, but I am interested to know what the optimal degree is of the polynomial in the exponent.

$\endgroup$
2
  • $\begingroup$ There's an obvious lower bound of $n!$ since every ordering of the singleton sets is obviously achievable. $\endgroup$
    – Tony Huynh
    Nov 22, 2019 at 12:32
  • $\begingroup$ Are there any exact counts for small $n$? I see that if we restrict $|T_1|=|T_2|=2$, then we will get OEIS A231074 or alike. $\endgroup$ Dec 3, 2019 at 21:41

2 Answers 2

2
$\begingroup$

You are asking for the number $T_n$ of threshold functions on the set $\{-1,1\}^n$. According to https://arxiv.org/pdf/1903.06595.pdf (Section 1.2), Zuev showed that $\log_2T_n\sim n^2$.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the reference. While I agree that the number of non-equivalent weight functions is at least the number of threshold functions, I don't see the other direction of the equivalence. How would you map each weight function $f$ to a threshold function $g$, so that non-equivalent weight functions map to different threshold functions? The obvious way seems to be picking a threshold value $t$ and letting $g(S) = 1$ iff $w(S) \geq t$, but then functions which are non-equivalent for subsets of weight less than $t$, may get mapped to the same threshold function. $\endgroup$ Nov 22, 2019 at 15:31
2
$\begingroup$

It turns out my question is answered in a recent paper by Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, and Shmuel Onn on the complexity of integer programming. Letting $w \in \mathbb{R}^n$ be the vector of weights, the weight of a subset $S' \subseteq S$ can be written by letting $x_{S'}$ be the $0/1$-characteristic vector of $S'$, so that the weight of $S'$ becomes the inner product $w \cdot x_{S'}$.

Theorem 65 in the cited paper shows that for any linear function $f(x) = w \cdot x$ for $x \in \{0,1\}^n$, there is an equivalent weight function $g(x) = w' \cdot x$ such that $w' \in \{- n(12n)^n, \ldots, n(12n)^n\}$, that is, each weight is an integer whose absolute value is $n \cdot n^{O(n)}$. Hence each weight function has a representation with each of the $n$ weights belonging to this range, giving an upper-bound of at most $(1+2n \cdot n^{O(n)})^n = 2^{O(n^2 \log n)}$ nonequivalent weight functions.

$\endgroup$

Your Answer

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

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