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$.



Splitting an evaluated complete graph
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. 


