Zero-Sum Over and the Story of
Graphs and Combinatorics, 2019•Springer
We prove the following results solving a problem raised by Caro and Yuster (Graphs Comb
32: 49–63, 2016). For a positive integer m ≥ 2 m≥ 2, m ≠ 4 m≠ 4, there are infinitely many
values of n such that the following holds: There is a weighting function f: E (K_n) → {-1, 1\} f:
E (K n)→-1, 1 (and hence a weighting function f: E (K_n) → {-1, 0, 1\} f: E (K n)→-1, 0, 1),
such that ∑ _ e ∈ E (K_n) f (e)= 0∑ e∈ E (K n) f (e)= 0 but, for every copy H of K_m K m in
K_n K n, ∑ _ e ∈ E (H) f (e) ≠ 0∑ e∈ E (H) f (e)≠ 0. On the other hand, for every integer n …
32: 49–63, 2016). For a positive integer m ≥ 2 m≥ 2, m ≠ 4 m≠ 4, there are infinitely many
values of n such that the following holds: There is a weighting function f: E (K_n) → {-1, 1\} f:
E (K n)→-1, 1 (and hence a weighting function f: E (K_n) → {-1, 0, 1\} f: E (K n)→-1, 0, 1),
such that ∑ _ e ∈ E (K_n) f (e)= 0∑ e∈ E (K n) f (e)= 0 but, for every copy H of K_m K m in
K_n K n, ∑ _ e ∈ E (H) f (e) ≠ 0∑ e∈ E (H) f (e)≠ 0. On the other hand, for every integer n …
Abstract
We prove the following results solving a problem raised by Caro and Yuster (Graphs Comb 32:49–63, 2016). For a positive integer , , there are infinitely many values of n such that the following holds: There is a weighting function (and hence a weighting function ), such that but, for every copy H of in , . On the other hand, for every integer and every weighting function such that $$|\sum _{e\in E(K_n)}f(e)|\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) - 2h(n)$$, where if (mod 4) and if (mod 4), there is always a copy H of in for which , and the value of h(n) is sharp.
Springer