9
$\begingroup$

Assume you have a simple, infinite graph $G$ with bounded degree (there is an upper bound for the degree of the nodes). Choose an arbitrary vertex $x\in V(G)$ and consider $$ G_{n}:=\{x\in G:d(x_0,x)\leq n\} $$ with the graph metric (hop metric). Assume that each pair of nodes is communicating a unit load of information and the load goes through the minimum path between nodes (if there is more than one minimum path we choose one arbitrarily). The total traffic in $G_{n}$ is equal to $\frac{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 $G_{n}$ 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$.

If the graph $G$ is planar and it has exponential growth $|G_{n}|=K\exp(\lambda n)$ for $n$ sufficiently large, then it is not difficult to prove that there are nodes in $G_{n}$ such that $$ T_{n}(v)\geq C\frac{N^2}{\log(N)} $$ for $n$ sufficiently large.

My question is the following

Is the same true if we remove the planar condition but we keep the exponential growth? My intuition is that the answer is no but I can't find a counterexample.

$\endgroup$
6
  • $\begingroup$ In the sentence "The total traffic in $G_n$ is equal to $n(n-1)/2$" and later on you seem to be using $n$ to denote both the radius of the graph and its number of vertices. Could you, please, change the notation? $\endgroup$ Apr 4, 2011 at 20:04
  • $\begingroup$ It is not clear to me that G_n should have O(n) vertices, much less that the total traffic in G_n should be n choose 2. Can you clarify these points? Also, in the proof of the bound you seek, can you tell us how planarity is used, and what a weaker replacement might be that you are confident would work? Gerhard "Ask Me About System Design" Paseman, 2011.04.04 $\endgroup$ Apr 4, 2011 at 20:11
  • $\begingroup$ @Gerhard: I did an abuse of notation which I already corrected. I hope it makes sense now. For the proof of the planar case you essentially prove that you can break your graph in two almost equal parts by a path of length $2n$. $\endgroup$
    – ght
    Apr 4, 2011 at 20:27
  • $\begingroup$ The correction helps. For a possible counterexample, I can imagine the initial vertex v_0 being a central locus of a "backwater" of the entire graph, so that for large values of n is looks like traffic collects around v_0, but for even larger values of N, one ties into a vast river of shorter, regularly arranged nodes, so that there will be exponentially many nodes sharing loads, and that things will be distributed by, say, some kind of hypercube architecture. If bounded degree means limited connectvity though, it won't work. Gerhard "Ask Me About System Design" Paseman, 2011.04.04 $\endgroup$ Apr 4, 2011 at 20:53
  • $\begingroup$ @Gerhard: I don't understand your example. Bounded degree simply means that $\sup_{v\in G}\{deg(v)\}<\infty$. $\endgroup$
    – ght
    Apr 4, 2011 at 21:28

1 Answer 1

4
$\begingroup$

I think the following provides a counterexample.

The idea is to use the fact that on a graph $G$ with maximum degree $\Delta$ and diameter $D$ reasonably close to the natural lower bound $\log_{\Delta-1}|V(G)|$ the traffic is almost uniformly distributed.

Explicitly, for a vertex $v$, let $S_k(v):=\{x \in V(G) \: | \: d(x,v)=k\}$. Then $|S_k(v)| \leq \Delta(\Delta-1)^{k-1}$ and the traffic through $v$ can be estimated as $$T_G(v) \leq \sum_{k+l \leq D} |S_k(v)||S_l(v)| < D^2\Delta^2(\Delta-1)^{D-2}.$$

Bollobas and de la Vega in a paper "The diameter of random regular graphs" (last reference for Lecture 1 at the link.) show that for sufficiently large $N'$ a random $r$-regular graph on $N'$ vertices has diameter at most $\log_{r-1}(N') + \log_{r-1}(\log_{r-1}(N'))+C$, where $C$ is a (small) constant depending on $r$. By adjusting $C$, we may assume that an $r$-regular graph on $N'$ vertices satisfying this bound on diameter exists for any $N'$.

Finally, we construct $G$ by, first, taking an infinite $r$-regular tree, except that for simplicity of calculations we let the degree of $x_0$ be $r-1$. Secondly, we put an $r$-regular graph with the diameter bound listed above on the set of vertices $S_k(x_0)$, that is on each level of our infinite tree, considered as rooted at $x_0$.

Note that $|S_k(x_0)|=(r-1)^k$ and the diameter of $G|S_k(x_0)$ (i.e. $G$ restricted to $S_k(x_0)$) is at most $k + \log_{r-1}(k)+C$. It follows that the diameter of $G_n$ is at most $$\max_{k \leq l \leq n}( \mathrm{diam}(G|S_k(x_0)) + l-k) \leq n + \log_{r-1}(n)+C$$

The graph $G_n$ has maximum degree $\Delta = 2r$ and by the bound on the traffic load above we have $$ T_n(v) \leq n^2(2r-1)^{n+\log_{r-1}(n)+C'}$$ for any $v \in V(G_n)$ and some choice of $C'(r)$ independent on $n$. On the other hand $$|V(G_n)|=N =\sum_{k=0}^n (r-1)^k > (r-1)^n$$

It follows that, for any $\epsilon >0$ we can choose large enough $r$ so that for large $n$ we have $T_n(v) \leq N^{1 + \epsilon}$ for every $v \in G_n$.

$\endgroup$
3
  • $\begingroup$ I see the problem in your solution. The diameter of $G|S_{k}$ is at most $2(k+\log_{r-1}(k)+C)$. This makes all the difference. $\endgroup$
    – ght
    Apr 5, 2011 at 16:40
  • $\begingroup$ @Gabriel: It would make the difference, but I am not sure where your factor of $2$ comes from. $G|S_k$ has the structure of the $r$-regular graph I am discussing above with $N'=(r−1)^k$. $\endgroup$ Apr 5, 2011 at 16:55
  • $\begingroup$ @Norin: I'm sorry, I totally misunderstood your construction. What you are actually doing is joining the notes in $S_{k}(x_0)$ (which has size $(r-1)^k$) via a $r$ regular graph. I thought that you were attaching a $r$ regular graph at each node. Now it makes sense. Thanks! $\endgroup$
    – ght
    Apr 5, 2011 at 17:33

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.