Maximum imbalance in a graph?

Question

Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average weight per node then is $\bar w = m/n$. Let $e_i = w_i - \bar w$ denote the deviation of node $i$ from the mean. We call $|e_i|$ the imbalance of node $i$.

Suppose that the weight between any two adjacent nodes can differ by at most $1$, i.e., $$ w_i - w_j \le 1\; \forall (i,j) \in E.$$

Question: What is the largest possible imbalance the network can have, in terms of $n$ and $m$? To be more precise, picture the vector $\vec{e} = (e_1, \dots, e_n)$. I'd be equally content with results concerning $||\vec{e}||_1$ or $||\vec{e}||_2$.

For $||\vec{e}||_\infty$, a simple bound in terms of the graph diameter can be found: Since all $e_i$ must sum to zero, if there is a large positive $e_i$, there must somewhere be a negative $e_j$. Hence their difference $|e_i - e_j|$ is at least $|e_i|$, but this difference can be at most the shortest distance between nodes $i$ and $j$, which in turn can be at most the graph diameter.

I'm interested in stronger bounds, preferably for the $1$- or $2$-norm. I suppose it should involve some spectral graph theory to reflect the connectivity of the graph. I tried expressing it as a max-flow problem, to no avail.

EDIT: More explanation. I'm interested in the $1$- or $2$-norm as they more accurately reflect the total imbalance. A trivial relation would be obtained from $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$, and $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$. I expect, however, that due to the connectedness of the graph and my constraint in the difference of loads between adjacent nodes, that the $1$- and $2$-norms should be much smaller.

Example: Hypercube of Dimension d, with $n = 2^d$. It has diameter $d = \log_2(n)$. The maximum imbalance is then at most $d$. This suggest as an upper bound for the $1$-norm $nd = n\log_2(n)$. So far, I have been unable to construct a situation where this is actually obtained, the best I can do is something along the lines of $||\vec{e}||_1 = n/2$, where I embed a cycle into the Hypercube and have the nodes have imbalances $0$, $1$, $0$, $-1$ etc. So, here the bound is off by a factor of $\log(n)$, which I consider already too much, as I'm looking for (asymptotically) tight bounds.

Answer 1

Since $|e_i|$ is bounded by the diameter $d$, the $\ell_1$ norm is going to be trivially bounded by $nd$, likewise for the $\ell_2$ norm, except by $\sqrt{n}d$ (in fact the $\ell_p$ norm is bounded by $n^{1/p}d$).

The $\ell_1$ case turns out to be surprisingly easy to analyze.

For a path, it's easy to see that $\|\vec e\|_1$ is $O(n^2)$, so you can't do any better than $O(nd)$.

For a complete $k$-ary tree, you can divide it in half at the root, setting $w_{\text{root}} = 0$, ascending one side and descending the other until the leaves have $|e_i| = |w_i| = \log_k n$, producing $O(n\log_k n) = O(nd)$ again.

For a clique it doesn't really matter how you distribute the weights, since they'll all be within $1$ of each other, and that will yield $O(n) = O(nd)$ again.

When you realize that what we're talking about here is a function $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$, and then we're taking its $\ell_1$ norm, as long as you can arbitrarily distribute weights $e_i \in [-d/2,d/2]$ evenly across the range, the bound will be $O(nd)$.

The only way to change this is to play games with the mass. For instance, if you have several giant cliques at points that are necessarily balanced, like a giant clique with two paths of equal length jutting out of it, then you can count on a bound of only (for example) $O(d^2)$.

This may be true for expanders to some degree as well, but I'm not sure. I could imagine a case where you set $w_1 = 0$ in a regular graph and then let the values increase subsequently from every hop. It seems likely that the mean could possibly have the most mass, but I don't know if it would be enough to affect the bound.

I think that you could reason similarly about $\ell_2$.

EDIT:

In the comments we figured out a (loose) $\ell_2$ bound of $O(|E|/\lambda_2(L))$ using the constraints of the problem and some basic spectral graph theory.

Answer 2

For connected graphs, the imbalance is upper bounded by the diameter of the graph. In order to bound the imbalance $|w_i - 1/n\sum_k w_k|$, we can rewrite each $w_k$ as $w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i + w_i$ where $w_k, v_1,...,v_k, w_i$ is the shortest path from $w_i$ to $w_k$. Define $w_{ki} = w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i$. We can write $$|w_i - 1/n\sum_k w_k| = |w_i - 1/n\sum_k (w_{ki} + w_i)| = |\sum_{k\neq i} \frac{w_{ki}}{n}|$$

Each $w_{ki}$ is upper bounded by the length of the shortest path from $i$ to $k$ by your assumption that $w_i - w_j \leq 1$ for each $i,j\in E$. Therefore, we get the trivial bound: $$|w_i - 1/n\sum_k w_k| \leq \frac{(n-1)}{n} D$$

This might not actually be too far from optimal. I'm thinking of a complete $k$-ary tree where the nodes on each level have weight one higher than the weight of the previous level. A large fraction of the graph has the highest weight, $D+1$. So, the average should be skewed towards the top. As $k$ and $n$ get larger, I expect $m$ to get closer and closer to $D+1$ which means the imbalance should get closer and closer to $D$.