Splitting an evaluated complete graph

Question

Suppose we are given a positive integer $k$. Let $K_k$ denote the complete (undirected and simple) graph with vertices $1, 2, \dots, k$. The set of edges of $K_k$ is the set $E_k = \{ \{ x,y \} \mid \ 1 \leq x < y \leq k\}$.

A valuation of $K_k$ is a function $\omega: E_k \rightarrow \mathbb Z$. A splitting of $K_k$ is a partition $\{ 1, 2, \dots, k \} = A \cup B$ of the vertices of $K_k$ into two nonempty sets $A$ and $B$.

Given a valuation $\omega$ of $K_k$ and a positive integer $n$, we call a splitting $A \cup B$ of $K_k$ $n$-valid, if the number $$\sum_{(x,y) \in A \times B} \omega(\{ x,y \})$$ is divisible by $n$.

Using Ramsey's theorem, one can prove that for every positive integer $n$, there exists a positive integer $k$ such that the following condition holds:

For any valuation $\omega$ of $K_k$, there is a splitting of $K_k$ that is $n$-valid.

If there exists at least one, there has to exist a smallest $k$ satisfying the above condition which we denote by $\eta(n)$.

Using the Combinatorial Nullstellensatz from N. Alon, one can show that $\eta(p) = 2p$ for odd primes $p$.

I now want to know if $\eta(n) = 2n$ is true for every integer $n \geq 3$.

Answer 1

The answer is NO, at least for $n=4$. I show here that $\eta(4) \leq 7$. So let $\omega$ be a valuation on $K_7$ ; we will show that it is $4$-valid.

First, we need some notation : for $A \cup B$ a nontrivial partition of $V=\lbrace 1,2,3, \ldots ,7\rbrace$, let

$$ s(A,B)=\\sum_{(x,y) \in A \times B} \omega(\{ x,y \}), \ f(A)=s(A,V\setminus A). $$

We can now write some useful relations :

$$ f( i,j)=f(i)+f(j)-2\omega(i,j), f(i,j,k)=f(i)+f(j)+f(k)-2(\omega(i,j)+\omega(i,k)+\omega(j,k)) $$

(where, for simplicity, we write $f(i)$ instead of $f(\lbrace i \rbrace)$, $f(i,j)$ instead of $f(\lbrace i,j \rbrace)$, etc).

Assume, by contradiction, that $\omega$ is not $n$-valid. Then the values of $f$ are all $1,2$ or $3$ modulo $4$. For convencience's sake, we now take $\omega$ and $f$ to take values in $\frac{\mathbb Z}{4\mathbb Z}$.

By easy double-counting, the sum $f(1)+f(2)+f(3)+ \ldots +f(7)$ is even (this is twice the sum of all the values of $\omega$), so that at least one $f(i)$ is even. Then $f(i)=2$. So the set $X=\lbrace i\in [1...7] | f(i)=2 \rbrace$ is not empty.

For any $i,j$ in $X$, we have $f(i,j)=4-2\omega(i,j)$, hence $\omega(i,j)=1$ or $3$ and $2\omega(i,j)=2$ in both cases. If $X$ contained more than two elements, we could find $i \lt j \lt k$ in $X$ and compute $f(i,j,k)=f(i)+f(j)+f(k)-2(\omega(i,j)+\omega(i,k)+\omega(j,k))=2+2+2-2-2-2=0$, a contradiction. So $|X| \leq 2$.

Similarly, we show that the set $Y=\lbrace i\in [1...7] | f(i)=1 \rbrace$ contains at most two elements. Reasoning as before, we have $2\omega(i,j)=0$ for any $i \lt j$ in $Y$. Recall that some $x$ in $[1...7]$ satisfies $f(x)=2$. We have $f(x,i,j)=-2(\omega(x,i)+\omega(x,j))$. By the pigeon-hole principle, if we had $|Y| \gt 2$ we cound find $i \lt j$ in $Y$ such that $\omega(x,i)=\omega(x,j)$, hence $f(x,i,j)=0$, a contradiction. So $|Y| \leq 2$.

Using the symmetry $x \mapsto -x$ in $\frac{\mathbb Z}{4\mathbb Z}$, we see that $|Y'| \leq 2$ where $Y'=\lbrace i\in [1...7] | f(i)=3 \rbrace$.

So, we have shown that on $[1..7]$, $f$ takes each of its three values ($1,2$ or $3$ mod $4$) at most twice. This contradicts the pigeonhole principle and finishes the proof.