7
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$ Apr 10, 2011 at 18:01
  • $\begingroup$ 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 $\endgroup$ Apr 10, 2011 at 18:06
  • $\begingroup$ 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 $\endgroup$ Apr 11, 2011 at 4:18
  • $\begingroup$ 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$. $\endgroup$ Apr 11, 2011 at 6:27
  • $\begingroup$ 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 $\endgroup$ Apr 11, 2011 at 7:04

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$ Apr 12, 2011 at 18:22
  • $\begingroup$ Thanks. So the situation is more complicated in general. Any suggestions what $\eta(n)$ might be for an arbitrary $n$? $\endgroup$ Apr 12, 2011 at 18:36
  • $\begingroup$ @ 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. $\endgroup$ Apr 12, 2011 at 20:07
  • $\begingroup$ By the way, $\eta(4)$ is exactly $7$, of course. $\endgroup$ Apr 12, 2011 at 20:08
  • $\begingroup$ @ Jens : my guess is that although $\eta(n)$ need not equal $2n$, it will never be far from $2n$. $\endgroup$ Apr 12, 2011 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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