Demostrando una gráfica tiene una propiedad si todos finito subdiagramas tienen esa propiedad

Question

Dado un grafo $G=(V,E)$ y un entero $k\in\mathbb N$, vamos a decir que $G$ $k$si es que:

para cada división $V=\bigcup_{i\in I} U_i$ tal que $i\not=j \Rightarrow U_i\cap U_j =\emptyset$$|U_i|\geq k$, para cada una de las $i\in I$ podemos optar $v_i\in U_i$ tal que $i\not=j \Rightarrow \{v_i ,v_j\} \notin E$.

Probar que si cada finito subgrafo de $G$ $k$- bien, a continuación, $G$ $k$- bien.

---

Traté de manejarlo de la misma manera que Erdős-Teorema de de Bruijn (si cada finito gráfico puede ser coloreado con 4 números de tal manera que... luego cada gráfico puede ser de color de 4 números (...) fue probado (la prueba de que estoy hablando, es la que utiliza el teorema de compacidad para el cálculo proposicional) sin embargo, no podía encontrar una manera de traducir a la proposición atómica y describir los conjuntos de proposiciones.

Answer 1

Aquí hay otra manera de demostrarlo, esta vez usando el cálculo proposicional. Como antes voy a mostrar el resultado de las particiones en el finita de conjuntos y generalizar como el anterior. Sólo voy a dar la prueba de boceto, pero debe ser sencillo para completar los detalles.

Deje $U_i$ ser una partición de $V$ a finito de conjuntos de conjuntos tales que a $|U_i|\geq k$ por cada $i\in I$. Ahora definir los siguientes proposicional, teoría de la. Crear un conjunto de etiquetas de la siguiente manera: $V\cup X$ donde $X$ es un conjunto de etiquetas de $\{v_i \mid i\in I\}$ elige de modo que $V\cap X=\emptyset$.

Para cada $v_i\in X$, $u\in V$ hay una letra proposicional $P_{v_i=u}$. Y para cada una de las $u,v \in V\cup X$ otra letra proposicional $Q_{u,v}$ significado "$u$ $v$ están conectados por una arista" (en teoría tendríamos que elegir una notación que no distingue $Q_{u,v}$$Q_{v,u}$). Aquí está una proposicional, teoría de la:

• $\bigvee_{u\in U_i} P_{v_i=u}$ por cada $i \in I$.
• $P_{v_i=u}\rightarrow \neg P_{v_i=v}$ siempre $u\not=v$ $u,v\in V$
• $Q_{v, u}$ si $\{v,u\}\in E$.
• $\neg Q_{v, u}$ si $\{v,u\}\not\in E$.
• $P_{v_i=u}\rightarrow (Q_{u, w}\leftrightarrow Q_{v_i,u})$ para cualquier $u\in V$, $v_i\in X$ y $w\in V\cup X$.
• $Q_{u,v}\leftrightarrow Q_{v,u}$
• $\neg Q_{v_i,v_j}$ al $i\not=j$

Por la construcción de cada subconjunto finito es consistente, por lo que hay una verdad de la función, $t$, lo que satisface el conjunto de la teoría. A continuación, simplemente definen $f(U_i) = u$ si $t(P_{v_i=u})=1$.

Answer 2

Tenga en cuenta que basta probar que cada partición de $V$ en conjuntos finitos, $U_i$, $|U_i|\geq k$ usted puede elegir $v_i$ como se describe. El resultado sería, a continuación, mantenga arbitrarias de particiones: si $U_i$ $i\in I$ es una partición tal que $|U_i|\geq k$ todos los $i$, elija cualquier subpartition finito de conjuntos, $W_i$ indexados por $J$ tal que $|W_i|\geq k$ por cada $i\in J$, y encontrar el requisito de $v_i$ por cada $W_i$. Por elección, para cada una de las $U_j$ podemos elegir un único $W_i$ que es un subconjunto de a $U_j$, y deje $U_j$s representante de los ser $W_i$s representante, $v_i$.

Así, supongamos que el $U_i$, indexado por $i$, es una partición de finito de conjuntos tales que a $|U_i|\geq k$. Para cada finito $X\subseteq I$ deje $f_X$ ser una función donde $f_X(U_i) \in U_i$ por cada $i\in X$ tal que $\{f_X(U_i), f_X(U_j)\}\not\in E$ siempre $i\not=j$. Dicha función existe desde el $\langle\bigcup_{i\in X} U_i, E\cap \bigcup_{i\in X} U_i\rangle$ es finita subgrafo y así es $k$-bien.

Deje $F$ ser un ultrafilter que contiene cada conjunto $F_X=\{Y \subseteq I| X\subseteq Y$ $Y$ finito$\}$ por cada finito $X\subseteq I$.

Definir finalmente, $f(U_i)=x$ fib $\{X|f_X(U_i)=x\}\in F$. (Esto está bien definida, de lo contrario, el complemento de a $\{X|f_X(U_i)=x\}$, para cada una de a lo más un número finito de diferentes $x$, pertenecen a $F$. Desde $F$ es un ultrafilter la intersección de estos componentes pertenecen a $F$, ya que existen en la mayoría de un número finito de cosas que se cruzaba. Pero la intersección es vacía y por lo tanto no puede ser un miembro de $F$.)

Supongamos que $i\not= j$$f(U_i)=x$$f(U_j)=y$. Esto significa que $\{X|f_X(U_i)=x\}$, $\{X|f_X(U_j)=y\}\in F$ y por lo tanto su intersección, $\{X|f_X(U_i)=x, f_X(U_j)=y\}$ $F$ y por lo tanto es no vacío. Por lo que se deduce que para algunos $X$, $f_X(U_i)=x, f_X(U_j)=y$, y por la forma en que elegimos cada una de las $f_X$,$\{x,y\}\not\in E$.