Conde Kneserovsky

Un gráfico de Kneser es un gráfico no dirigido que describe la relación entre los subconjuntos de elementos - que no se intersecan de un conjunto de elementos -. ${\ Displaystyle KG_ {n, k}}$ $k$ $norte$

Formal definición

deja _ Entonces el gráfico de Kneser se define como un par de conjuntos de vértices y aristas $R_{n}=\{1,2,\cdots,n\}$ $KG_{n,k}=(V,E)$ $V=\{S\mid S\subconjunto R_{n},|S|=k\}$ ${\displaystyle E=\{(A,B)\mid A\in V,B\in V,A\cap B=\varnada\))$

Casos especiales

Para , un gráfico de Kneser es un gráfico vacío (sin bordes). $k>{\frac{n}{2))$

Para , la gráfica de Kneser es una coincidencia. Por supuesto, sólo se considera el caso. $k={\frac{n}{2}}$ $n\equiv 0{\pmod {2}}$

Cuando una gráfica de Kneser es una gráfica completa . $k=1$

El conde es el conde de Petersen . $KG_{{5,2}}$

De principal interés son los gráficos de Kneser con valores de parámetros en el intervalo . $k$ ${\ estilo de visualización [2; {\ frac {n} {2}}}}$

Número cromático

El gráfico de Kneser, entre otras cosas, se puede utilizar para ilustrar un caso especial de la impracticabilidad de las estimaciones triviales del número cromático de un gráfico en términos del número de camarilla y el número de independencia.

Estimaciones triviales generales

El número de independencia es el tamaño del conjunto de vértices más independientes en un gráfico . La definición de coloreado significa que define el número máximo de vértices que se pueden colorear con el mismo color. Basado en alguna modificación del principio de Dirichlet , el número cromático de un gráfico se puede estimar como ${\ estilo de visualización \ alfa (G)}$ $GRAMO$ ${\ estilo de visualización \ alfa (G)}$ $\chi (G)\geq {\frac {|V|}{\alpha (G)))$

De manera similar, el número de clics se define como el tamaño de la camarilla máxima. Este número evalúa ${\ estilo de visualización \ omega (G)}$ ${\ estilo de visualización \ chi (G) \ geq \ omega (G)}$

Como regla general, la primera estimación es mejor que la segunda, es decir, para un gráfico aleatorio en los vértices, la probabilidad que tiende a la unidad al aumentar . Del hecho de que cada camarilla del gráfico se puede asociar con un conjunto independiente del gráfico , podemos concluir que lo mismo es cierto para . $GRAMO$ $norte$ ${\ estilo de visualización \ alfa (G) <2 \ log _ {2} {n}}$ $norte$ $GRAMO$ ${\ estilo de visualización \ no G}$ ${\ estilo de visualización \ omega (G)}$

Sin embargo, el gráfico de Kneser proporciona una ilustración clara de toda una clase de gráficos que desacreditan las estimaciones anteriores (en el caso general, no para los gráficos aleatorios).

Haga clic en el número

Sin pérdida de generalidad, suponemos que entra en la camarilla como vértice. Entonces, a partir de la definición de clique, ningún otro vértice debe contener en su subconjunto ningún elemento de . Tras un análisis similar adicional, esto obviamente da ${\ estilo de visualización \ {1, \ puntos, k \}}$ ${\ estilo de visualización \ {1, \ puntos, k \}}$ $\omega (KG_{n,k})=\left\lfloor {\frac {n}{k))\right\rfloor$

Número de Independencia

Es obvio por consideraciones combinatorias que . Para construir un conjunto independiente de este tamaño, basta con fijar un vértice y enumerar todos los subconjuntos de elementos que lo contienen. Por definición, no habrá borde entre ningún par de tales conjuntos. $\alpha (KG_{n,k})\geq {\binom {n-1}{k-1))$ $k$

Erdős , Co y Rado publicaron en 1961 una prueba de un teorema que afirmaba la igualdad en la estimación anterior. Según los matemáticos, encontraron una prueba varias décadas antes, pero en ese momento no tenía sentido publicarla, porque a nadie le interesaba el teorema. Por cierto, el gráfico de Kneser aún no se conocía en ese momento, por lo que Erdős, Co y Rado demostraron el teorema en la formulación elemental del número máximo de subconjuntos de elementos de elementos que se cruzan por pares. $k$ $norte$

Usando una estimación trivial, solo , es decir, se puede obtener del valor dado del número de independencia . Esta estimación es casi la misma que la estimación a través del número de clic. $\chi (KG_{n,k})\geq {\frac {\binom {n}{k}}{\binom {n-1}{k-1}}}={\frac {n} {k}}$ $\chi (KG_{n,k})\geq \left\lceil {\frac {n}{k))\right\rceil$

Significado exacto

Formulado en 1955 por Martin Kneser y demostrado en 1977 por Laszlo Lovas , el teorema establece que ${\ estilo de visualización \ chi (KG_ {n, k}) = n-2k + 2}$

Construcción de una coloración óptima

Para cualquier , coloreemos en el -ésimo color cada subconjunto cuyo elemento mínimo sea el número . Coloreemos cada subconjunto contenido en el conjunto . Dado que hay un elemento en el conjunto especificado, dos de sus subconjuntos de elementos se cruzan, es decir, no hay borde entre los vértices correspondientes. Por lo tanto, la coloración construida es correcta. $j=1,2,\ldots,n-2k+1$ $j$ $j$ ${\ estilo de visualización n-2k+2}$ ${\displaystyle \{n-2k+2,n-2k+3,\ldots,n\))$ ${\ estilo de visualización 2k-1}$ $k$

Véase también

Fuentes

Popular revista científica física y matemática "Kvant", 2011, "La hipótesis de Kneser y el método topológico en combinatoria" (A. Raigorodsky)