Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
show 3 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.