# Splitting an evaluated complete graph

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

-
Your phrasing suggests that the edges are directed, specifically x < y for an edge (x,y) in E_k. Do you mean this? If not, your sum should be over (x,y) and over (y,x) in the product of A and B. Gerhard "Ask Me About System Design" Paseman, 2011.04.10 –  Gerhard Paseman Apr 10 '11 at 18:01
My main concern in the above comment is that (5,3) may be in AxB when (3,5) is not. Also, I suggest talking about n-valid in the definition, for clarity. Gerhard "Ask Me About System Design" Paseman, 2011.04.10 –  Gerhard Paseman Apr 10 '11 at 18:06
Thanks for the changes. It may be that the case $n=4$ is within reach of computer determination. Do you know anything more about $\eta(n)$ for nonprime values of $n$, including obvious lower bounds? Gerhard "Ask Me About System Design" Paseman, 2011.04.10 –  Gerhard Paseman Apr 11 '11 at 4:18
An easy lower bound : taking $\omega(x,y)=1$ if $1\in \lbrace x,y \rbrace$ and $\omega(x,y)=0$ otherwise, we see that $\eta(n) \geq n+2$. –  Ewan Delanoy Apr 11 '11 at 6:27
Ewan, I see that $\eta(n) >=n+1$ by that coloring. Can you tell me how you get $n+2$? Gerhard "Ask Me About System Design" Paseman, 2011.04.11 –  Gerhard Paseman Apr 11 '11 at 7:04

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.

-
For improving correctness, you should say that most equations involving $f$ or $\omega$ are mod 4, except in one case where they are mod 2. You could also replace the involution by the remark that the computation for $Y$ works for 3 mutatis mutandum (or whatever the phrase is for word for word) as it does for 1. I like it. Does it generalize to $n=6$? Gerhard "Ask Me About System Design" Paseman, 2011.04.12 –  Gerhard Paseman Apr 12 '11 at 18:22
Thanks. So the situation is more complicated in general. Any suggestions what $\eta(n)$ might be for an arbitrary $n$? –  Jens Reinhold Apr 12 '11 at 18:36
@ Gerhard : the initial equations in $f$ and $\omega$ hold over $\mathbb Z$, not just mod 4. Also, I carefully mention at the beginning of the proof " we take $f$ and $\omega$ to take values mod 4". Although arguing modulo 2 is natural in this context, all the "modular" equalities I wrote are in fact modulo 4. –  Ewan Delanoy Apr 12 '11 at 20:07
By the way, $\eta(4)$ is exactly $7$, of course. –  Ewan Delanoy Apr 12 '11 at 20:08
@ Jens : my guess is that although $\eta(n)$ need not equal $2n$, it will never be far from $2n$. –  Ewan Delanoy Apr 12 '11 at 20:12