Let $\{G\_{n}\}$ be a sequence of $k$-regular [expander graphs](http://en.wikipedia.org/wiki/Expander_graph). For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum path between nodes (if there is more than one minimum path we choose one arbitrarily). Then the total traffic in $G\_{n}$ is equal to $N(N-1)/2$ where $N=N(n)=|G\_{n}|$.


Given a node $v\in G\_{n}$ we define $T\_{n}(v)$ as the total traffic generated in the graph passing through $v$. In other words, $T\_{n}(v)$ is the sum off all the geodesic paths in $G\_{n}$ which are carrying traffic and contain the node $v$.


Let $T(G\_{n})$ be the maximum load in the graph. More precisely,
$$
T(G\_{n})=\max\_{v\in G\_{n}} \{T\_{n}(v)\}.
$$


As Lukasz pointed out this question can be reformulated without talking about traffic. For instance, for each two vertices we choose a geodesic that connects them and then define $T\_{n}(v)$ as the number of geodesics paths that pass through the node $v$.


My question is: 


* What can we say about the rate of growth of $T(G\_{n})$?
* Is there anything known in this direction?



Number of Geodesic Paths Passing Through a Vertex in an Expander Graph
My short answer: I think not much is known. But: here is the state of the art on related problems, as far as I am aware. 


[Aldous and Bhamidi](http://arxiv.org/pdf/0708.0555v1.pdf) consider the following model. Place independent exponential edge weights on the edges of the complete graph $K\_n$; we view the weights as edge lengths. Then, for each pair $u,v$ of vertices, place a constant flow between them on the shortest path from $u$ to $v$. For each edge $e$, write $F\_n(e)$ for the total flow along edge $e$ in the resulting network. Then for each fixed $z > 0$, as $n \to \infty$, 
`\[
\frac{1}{n} \#\{e: F_n(e) > z\log n\} \to \int_0^{\infty}\mathbb{P}(W_1W_2e^{-u} > z)~du,
\]`
where $W\_1$ and $W\_2$ are independent exponentials. (In fact, the paper proves a more detailed distributional convergence result.) In particular, *typical* edge congestion is $O(\log n)$; but the paper does not address *maximum* edge congestion. The paper also addresses vertex congestion (more directly linked to your question), showing a similar convergence result but with a more complicated term on the right-hand side of the convergence. As in the edge case, however, maximum vertex congestion is not treated, only typical congestion. 



> 
> What follows is less relevant as it relates to *global* strategies for minimizing congestion, rather than greedy routing between nodes. I'm posting it anyway in case it's useful. 
> 
> 
> 


Alan Frieze has [a survey on disjoint paths in expander graphs](http://math.cmu.edu/~af1p/Texfiles/R98.pdf) which may be of interest. Theorems 4 and 5 of that survey are results of Broder, Frieze and Upfal, which imply that in an expander, any set of at most $c n/\log^2 n$ pairs of vertices can be connected by disjoint paths, and that every pair can be connected by a path in such a way that the total congestion is $O(n \log n)$. 


Finally, for a particular class of *random* expanders, something can be said about a fractional version (flows rather than paths; again, this allows global optimization). Given a connected, undirected graph $G=(V,E)$, a *uniform flow of volume $\phi$* on $G$ is a collection $F$ of flows, one for each ordered pair $(v,w)$ of vertices of $G$, each having volume $\phi$. Given $f \in F$ and $e \in E$, write $f(e)$ for the flow through edge $e$ in $f$ (ignore direction so this is always non-negative). Then write 
`\[
\chi(F)=\max_{e \in E} \sum_{f \in F} f(e)
\]` 
for the maximum flow across any edge of $G$, when all flows of $F$ are simultaneously active 


[Aldous, Mcdiarmid, and Scott](http://www.stat.berkeley.edu/~aldous/Papers/me122.pdf) have proved the following. Fix a non-negative random variable $C$ with $\mathbb{E}(C) < \infty$, and take G\_n to be the complete graph $K\_n$ each of whose edges $e$ is weighted with an independent copy $C\_e$ of $C$. Let $\phi\_n$ be the largest value such that there exists a uniform flow $F$ of volume $\phi\_n$ on $G$ such that 
`\[
\sum_{f \in F} f(e) \le C_e
\]`
for all $e \in E(K\_n)$. Then there is a positive constant $\phi\_\*$ such that $\phi\_n \to \phi\_\*$ in probability. 


Note that if $C$ takes some fixed value $M$ with probability $p$, and is $0$ with probability $1-p$, this is equivalent to requiring maximum congestion $\le M$ on the random graph $G\_{n,p}$. Thus, this setting includes (edge) congestion-type bounds on at least some expander-like graphs. 


