Combinando pedidos por acuerdo

Question

No es un conjunto fijo $K$ con $k\geq 2$elementos. Una relación $\geq$ a $K$ se llama una débil pedido si es transitiva y completa (para cada una de las $x,y\in K$, $x\geq y$ o $y\geq x$ o ambos).

Hay un conjunto $N$ de $n\geq 2$ débil órdenes en $K$, y un número de $m \leq n$. Nos gustaría crear una nueva débil de pedidos $\succsim$ a $K$ con el siguiente acuerdo propiedad:

$x\succsim y$ sólo si al menos $m$ ordenamientos en $N$ de acuerdo en que $x \geq y$.

Para qué valores de a$m$ (en función de la $n,k$) es posible la creación de esta $\succsim$?

• Cuando $m=n$ esto puede ser imposible, incluso para $k=2$. Como un ejemplo, suponga $K = \{x,y\}$, y el conjunto de $N$ contiene $n=2$ débil órdenes: uno con $x\geq y$ y un con $y\geq x$. Luego, con $m=2$, el acuerdo de propiedad implica que ni $x\succsim y$ ni $y\succsim x$ - , pero, a continuación, $\succsim$ no es una relación completa.
• Cuando $m \leq n/2$, esto es posible por $k=2$. Supongamos $K = \{x,y\}$. Ya que cada pedido en $N$ es completa, que contiene al menos el $n/2$ relaciones para que $x\geq y$, o, al menos, $n/2$ relaciones para que $y\geq x$ (o ambos). En el primer caso, establezca $x\succsim y$, en el último caso, el conjunto de $y\succsim x$. La resultante de la relación es débil ordenar y cumple con el contrato de la propiedad.
• En general, cuando se $m \leq n/k!$, esto es posible, ya que por el principio del palomar, existe un orden de los elementos contenidos en, al menos, $n/k!$ relaciones $N$, así que podemos hacer $\succsim$ igual a esta relación.

Es posible que $m > n/k!$? ¿Cuál es el mayor $m$ (como una función de la $n$ e $k$) para los que esto es posible?

EDIT: creo que es posible siempre que $m \leq n/k$. La construcción de la nueva relación de la siguiente manera.

1. Si $x\geq y$ más de $n (k-1)/k$ ordenamientos en $N$, a continuación, establezca $x\succsim y$.

2. Añadir a $\succsim$, todas las relaciones que se derivan de las relaciones existentes por transitividad.

Las relaciones añadieron en 1 obviamente satifsy el acuerdo de requerimiento. Tenemos que demostrar que el mismo es cierto para las relaciones añadieron en 2. En efecto, supongamos que tenemos una cadena de $l-1$ relaciones, es decir, $x_1 \succsim x_2 \succsim \cdots \succsim x_l$, donde cada uno de estos $\succsim$ relaciones se agregó en el paso 1. Así que cada relación es acordado por más de $(k-1)n/k$ base de las relaciones. Para cada relación está en desacuerdo por menos de $n/k$ base de las relaciones. Así, en la mayoría de las $(l-1)n/k$ base de relaciones de acuerdo a al menos uno de los $\succsim$ relación. Así que, por lo menos, $(k-l+1)n/k$ base de relaciones de acuerdo a todas las $\succsim$ relaciones. Ya que cada base de la relación es transitiva, al menos $(k-l+1)n/k$ base de relaciones de acuerdo en que $x_1\geq x_l$. Ya existen en la mayoría de las $k$ elementos, $l\geq k$. Por lo tanto, al menos $n/k$ base de relaciones de acuerdo en que $x_1\geq x_l$, por lo que el acuerdo de requerimiento es satisfecho.

PREGUNTA: ¿es posible cuando se $m > n/k$?

Answer 1

No es una respuesta completa, pero si $n=k$ e $m>1$, entonces no es siempre posible.

Prueba: Supongamos que $K=\{1,...,k\}$. A continuación, para $N$ tomar la orden definido por las permutaciones $$k(k-1)...21\\1k(k-1)...32\\...\\(k-1)(k-2)...21k$$ Asumir, por el contrario, que tenemos suficiente $\succsim$.

Si $i\succsim i+1$ para algunos $i,i+1\in K$, entonces esto sólo está de acuerdo con la permutación $$i(i-1)...21k(k-1)...(i+2)(i+1)$$ Desde $m>1$, esto no es suficiente, lo cual es una contradicción. De ello se desprende que $i+1\succsim i$ tiene para todos los $i,i+1\in K$. Por transitividad $k\succsim 1$. Esto sólo está de acuerdo con la permutación $$k(k-1)...21$$ Desde $m>1$, esto no es suficiente, que es de nuevo una contradicción. Llegamos a la conclusión de que no hay suficiente $\succsim$.