Amplitude of Random Cubic Graphs

Question

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.

Answer 1

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.

Answer 2

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.