Amplitude of Random Cubic Graphs

Consider a connected random cubic graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined here, i.e. $3n$ is even and any two graphs have the same probability).

Of course there are $n$ possible Breadth First Searches, one for each starting node $s \in V$. A Breadth First Search $B_G$ starting at node $s \in V$ assigns a level $d(s, v)$ to each node $v \in V$, where $d(s, v)$ is the distance between $s$ and $v$ in $G$.

Let us say that such a Breadth First Search $B_G$ also assigns a level $$L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$$ to each edge $e=\{u,v\} \in E$.

Given a specific Breadth First Search $B_G$, let $\alpha(B_G,i)$ be the number of edges that have been assigned level $i$, and let $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$. In other words $\alpha(B_G)$ is the number of edges of the level containing more edges than any other level. Finally, let $\alpha(G)$ be the maximum $\alpha(B_G)$ for any of the $n$ Breadth First Searches of $G$.

Let us call $\alpha(G)$ the amplitude of $G$.

Question

How does the expected value of $\alpha(G)$ grow as $n$ tends to infinity? Recall that $G$ is random cubic. More precisely, what I really would like to know is whether the expected value of $\alpha(G)$ belongs to $o(n)$.

Since $n$ is even, the limit is considered so that I don't care of odd $n$'s.

• (1) Please specify from which probability distribution you draw your cubic graph. (2) Are you interested in the expectation of $\alpha(G)$ as a function of $n$, or something else? (3) I suppose $n$ is even (otherwise a cubic graph doesn't exist). So, I suppose the limit is considered so that you don't care for odd $n$'s. Dec 15, 2011 at 15:26
• @YoshioOkamoto: (1) From $G(n, 3$-reg$)$ as defined in stanford.edu/class/msande337/notes/… ($3n$ is even and any two graphs have the same probability). (2) I've enriched the question to clarify this point. (3) Yes, $n$ is even and the limit is considered so that I don't care of odd $n$'s. Dec 15, 2011 at 15:41
• @SureshVenkat: Thanks for having improved the readability of the question ;-) Dec 15, 2011 at 16:01
• Let me say that it is quite likely that there are concentration results for $\alpha(G)$ on random cubic graphs, which means that the expected value, the high probability value, and so on, are all the same. Unless the OP clarifies, I think an answer for any of these questions would be a reasonable answer for this question. Dec 15, 2011 at 17:07
• @WalterBishop: Let me ask one more question. How do you define $\alpha(G)$ if $G$ is disconnected? Dec 16, 2011 at 0:15

The amplitude $\alpha(n) = \Theta(n)$ for expander graphs. A random 3-regular graph is asymptotically almost surely an expander graph (see Wikipedia), so the expectation of the amplitude will be $\Theta(n)$, since the probability that it's not an expander graph goes to $0$ as $n$ goes to $\infty$.

For an expander graph with parameter $\beta$, for any set of $s$ vertices with $s \leq n/2$, there are $\beta s$ neighbors of the set. Now, let the number of vertices on level $j$ be $\ell_j$, with $\ell_0=1$. We then have from the expansion property that as long as $j$ is not too large (i.e., we haven't included half the vertices yet) $$\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}$$ Now, look for the level $\ell_j$ which contains vertex $\frac{n}{3}$. That is, so $\sum_{i=0}^{j-1} \ell_i < n/3$ and $\sum_{i=0}^{j} \ell_i \geq n/3$. If this level is large, i.e., $\ell_j \geq n/6$, we are done. Otherwise, the next level has size $$\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},$$ and we are done.

While this proof looks at the number of vertices in a level rather than the number of edges (which the OP asked about), there are always at least as many edges added in step $i$ as vertices in level $i$, since each vertex must be reached by some edge.

• Thanks for your answer! This is very surprising (at least to me): even if the total number of edges is $m = 1.5 \cdot n \in \Theta(n)$, and the number of levels is $\Omega(log(n))$, the most crowded level has still $\Theta(n)$ edges. Thus the edges are not scattered uniformly among the levels: my (empirical, wrong) intuition was that, except for few initial levels and few final levels, there should have been $\Omega(log(n))$ central levels among which the edges would have been scattered somewhat uniformly. Dec 19, 2011 at 9:13
• with "empirical" you mean you actually ran tests? $\beta$ is about $0.1845$ for cubic random graphs, see ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf Dec 19, 2011 at 13:14
• Yes I ran tests from $n = 100$ up to $n = 150000$ and measured the quantity $k = \frac{\alpha(G)}{m}$. If $k$ approached $0$ as $n$ increased, this would have given empirical evidence that $\alpha(G) \in o(n)$. Around $n=100$, $k$ was about $0.3$, while around $n=150000$, $k$ was about $0.26$ (of course I've never considered these numbers as empirical evidence, because $n = 150000$ is still too small to represent an asymptotic). However when I said "empirical intuition" Dec 19, 2011 at 14:51
• ...I meant a real (wrong) feeling rather than the outcome of the tests: I somewhat felt that those BFS must have a "sausage" shape (i.e. tiny at the extremes, and of constant tickness in the middle). "They have to be like that", I thought. The above proof shows how plain wrong my intuition was. Nonetheless, I'm still surprised: $\Theta(n)$ edges, $\Omega(log(n))$ levels, but not $O(\frac{n}{log(n)})$ edges on each level. Dec 19, 2011 at 15:05

Peter Shor's answer is really good, but there is another way to answer this: proving that treewidth is upper bounded by two times the amplitude (the vertex version). Since we know that 3-regular expanders have linear treewidth, we are done.

See the construction of a tree decomposition given a BFS tree, it's slide 15 of this presentation: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

It's easy to see that the size of every bag is upper bounded by two times the widest level.