simétrica $(2k)\times (2k)$ matriz, $k \geq 4$, que consta de $0$s y $1$s con exactamente $k$ en cada fila y columna

Question

Deje $k \geq 4$. Deje $M=(m_{ij})_{1 \leq i,j\leq 2k}$ ser simétrica $(2k)\times (2k)$ matriz cuyas entradas son o $0$s o $1$s y

(1) Todas las entradas de la diagonal son cero, es decir, $m_{ii}=0$;

(2) Cada fila y cada columna tiene, precisamente,$k$.

(3) El número total de $1$s es $2k^2$.

(4) Suponga que $$M \neq \begin{bmatrix}0^{k\times k} &1^{k\times k}\\1^{k\times k} &0^{k\times k}\end{bmatrix}, $$ o cualquier matriz que consiste en una primaria de permutación de esta matriz (yo no podía pensar en una mejor manera de decirlo).

Supongamos que $M_1, \ldots, M_{2k}$ son los vectores fila (también los vectores columna por simetría) de $M$. Yo quiero probar la existencia de dos enteros $1 \leq i<j \leq 2k$ tal que $m_{ij}=m_{ji}=1$$M_i \cdot M_j^T\geq 2$.

No puedo encontrar un contraejemplo para las pequeñas casos como el de $k=4$$k=5$. Quería probar esta contradicción: Supongamos que para cada una de las $1\leq i<j\leq 2k$ tal que $m_{ij}=m_{ji}=1$$M_i \cdot M_j^T\in \{0,1\}$. Aquí es donde chocó contra un muro. Alguna sugerencia?

---

Voy a incluir la teoría de grafos problema equivalente: Vamos a $k \geq 4$. Dado un $k$-gráfico regular en $2k$ vértices y $k^2$ bordes, que $G \not \cong K_{k,k}$, muestran que existe una arista $xy \in E(G)$ tal que $|N(x)\cap N(y)|\geq 2$, es decir, $x$ $y$ tiene al menos dos vecinos. Esto es equivalente a mostrar que la $G$ debe contener un subgrafo isomorfo a $K_4-e$.

Si te sirve de ayuda, hay un teorema por Paul Erdős que dice que una gráfica, como se describió anteriormente, debe tener al menos $k-1$ triángulos. Quiero mostrar que existen dos triángulos que comparten un borde.

Answer 1

Esto-la declaración que se pretende demostrar-es equivalente a decir que hay dos vértices adyacentes en cualquier grafo $k$-gráfico regular $G$ $2k$ vértices que no está completa bipartito compartir al menos 2 vecinos. Aquí es una prueba para $k > 3$:

Deje $v$ ser un vértice arbitrario en $G$. Deje $N(v)$ el conjunto de vértices de la distancia 1 (este conjunto ha $k$ vértices) y deje $N_2(v)$ ser el resto de $k-1$ vértices. Por el hecho de que $G$ no está completa bipartito hay al menos dos vértices $u$ $w$ $N(w)$ que son adyacentes, para cada vértice $N(v)$ estar al lado de todos los $k-1$ vértices en $N_2(v)$ [debido a $k$-regularidad]

Ahora vamos a $C_w$ el número de vértices en $N(v)$ que $w$ es adyacente además de a $u$ y deje $C_u$ el número de vértices en $N(v)$ que $u$ es adyacente además de a $w$. A continuación, tanto en $C_w$ $C_u$ debe ser 0, o (suponiendo WLOG que $C_w$ es positivo) $w$ es adyacente a $v$ y luego compartir dos vecinos con $v$ (es decir, $u$ e las $C_w$ otros vértices en $N(v)$).

Por otro lado, $u$ es adyacente a $k-2-C_u$ vértices en $N_2(v)$ mientras $w$ es adyacente a $k-2-C_w$ vértices en $N_2(v)$. Así que para estos conjuntos para que no se superponen (si se superponen, a continuación, se realiza), a continuación, $2k-4-(C_u+C_w) \leq k-1$ lo que implica $C_u+C_w \geq k-3$. Como ya hemos visto en el párrafo anterior que $C_u+C_w$ debe ser 0, esto lleva a una contradicción.

Answer 2

¿No crees que el siguiente sea un contraejemplo: $$ M = \begin{bmatrix}0^{k\times k} &1^{k\times k}\\1^{k\times k} &0^{k\times k}\end{bmatrix}, $$ donde $0^{k\times k}$ $1^{k\times k}$ $k\times k$ matrices de ceros y unos?

Con el fin de tener $m_{i,j}=1$, usted necesita tener $i\le k$$j>k$, o al contrario. Pero, a continuación, $$M_i\cdot M_j^T=(1,\dots1,0\dots,0)\cdot(0,\dots,0,1\dots,1)=0.$$

Answer 3

Sin embargo, esto no es cierto para $k=3$. Se construye un gráfico de $G$ que es un contraejemplo. Deje que el conjunto de vértices de $G$$\{t,u,v,w,x,y\}$.

A continuación, $G$'s edge es, precisamente,$\{ \{t,u\},\{t,v\},\{t,w\}, \{u,w\}, \{v,x\},\{v,y\}, \{u,x\},\{w,y\}, \{x,y\} \}$. Esta gráfica tiene un triángulo $(v,x,y)$, pero no hay dos vértices adyacentes comparten los otros 2 vecinos.

Además, para $k=2$ sólo el 2 regular el gráfico de 4 vértices es la plaza, la cual se completa bipartito. Y para $k=1$ 1 gráfico regular en 2 vértices es de un solo filo.

Por lo que la anterior es la respuesta completa.