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.
Maximum imbalance in a graph?
graph theory;co.combinatorics;spectral graph theory
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.