Número mínimo de bordes monocromáticos en un gráfico de Kneser "debajo del color"

Question

Definir el $n,k$ Kneser Gráfico de $KN(n,k)$ como sigue: $V=\binom{[n]}{k}$ e $ E=\{ (a,b) |a,b\in V, a\cap b = \emptyset\} $. En otras palabras, los vértices son las $k$-conjuntos de un $n$-elemento tierra set y nos conecte ellos si son disjuntas.

El Kneser–Lovász Teorema mostró que $\chi(KN(n,k))=n-2k+2$.

Ahora defina $\mu(n,k)$ a ser el número mínimo de monocromático de los bordes en la $KN(n,k)$ color con $n-2k+1$ colores (por lo que uno menos color).

Ya he demostrado que $\mu(n,k)\leq\binom{2k-1}{k}$. Esencialmente, he creado $n-2k+2$ distintos conjuntos independientes donde la primera $n-2k+1$ de ellos tenía el mismo elemento más pequeño y el último conjunto sólo tenía todo el resto. Entonces, he combinado los dos últimos conjuntos independientes y demostró que la gráfica correspondiente tenido en la mayoría de las $\binom{2k-1}{k}$ monocromática bordes.

$\textbf{QUESTION:}$ Estoy luchando para mostrar la igualdad sostiene cuando (1) $k=2$ y (2) $n=2k+1$.

Me moví un poco con él, pero yo no era capaz de encontrar alguna pista en donde la prueba sería.

Cualquier ayuda es muy apreciada.

\textbf{ACTUALIZACIÓN:}

He estado pensando acerca de (1) un poco y supongo que tiene que ver con la Erdos-Ko-Rado Teorema que establece que la familia más grande de $k$ elemento de subconjuntos de un $n$-conjunto tal que cada subconjunto es pares de intersección de ha $\binom{n-1}{k-1}$ conjuntos.

Esto significa que la mayor conjunto independiente en $KN(n,2)$ tiene el tamaño de $\binom{n-1}{2-1}=n-1$.

Para agregar un hecho útil, cada vértice es adyacente a el número de conjuntos es disjunta de, por lo $\binom{n-2}{2}$ conjuntos.

Answer 1

Esto es duro, pero aquí es lo que tengo:

Recordemos que el Schrijver Gráfico de $SG(n,k)$ se define de manera similar a la Kneser gráfico, pero no $k$-conjunto puede contener tanto $i$ e $i+1$ (o 1 y $n$, para el caso). También tenemos que $\chi(SG(n,k)=n-2k+2$.

(1) $k=2$ significa que tenemos que mostrar que $\mu(n,2)=3$. Esta es sólo la comprobación de los casos, pero, esencialmente, usted necesita mostrar que si se va a eliminar sólo dos bordes, el gráfico aún no pueden ser adecuadamente de color con sólo $n-2k+1$ colores. Entonces lo que puedes hacer es demostrar que no importa lo que los dos bordes de eliminar (se puede arreglar $\{12,34\}$ WLOG), entonces siempre habrá alguna instancia de $SG(n,2)$ en el gráfico. Para hacer esto, usted necesita encontrar una manera de indexar el $k$-conjuntos tales que los bordes se mantienen, pero los bordes se elimina involucrado un vértice que había consecutivos elementos en ella.

(2) $n=2k+1$ medios con la necesidad de mostrar $\mu(2k+1,k)=\binom{2k-1}{k}$. Por otra parte, acabamos de demostrar que para ser capaz de 2-color de la gráfica, $\binom{2k-1}{k}$ bordes, debe ser eliminado. Para hacer esto, usted puede contar con el total de número de $SG(2k+1,k)$'s son en el $KN(2k+1,k)$ y luego contar el número que utiliza un fijo arbitrario borde. Para hacer esto, usted necesita para contar el número de maneras únicas, hasta rotación y reflexión, puede reorganizar el orden de los elementos para la ex y se puede volver a contar el número de maneras en que usted puede volver a clasificar los elementos de cada uno de los vértices consecutivos tales que los elementos no se producen para el último. Usted debe obtener la $\frac{1}{2}(n-1)!$ e $k!k!$ respectivamente. Por lo tanto, mediante la eliminación de un borde, le quite $k!k!$ Schrijver gráficos. Por lo tanto, la división de las dos cantidades que debe proporcionar el número de aristas que usted necesita para eliminar antes de que todos los Schriver gráficos se han ido. Esto le da a usted $\frac{1}{2}\binom{2k}{k}=\binom{2k-1}{k-1}$.