symmetric $(2k)\times (2k)$ matrix, $k \geq 4$, consisting of $0$s and $1$s with exactly $k$ ones in each row and column

Question

Let $k \geq 4$. Let $M=(m_{ij})_{1 \leq i,j\leq 2k}$ be a symmetric $(2k)\times (2k)$ matrix whose entries are either $0$s or $1$s and

(1) All diagonal entries are zero, i.e., $m_{ii}=0$;

(2) Every row and every column have precisely $k$ ones.

(3) The total number of $1$s is $2k^2$.

(4) Assume that $$M \neq \begin{bmatrix}0^{k\times k} &1^{k\times k}\\1^{k\times k} &0^{k\times k}\end{bmatrix}, $$ or any matrix that consists of an elementary permutation of this matrix (I could not think of a better way to say this).

Suppose that $M_1, \ldots, M_{2k}$ are the row vectors (also the column vectors by symmetry) of $M$. I want to prove the existence of two integers $1 \leq i<j \leq 2k$ such that $m_{ij}=m_{ji}=1$ and $M_i \cdot M_j^T\geq 2$.

I cannot find a counterexample for smaller cases like $k=4$ and $k=5$. I wanted to try to prove this by contradiction: Suppose that for each $1\leq i<j\leq 2k$ such that $m_{ij}=m_{ji}=1$ and $M_i \cdot M_j^T\in \{0,1\}$. Here is where I hit a wall. Any suggestions?

---

I will include the graph theory equivalent problem: Let $k \geq 4$. Given a $k$-regular graph on $2k$ vertices and $k^2$ edges such that $G \not \cong K_{k,k}$, show that there exists an edge $xy \in E(G)$ such that $|N(x)\cap N(y)|\geq 2$, i.e., $x$ and $y$ have at least two neighbors. This is equivalent to showing that $G$ must contain a subgraph isomorphic to $K_4-e$.

If it is of any help, there is a theorem by Paul Erdős that says that such a graph, as described above, should have at least $k-1$ triangles. I want to show that there exist two triangles that share an edge.

Answer 1

This--the statement you are intending to prove--is equivalent to saying that there are two adjacent vertices in any undirected $k$-regular graph $G$ on $2k$ vertices that isn't complete bipartite share at least 2 neighbours. Here is a proof for $k > 3$:

Let $v$ be an arbitrary vertex in $G$. Let $N(v)$ be the set of vertices of distance 1 (this set has $k$ vertices) and let $N_2(v)$ be the remaining $k-1$ vertices. By the fact that $G$ isn't complete bipartite there are at least two vertices $u$ and $w$ in $N(w)$ that are adjacent, lest every vertex in $N(v)$ be adjacent to all $k-1$ vertices in $N_2(v)$ [due to $k$-regularity]

Now let $C_w$ be the number of vertices in $N(v)$ that $w$ is adjacent to besides $u$ and let $C_u$ be the number of vertices in $N(v)$ that $u$ is adjacent to besides $w$. Then both $C_w$ and $C_u$ must be 0, or (assuming WLOG that $C_w$ is positive) $w$ is adjacent to $v$ and then would share two neighbors with $v$ (namely $u$ and the $C_w$ other vertices in $N(v)$).

On the other hand, $u$ is adjacent to $k-2-C_u$ vertices in $N_2(v)$ while $w$ is adjacent to $k-2-C_w$ vertices in $N_2(v)$. So for these sets to not overlap (if they overlap then we are done) then $2k-4-(C_u+C_w) \leq k-1$ implying $C_u+C_w \geq k-3$. As we already have shown in the previous paragraph that $C_u+C_w$ must be 0, this leads to a contradiction.

Answer 2

Wouldn't the following be a counterexample: $$ M = \begin{bmatrix}0^{k\times k} &1^{k\times k}\\1^{k\times k} &0^{k\times k}\end{bmatrix}, $$ where $0^{k\times k}$ and $1^{k\times k}$ are $k\times k$ matrices of zeroes and ones?

In order to have $m_{i,j}=1$, you need to have $i\le k$ and $j>k$, or the opposite. But then $$M_i\cdot M_j^T=(1,\dots1,0\dots,0)\cdot(0,\dots,0,1\dots,1)=0.$$

Answer 3

However, this isn't true for $k=3$. We construct a graph $G$ that is a counterexample. Let the vertex set of $G$ be $\{t,u,v,w,x,y\}$.

Then $G$'s edge-set is precisely $\{ \{t,u\},\{t,v\},\{t,w\}, \{u,w\}, \{v,x\},\{v,y\}, \{u,x\},\{w,y\}, \{x,y\} \}$. This graph has a triangle $(v,x,y)$ but no two adjacent vertices share 2 other neighbours.

Furthermore, for $k=2$ the only 2 regular graph on 4 vertices is the square which is complete bipartite. And for $k=1$ a 1-regular graph on 2 vertices is a single edge.

So the above is the full answer.