Involución que trae conjuntos a conjuntos disjuntos

Question

Deje $A$ ser una colección de subconjuntos de a $\{1,2,\dots,n\}$ que es cerrado bajo tomando subconjuntos (es decir, si $U\in A$$V\subseteq U$$V\in A$). Hay siempre una involución $f:A\to A$ tal que $f(V)\cap V=\emptyset$ todos los $V\in A$? Supongo que sí.

Tenga en cuenta que si $A=\mathcal P(\{1,2,\dots,n\})$, luego de tomar el complemento funciona. También tenga en cuenta que si $|A|$ es impar, podemos enviar el conjunto vacío a sí mismo (el conjunto vacío es distinto de sí mismo, ¿no es eso extraño?).

He intentado trabajar a través de unos pequeños ejemplos. No he encontrado un contraejemplo, pero también no he encontrado una prueba.

Answer 1

He aquí una prueba de que se da un algoritmo para la construcción de una involución. Si el orden ideal $\mathcal{A}=\emptyset$ estamos hecho; de lo contrario, se puede seleccionar un elemento maximal $X$ $\mathcal{A}$ (con respecto a la inclusión.) Si realmente estamos de suerte, hay otro elemento maximal $Y$ $\mathcal{A}$ disjunta de a $X$. Si es así, podemos establecer $X\leftrightarrow Y$; desde $\mathcal{A}'=\mathcal{A}\setminus\{X,Y\}$ es de un orden ideal, podemos encontrar una adecuada involución en $\mathcal{A}'$ por inducción en $|\mathcal{A}|$, así que hemos terminado.

En general, no vamos a ser tan afortunados, pero la intuición es la misma. Dado un elemento maximal $X$$\mathcal{A}$, seleccione un elemento maximal $Y$ en $\{ Y\in \mathcal{A}\mid Y\cap X=\emptyset \}.$ Podemos par $X$$Y$, pero en general $Y$ no es máxima en $\mathcal{A}$, por lo que tenemos que hacer un poco más de trabajo antes de que podamos apelar a la inducción. Por la elección de $Y$, cada conjunto en $\mathcal{A}$ contiene $Y$ tiene la forma $Y\cup B$ algunos $B\subset X$. Vamos $$\mathcal{B} =\{B\subset X\mid Y\cup B\in\mathcal{A}\};$$ tenga en cuenta que $\mathcal{B}$ es cerrado bajo tomando subconjuntos desde $\mathcal{A}$ es.

Para cada una de las $B\in\mathcal{B}$, nosotros par $Y\cup B$ $X\setminus B$ (que, como sabemos, es en $\mathcal{A}$ desde $\mathcal{A}$ es de un orden ideal.) En resumen, esto coincide con los elementos de $Y\cup\mathcal{B}$ con los elementos de la $X\setminus\mathcal{B}$. Vamos $\mathcal{A}'$ ser el resultado de la eliminación de todos estos pares de elementos de $\mathcal{A}$. Una vez que comprobamos $\mathcal{A}'$ es de un orden ideal, hemos terminado por inducción.

Todo lo que tenemos que comprobar es que el conjunto de elementos que hemos eliminado, es una orden coideal de $\mathcal{A}$. (es decir, si quitamos $Z$, e $W\supset Z$$\mathcal{A}$, entonces también le quitan $W$). Pero $Y\cup \mathcal{B}$ es un coideal por la construcción; $X\setminus\mathcal{B}$ es uno desde $\mathcal{B}$ es de un orden ideal, y la unión de fin de coideals es un coideal. Por lo $\mathcal{A}'$ es de un orden ideal, y está hecho por inducción. $\square$

Nota: si $\mathcal{A}$ es el juego de poder de $X$, $X$ es el único elemento maximal de a $\mathcal{A}$; el algoritmo escoge $Y=\emptyset$, y los pares de cada una de las $B$ con el complemento de $X\setminus B$, por lo que este se generaliza el caso especial señaló en el post original. También se generaliza el caso especial en el inicio del post: si $Y$ es máxima en $\mathcal{A}$ $\mathcal{B}=\emptyset.$

Answer 2

No sé la respuesta, pero me gustaría reformular la pregunta en el lenguaje de la teoría de grafos. Dado un conjunto finito $X$, el powerset $\mathcal{P}(X)$ se convierte en el vértice de un grafo, al declarar que dos subconjuntos de a $X$ tienen un borde entre ellos iff son disjuntas. Además, el gráfico de $\mathcal{P}(X)$ tiene una perfecta coincidencia, dado por complementación. Su pregunta es si es cierto que para cada descendente-cerrado subconjunto $\mathcal{A}$ de la poset $\mathcal{P}(X)$, el gráfico inducida en $\mathcal{A}$ tiene un perfecto maridaje.

A la luz de esto, tal vez Tutte del teorema de ayuda.

Answer 3

Para cualquier $A$ a empezar con el más pequeño powerset que incluye $A$ (por ejemplo, si $A=\{\emptyset,\{1\},\{2\}\}$ inicio con $\mathcal P(\{1,2\})$). El uso de la trivial involución usted sugiere para este juego de poder. Luego transformar esta involución a una nueva involución, eliminando los elementos uno por uno para llegar a $A$ (empezar con más elementos). En ello, la alternativa entre la reasignación $\emptyset$ a sí mismo y el elemento que se asigna al elemento eliminado. De esta manera usted puede construir una involución para cualquier $A$. Usted necesita demostrar que las condiciones requeridas se conservan bajo estas transformaciones. Tenga en cuenta que cada transformación que se aplica en la anterior transformado la involución.