Dominación "circular" en${\mathbb R}^4$

Question

El siguiente problema es el relacionado con (y motivado por) el primer caso abierto de este MO pregunta. Es difícil creer que este es un problema difícil; y, sin embargo, no tengo una solución.

Para dos vectores $x,y\in {\mathbb R}^4$, digamos que $x$ está dominado por $y$ si hay (al menos) dos coordenadas en que $x$ es estrictamente menor que $y$. Con este convenio, el problema es el siguiente:

¿Existe un finito, no-vacío $S\subset {\mathbb R}^4$ con la propiedad de que para cualquier par de vectores $x,y\in S$, existe otro vector de $z\in S$ de manera tal que las coordenadas de sabios máximo de $x$ e $y$ está dominado por $z$?

Aviso de que es fácil encontrar un conjunto de vectores con la propiedad en cuestión en ${\mathbb R}^5$ (ver comentarios más abajo), o para encontrar un finito, no-vacío conjunto de vectores en ${\mathbb R}^4$ de manera tal que cualquier vector es dominado por otro. Por otro lado, no es finito, no-vacío en ${\mathbb R}^4$ en que para cualquier par de vectores hay una tercera superior al de su máximo en al menos tres coordenadas.

---

Post-factum: asegúrese de que no has perdido la extremadamente inteligente solución por zeb! No es fácil de seguir, pero he hecho un esfuerzo para rastrear cuidadosamente y, hasta donde yo puedo ver, es perfectamente correcto. Ya el primer paso es muy inusual: en lugar de buscar en la más pequeña contraejemplo, zeb considera un contraejemplo que no es menor, sino que tiene una estructura comprensible. Si han votado por el problema en sí o no, considere la posibilidad de votar por zeb la solución!

Answer 1

No existe tal conjunto de $S$. Supongamos por contradicción que existe. Por el reescalado de las coordenadas, podemos asumir que todos los coeficientes de puntos en $S$ son enteros positivos. Ahora, la construcción de un conjunto $S'$ como sigue: para cada punto de $(a,b,c,d)\in S$, poner puntos de $(a,b,0,0), (a,0,c,0), (a,0,0,d), (0,b,c,0), (0,b,0,d), (0,0,c,d)$ en $S'$. $S'$ será entonces una solución para el problema de si $S$ era, por lo tanto, reemplace $S$ por $S'$.

Mediante la adición de un número finito de puntos adicionales a $S$, que además puede suponer que si se disminuye un coeficiente de un punto en $S$ por $1$, entonces el punto resultante es todavía en $S$ mientras que el coeficiente fue mayor que $1$ a empezar. $S$ ahora tiene las siguientes propiedades:

La propiedad 0: Cada punto en $S$ tiene exactamente dos coeficientes positivos, y el máximo de $M$ tal que $(M,1,0,0)\in S$ es el mismo que el de la máxima $M'$ tal que $(M',0,1,0)\in S$.

Propiedad 1: Si $(a,b,0,0)\in S$ e $(0,0,c,d)\in S$, entonces al menos uno de $(a+1,0,c+1,0), (a+1,0,0,d+1), (0,b+1,c+1,0), (0,b+1,0,d+1)$ es de $S$.

Prueba: Vamos a $A$ ser máxima tal que $(A,b,0,0)\in S$ y deje $D$ ser máxima tal que $(0,0,c,D)\in S$. Algún elemento de $S$ domina $(A,b,c,D)$, y por la elección de $A$ (respectivamente $D$) no puede tener sus dos últimas (respectivamente dos primeros coeficientes de la igualdad de a $0$.

Propiedad 2: Si $(x,y,0,0)\in S$, entonces al menos uno de $(x+1,0,0,2), (0,y+1,0,2)$ es de $S$.

Prueba: Vamos a $X$ ser máxima tal que $(X,y,0,0)\in S$, y deje $M$ ser máxima tal que $(0,0,M,1)\in S$. A continuación, algunas elemento $(a,b,c,d)$ de % de $S$ domina $(X,y,M,1)$. Por la Propiedad 0 tenemos $c\le M$, lo $c = 0$. Ya que no podemos tener $(X+1,y+1,0,0)\in S$, $d$ no debe ser $0$, lo $d \ge 2$ y, o bien $a \ge X+1 \ge x+1$ o $b \ge y+1$.

Ahora considere la siguiente propiedad, dependiendo de un parámetro de $k$:

La propiedad $k$: Si $(x,y,0,0)\in S$, entonces al menos uno de $(x+1,0,0,k), (0,y+1,0,k)$ es de $S$.

Si $S$ tiene la Propiedad $k$ para cada entero $k$, entonces claramente $S$ debe ser infinito. Ahora vamos a probar que, de hecho, la Propiedad $k$ implica que la Propiedad $k+1$ para $k \ge 2$, y esto le dará a nuestra deseada de la contradicción.

La propiedad $k$ implica que la Propiedad $k+1$: Elija $A,B,C$ maximal tal que $(A,0,0,k), (0,B,0,k), (0,0,C,k) \in S$. A ver que tal $A,B,C$ existe en absoluto, aplicamos la Propiedad $k$ hasta el punto de $(1,1,0,0)$ a ver que cualquiera de las $(2,0,0,k)$ o $(0,2,0,k)$ es de $S$, y, a continuación, aplicamos la Propiedad $0$ a ver que todos los de $(1,0,0,k), (0,1,0,k), (0,0,1,k)$ es $S$.

Ahora construimos una secuencia de puntos de $s_i \in S$, cada una con cuarta coordenada igual a cero, de la siguiente manera. Empezar con $s_0 = (x,y,0,0)$. Para cada una de las $i$, dividido en varios casos:

1. Si $s_i = (0,u,v,0)$, aplicar la Propiedad 1 a $(0,u,v,0)$ e $(A,0,0,k)$, y llamar a la resultante dominando punto de $s_{i+1}$. Si la cuarta coordenada de $s_{i+1}$ es distinto de cero, se detienen aquí.
2. Si $s_i = (u,0,v,0)$, aplicar la Propiedad 1 a $(u,0,v,0)$ e $(0,B,0,k)$. Proceder de forma similar a la anterior.
3. Si $s_i = (u,v,0,0)$, aplicar la Propiedad 1 a $(u,v,0,0)$ e $(0,0,C,k)$. Proceder de forma similar a la anterior.

El reclamo es que este proceso debe parar, y el final de la $s_{i+1}$ producida será el punto que estamos buscando. Para ver esto, la primera nota que nunca podemos terminar en el mismo caso dos veces en una fila durante este proceso. Además, nunca se puede pasar a través de los tres casos en el curso de este proceso: por ejemplo, si queremos que se inicie en el caso de que en el paso 3 $i-2$, a continuación, vaya a través de casos en el paso 2 $i-1$, y luego terminan en el caso 1 en el paso $i$, entonces si escribimos $s_i = (0,u,v,0)$ nos encontramos con que $u = B+1$ e $v = C+2$. Aplicación de la Propiedad $k$ a $s_i$, vemos que uno de $(0,B+2,0,k), (0,0,C+3,k)$ es de $S$, contradiciendo la elección de $A,B,C$.

Por lo tanto, el proceso se alterna entre el caso 3 y algún otro caso, dicen que el caso 2 para su concreción. En cada paso, la primera coordenada de $s_i$ aumentará, y de manera inductiva vemos que para $i\ge 0$, la primera coordenada de $s_i$ es $x+i$. Ya que no puede aumentar sin límite, el proceso debe terminar eventualmente. Si termina después del paso $0$, entonces el vector dominante $s_1$ es $(x+1,0,0,k+1)$ o $(0,y+1,0,k+1)$. Si termina después del paso $i$ para $i\ge 1$, entonces el vector dominante $s_{i+1}$ debe $(x+i+1,0,0,k+1)$, ya que de lo contrario serían $(0,B+2,0,k+1)$ o $(0,0,C+2,k+1)$ dependiendo de si $i$ era pares o impares, contradiciendo la elección de $A,B,C$.

Answer 2

Esto puede ser un comienzo. Suponiendo que existe un número finito de $S$, podemos aplicar el principio extremal en varias formas de restricciones.

Notación : Para distintos $x,y\in S$, vamos a denotar por $x\cup y$ el vector de sus coordenadas sabio maxima y se refieren a ella como un par. Más denotar $I := \lbrace 1,2,3,4\rbrace$.

Suponga que $S$ tiene un mínimo de tamaño. A continuación, cada una de las $x\in S$ es necesario para dominar algún par.

Dentro de cada coordenada $i$, etiqueta de la que ocurren las entradas de los más pequeños ($0$) a mayor (llamar a ese $m_i$). Podemos wlog reemplazar las entradas de todos los vectores de $S$ por estas etiquetas. Tenga en cuenta que cada número de $\lbrace 0,\dots,m_i\rbrace$ se produce como $i$th coordinar para algún vector en $S$.

Ahora trataremos de "comprimir" un par de coordenadas. Con esto quiero decir que tenemos que elegir un $i\in I$, y para cada una de las $x\in S$ tal que $x_i\ne0$, reemplace $x_i$ por $x_i-1$. Mientras el set modificada todavía se ajusta a la propiedad, se puede iterar este proceso y finalmente se llega a una contradicción, como todas las coordenadas va a terminar como $0$ en todas partes. Así que (como hemos supuesto la existencia de una inicial S), la propiedad debe ser violado en una de estas iteraciones, y así obtendrás con nosotros algunas limitaciones.

Comprimir la primera coordenada siempre y cuando las obras, luego de la 2da, 3ra, 4ta.

La propiedad será violado por primera coordinar iff hay $a^1,b^1\in S$ con $a^1_1=b^1_1=0$ de manera tal que cada vector $x\in S$ que domina $u^1:=a^1\cup b^1$ ha $x_1=1$. (Esto es porque si, siempre hay un $x$ con $x_1>1$ o $x_1=0$, la compresión no interferir con la propiedad). Que se indique lo contrario, cada una de las $x\in S$ con $x_1>1$ debe tener $x_i\le u^1_i$ para $i=2,3,4$. $(*)$. Lo mismo para las otras coordenadas.

Para cada una de las $i\in I$ tomar un vector $v^i\in S$ de manera tal que su $i$th coordinar $v^i_i=m_i$ es máxima. Es fácil ver que $v^1,\dots,v^4$ debe ser distintos, es decir, no hay vector de $S$ puede ser máxima en más de una coordenada. $(**)$

Supongamos $v^i_j>1$ una $j\ne i$. Entonces por $(*)$, debemos tener $m_i=v^i_i\le u^j_i$, lo $u^j_i=m_i$ debido a que este es máxima.

Cada una de las $a^j$ e $b^j$ sólo puede tener una coordenada máxima porque de $(**)$. Como $u^j=a^j\cup b^j$, para cada una de las $i$ hay al menos un $j\ne i$ tal que $v^i_j\le1$.

Así que sabemos que cada vector $v^i$ anterior (es decir, con un máximo de $i$th de coordenadas) debe tener otro coordinar $\le 1$.

No sé si esto será de gran ayuda para la realización de. También parece (pero mi prueba de que aún no está completa) que debe haber un (único?) $w\in S$ que domina todos los pares $v^i\cup v^j$, y a partir de ahí se podría ir bastante lejos hacia el tan ansiosamente buscado contradicción.

Answer 3

Esta es sólo poco más de un comentario.

Por $t \to -t$ la cuestión de la circular de la dominación, es equivalente a encontrar un conjunto donde la coordenada sabio mínimo de cada par $x,y$ domina $z$ en $S$ o $z <_2 \min(x,y)$.

Asumir que hay un número finito de $S=\{s_0,\ldots,s_n\} $ con un mínimo de número de $n+1$ de los elementos, de tal manera que cada juego con menos elementos, no tiene circular de la dominación. A continuación, para cada coordenada $i=1,\ldots,4$ es posible sustituir los números reales $S=\{s_{0,i},\ldots,s_{n,i}\} $
por los números naturales $\{0,1,\ldots,n\}$ mientras que conserva el orden. Si algunas coordenadas reales son iguales, uno puede elegir cualquier el fin de los correspondientes números naturales sin destruir la circular de la dominación. (por ejemplo, reemplace $(-0.3, -0.1, 0, 0, 0, 0.3, 1.5)$ con $(0,1,2,3,4,5,6)$ o $(0,1,4,2,3,5,6)$ )

Prueba: Por $u,v,w \in S$ con $u <_2 \min(v,w)$, a continuación, también por los renombrados conjunto tenemos $nat(u) <_2 \min(nat(v), nat(w))$.

Por lo tanto, si cualquier conjunto mínimo $S$ existe, uno puede encontrar un conjunto mínimo $S$ cuando la $i$-th coordenadas son permutaciones de $\{0,1,\ldots,n\}$. Esto muestra que el problema de decidir si la circular de la dominación es posible en un conjunto con $k$ elementos finitos problema. Por la fuerza bruta de la informática podía, al menos, muestran que la circular de la dominación requiere de $k>6$.

Esta formulación también ayuda a ver que en cada coordenada hay

$n$ pares que tienen un mínimo de 0,

$n-1$ con un mínimo de 1

y así sucesivamente. El valor esperado de cada coordenada mínima de dos elementos es $\frac{ n+2}{3}$. Esto corrobora la intuición de que no hay suficientes números pequeños, de tal manera que cada uno de los elementos está dominado por un mínimo de dos personas. Sin embargo, este debe ser el caso en un mínimo de circular conjunto (de lo contrario acaba de tirar los elementos que no lo son, y usted todavía tiene un conjunto circular). No podía transformar esto en una prueba, aunque.

Answer 4

Tome$S_N=\left \{x_n\right \}_{n=1}^N$ donde$x_n=(n,n,1/n,1/n)$. Entonces$$\max\left \{x_n,x_m \right \}=(\max\left \{n,m \right \},\max \left \{n,m \right \},1/\min\left \{n,m \right \},1/\min \left \{n,m \right \}).$$ If $ n <N$ and $ m <N$, then $ \ max \ left \ {x_n, x_m \ right \}$ is dominated by $ x_N$. If $ n> 1$ and $ m> 1$, then $ \ max \ left \ {x_n, x_m \ right \}$ is dominated by $ x_1$. Also $ \ max \ left \ {x_1, x_N \ right \}$ is dominated by $ x_n$ for any $ n \ neq1$ or $ N $.