Zero-sum bipartite Ramsey numbers

NEW

Problem: Reconstruct $B(H,\mathbb Z_k)$ as the least $N$ such that every edge-labeling $c:E(K_{N,N})\to\mathbb Z_k$ contains a copy of $H$ whose edge-label sum is $0\in\mathbb Z_k$. The conjecture is:

For every integer $n\ge2$,

$$B(K_{2,n},\mathbb Z_{2n})\le 4n-3 .$$

Result: The conjecture is true.

Let $m=4n-3$, and label the two parts of $K_{m,m}$ by $L,R$. Given any coloring $c:E(K_{m,m})\to\mathbb Z_{2n}$, assign to each $x\in L$ its parity vector

$$p(x)=(c(x,y)\bmod 2)_{y\in R}\in\{0,1\}^m .$$

We need the following binary-code lemma.

Lemma. Among any $m=4n-3$ binary vectors of length $m$, two agree in at least $2n-1$ coordinates.

Proof. Suppose not. Then every pair has Hamming distance at least $2n-1=(m+1)/2$. Let $D$ be the sum of all pairwise Hamming distances. For each coordinate, if $t$ vectors have value $1$, its contribution is $t(m-t)\le (m^2-1)/4$, since $m$ is odd. Hence

$$D\le m\frac{m^2-1}{4}.$$

But the assumed minimum distance gives

$$D\ge \binom m2\frac{m+1}{2}=m\frac{m^2-1}{4}.$$

Thus equality holds everywhere. Hence all pairwise distances are $(m+1)/2$, and each coordinate is balanced, with column sum $\pm1$ in $\{\pm1\}$-notation.

Converting the binary vectors to rows of a $\{\pm1\}$-matrix $X$, we get pairwise row inner products $-1$. The equality/balance condition extends $X$ to a Hadamard matrix of order $m+1=4n-2$. But a Hadamard matrix of order $>2$ must have order divisible by $4$, contradiction. Since $4n-2\equiv2\pmod4$ and $n\ge2$, the lemma follows. $\square$

By the lemma, choose distinct $x,x'\in L$ agreeing in parity on a set $S\subseteq R$ with $|S|\ge2n-1$. For each $y\in S$,

$$c(x,y)+c(x',y)$$

is even in $\mathbb Z_{2n}$, so uniquely equals $2b_y$ for some $b_y\in\mathbb Z_n$.

By the Erdős–Ginzburg–Ziv theorem applied in $\mathbb Z_n$, among any $2n-1$ of the $b_y$'s there exist $n$ of them, say indexed by $T\subseteq S$, with

$$\sum_{y\in T} b_y=0\in\mathbb Z_n .$$

Therefore

$$\sum_{y\in T}\bigl(c(x,y)+c(x',y)\bigr) =2\sum_{y\in T}b_y =0\in\mathbb Z_{2n}.$$

Thus the subgraph induced by $\{x,x'\}\subseteq L$ and $T\subseteq R$ is a zero-sum copy of $K_{2,n}$. Since the coloring was arbitrary,

$$B(K_{2,n},\mathbb Z_{2n})\le 4n-3.$$

Audit: the proof uses exactly the reconstructed balanced bipartite zero-sum Ramsey definition, assumes only $n\ge2$, and proves the stated upper bound.

Citation: Problem source: Y. Caro, “Zero-sum bipartite Ramsey numbers,” Math. Bohem. 122 (1997). External ingredient: Erdős–Ginzburg–Ziv theorem, P. Erdős, A. Ginzburg, A. Ziv, “Theorem in the additive number theory,” Bull. Res. Council Israel 10F (1961), 41–43.