Vamos a $G$ es bipartito gráfico con lados de $X=\{v_1,v_2,\ldots,v_n\}$ $Y=\{u_1,u_2,\ldots,u_n\}.$ Deje $|N_G(v_i)|=k$$|N_G(v_i)\cap N_G(v_j)|=d\lt k~,(i\ne j)$. Demostrar que $|N_G(u_i)|=k$ y $|N_G(u_i)\cap N_G(u_j)|=d,~(i\ne j)$. $N_G(v)$ es el barrio de vértice $v$ en el gráfico $G$.
No tengo idea de cómo puedo empezar la prueba.
Deje $A$ denotar la matriz de adyacencia para el gráfico. Tenemos orden de los vértices de tal manera que podemos escribir $$A = \begin{pmatrix} 0 & B\\B^\mathrm{T} & 0\end{pmatrix}$$ Tenga en cuenta que una descomposición como esto es posible para cualquier bipartito gráfico. La matriz $B$ representa la incidencia de la $X$$Y$. Tenga en cuenta que por la asunción de $|X|=|Y|=n$, la matriz $B$ $n\times n$ matriz cuadrada. También tenga en cuenta que $B$ es un $0$-$1$ de la matriz.
Las condiciones que $|N_G(v_i)|=k$ $|N_G(v_i)\cap N_G(v_j)| = d<k$ ahora traducir a $$\mathbf{b}_i\cdot \mathbf{b}_j = (k-d)\delta_{ij}+d$$ donde $\mathbf{b}_i$ indica el $i$ésima fila de la matriz $B$. La condición anterior, por supuesto, implica que $$BB^\mathrm{T} = (k-d)I_n + dJ_n\tag{*}$$ donde $I_n$ es la matriz identidad y $J_n$ es la matriz de todos.
Lema: Un $0$-$1$ matriz cuadrada $B$ que satisface ( $*$ ) $k>d$ es invertible normal de la matriz.
La prueba: Los autovalores (arriba a la multiplicidad) de $J_n$$n$$0$, por lo que los autovalores de a$BB^\mathrm{T}$$k+(n-1)d$$k-d$. En particular, esto significa que $BB^\mathrm{T}$ es invertible y, por tanto, $B$ también es invertible.
Cuenta ahora de que $B$ satisface $$BJ = kJ,\ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ J=kB^{-1}J$$ Haga multiplicando $(*)$ $J$ da $$BB^\mathrm{T}J = (k-d)J + dJ^2 = (k-d)J + ndJ = [k+(n-1)d]J$$ La aplicación de $B^{-1}$ a la anterior, obtenemos $$B^\mathrm{T}J = [k+(n-1)d]B^{-1}J = \frac{k+(n-1)d}{k}J$$ Tomando la transpuesta de la anterior, obtenemos $$JB = \frac{k+(n-1)d}{k}J$$ Derecho-multiplicando por $J$ rendimientos $$JBJ = n\frac{k+(n-1)d}{k}J$$ Por otro lado, también sabemos que $BJ = kJ$, de modo que $$JBJ = nkJ$$ En comparación, se debe tener $$k = \frac{k+(n-1)d}{k}$$ Por lo tanto, tenemos $$JB = kJ = BJ$$ y, en consecuencia, $B$ $B^\mathrm{T}$ viajes con $BB^\mathrm{T}$. Por lo tanto $$B^\mathrm{T}B = B^\mathrm{T}(BB^\mathrm{T})(B^T)^{-1} = (BB^\mathrm{T})[B^\mathrm{T}(B^\mathrm{T})^{-1}] = BB^\mathrm{T}$$ como se requiere. $\square$
Por último, tenga en cuenta que $$B^\mathrm{T}B = (k-d)I_n + dJ_n$$ es precisamente la condición necesaria para $|N_G(u_i)| = k$$|N_G(u_i)\cap N_G(u_j)|=d$, lo que completa la prueba. Además, tenemos el siguiente corolario según lo revelado por la prueba.
Corolario: Si $G$ satisface la mencionada hipótesis, entonces $k^2 - k = (n-1)d$. $\square$
Tenga en cuenta que el anterior corolario tiene una simple combinatoria de interpretación. Fijar un vértice arbitrario $v\in X$ y tener en cuenta el número de maneras en que podemos llegar a algún otro vértice $v\neq v'\in X$ $2$ pasos. Se cuenta en $2$ maneras.
En primer lugar, desde $v$ $k$ vecinos en $Y$, se puede elegir cualquiera de las $k$ vecinos. Cada vecino de $v$ también ha $k$ a los vecinos, uno de los cuales es $v$ sí. Por lo tanto, podemos llegar a algún vértice $v'\in X$ $k(k-1)$ maneras.
Alternativamente, cada una de las $n-1$ otros vértices de $X$ de las acciones de un tamaño de $d$ barrio con $v$. Por lo tanto, cada una de las $v'\in X$ puede ser alcanzado precisamente en $d$ formas de $v$. El número total de maneras de $v$ a algunos otros $v'$ por lo tanto $d(n-1)$.
Como prometí aquí está la solución.
Vamos a $A=(a_{ij})_{i,j=1}^n$ ser la siguiente matriz: $a_{ij}=1,$ si $\{v_i,u_j\}$ es el borde de la gráfica de $G$ $a_{ij}=0,$ lo contrario. A partir de las condiciones que se deduce que $AA^T=dB+(k-d)I,$ donde $B$ es una matriz con todas las entradas de la igualdad de $1$. Es fácil de comprobar (mediante la búsqueda de determinante o mediante la demostración de que las columnas independientes) que $det(AA^T)\ne0,$ por lo tanto $det(A)\ne0$. Así tenemos $$A^TA=A^{-1}(AA^T)A=dA^{-1}BA+(k-d)I.$$ Now to complete the proof we need to prove that $A^{-1}BA=B,$ that is, $AB=BA$. Let $e^T=(1,1,\ldots,1)$, then $e$ is an eignvector for $A$ (therefore for $A^{-1}$ too) and also for $AA^T$. So $e$ is an eignvector for $A^{-1}(AA^T)=A^T$, $A^Te=k'e.$ As $k'n=e^TAe=kn$, $k'=k$. Therefore $eA=ke~\Rightarrow~BA=kB=AB.$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
