Número de funciones de peso no equivalentes en un conjunto de $n$ elementos

Question

Para un conjunto finito $S$ de $n$ elementos, digamos que una función de peso es una función $f \colon S \to \mathbb{R}$ . Para cualquier subconjunto $T \subseteq S$ , defina $f(T) = \sum _{x \in T} f(x)$ . Definir dos funciones de peso $f_1, f_2$ en el mismo conjunto $S$ para ser equivalente si $f_1(T_1) \leq f_1(T_2) \Leftrightarrow f_2(T_1) \leq f_2(T_2)$ para todos los conjuntos $T_1, T_2 \subseteq S$ .

¿Cuántas funciones de peso no equivalentes hay en un conjunto de $n$ elementos, asintóticamente en función de $n$ ? Se deduce de un resultado de Frank y Tardos (Thm 3.3) que hay a lo sumo $2^{O(n^4)}$ funciones de peso distintas, pero me interesa saber cuál es el grado óptimo del polinomio en el exponente.

Answer 1

Usted pregunta por el número $T_n$ de funciones de umbral en el plató $\{-1,1\}^n$ . Según https://arxiv.org/pdf/1903.06595.pdf (Sección 1.2), Zuev demostró que $\log_2T_n\sim n^2$ .

Answer 2

Resulta que mi pregunta tiene respuesta en un reciente artículo de Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin y Shmuel Onn sobre la complejidad de la programación entera. Dejando que $w \in \mathbb{R}^n$ sea el vector de pesos, el peso de un subconjunto $S' \subseteq S$ se puede escribir dejando que $x_{S'}$ sea el $0/1$ -vector característico de $S'$ para que el peso de $S'$ se convierte en el producto interior $w \cdot x_{S'}$ .

El teorema 65 del artículo citado muestra que para cualquier función lineal $f(x) = w \cdot x$ para $x \in \{0,1\}^n$ existe una función de peso equivalente $g(x) = w' \cdot x$ tal que $w' \in \{- n(12n)^n, \ldots, n(12n)^n\}$ es decir, cada peso es un número entero cuyo valor absoluto es $n \cdot n^{O(n)}$ . Por lo tanto, cada función de peso tiene una representación con cada uno de los $n$ pesos que pertenecen a este rango, dando un límite superior de como máximo $(1+2n \cdot n^{O(n)})^n = 2^{O(n^2 \log n)}$ funciones de peso no equivalentes.