El Kneser gráfico de $KG_{n,k}$ es el grafo cuyos vértices corresponden a la $k$-elemento de subconjuntos de un conjunto de $n$ elementos, y en el que dos vértices son adyacentes si y sólo si los dos conjuntos correspondientes son disjuntas. ¿Cuál es el número máximo de vértices en un completo bipartito subgrafo de $KG_{n,k}$?
En un completo bipartito subgrafo, tenemos dos conjuntos de $X,Y$ de vértices tales que todos los pares de subconjuntos correspondientes a los vértices de cada lado son no disjuntas, mientras que en cada vértice $X$, y en cada vértice $Y$ son disjuntas. Suponiendo que $n$ es incluso, podemos dividir el conjunto de $n$ elementos en dos subconjuntos $A,B$ $n/2$ elementos. Elegir como $X$ todos los vértices correspondientes a $k$-elemento de subconjuntos de a $A$ que contienen un elemento fijo $a\in A$, y del mismo modo para $B$. Este rendimientos $2\cdot\dbinom{n/2-1}{k-1}$ vértices en $A\cup B$.
Es esta la mejor posible?
Respuesta
¿Demasiados anuncios?
Supongamos que los conjuntos de $X$ corresponde a uno de los vértices de las particiones de tu gráfico bipartito y que la pone en $Y$ corresponden a los otros. Deben cumplirse las siguientes condiciones: $X$ es de intersección de la familia (cada $x_{i}\in X, x_{j}\in X$ satisfacer $x_{i}\cap x_{j}\neq \emptyset$, de modo que los vértices en $X$ no son adyacentes. Del mismo modo, en $Y$. También debe ser el caso de que cada $x\in X$ y cada una de las $y\in Y$ que $x\cap y=\emptyset$, de modo que hay un borde de$x$$y$.
Deje $A=\bigcup_{x\in X} x$$B=\bigcup_{y\in Y} y$. Tenga en cuenta que $A$ $B$ son disjuntas (de lo contrario no es un $x\in X$$y\in Y$$x\cap y\neq \emptyset$). Este hecho justifica inicialmente creación de particiones en la base de los elementos de dos conjuntos disjuntos. Deje $a=|A|$ $b=|B|$ señalando que $a+b=n$.
Tenga en cuenta que el conjunto de $X$ es de intersección de la familia de $k$, viniendo de un conjunto de base con $a$ elementos. El Erdos-Ko-Rado teorema (http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem) dice que la mayoría de las $k$-establece que puede estar contenida en $X$: $\binom{a-1}{k-1}$. Esto implica que
$$|X| \leq \binom{a-1}{k-1} \text{ and } |Y|\leq \binom{b-1}{k-1}.$$
Por lo tanto, la más grande bipartito gráfico que usted podría tener es:
$$\max \binom{a-1}{k-1} + \binom{n-a-1}{k-1}.$$
Debemos suponer que tanto $a$ $b$ al menos $k$--suponiendo que se espera que el bipartito completo gráfico para contener un borde--optimizar la partición. Algunas rápida experimentación con el código de python muestra que esta optimizado al $a=k$ (o $b=k$ por simetría). Por lo tanto, la mayoría de los vértices en los que se podría tener en una completa bipartito subgrafo de la Kneser gráfica es:
$$\binom{n-k-1}{k-1}+1.$$
La forma en que esto puede lograrse mediante el establecimiento de lado una sola $k$-elemento del subconjunto (para una partición, que la mitad de la completa bipartito gráfica tiene un solo vértice), y tomar todas las $k$-subconjuntos que se cruzan una sola (preseleccionada), elemento que en el otro lado.
