10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ (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. $\endgroup$ – Yoshio Okamoto Dec 15 '11 at 15:26
  • $\begingroup$ @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. $\endgroup$ – Giorgio Camerani Dec 15 '11 at 15:41
  • $\begingroup$ @SureshVenkat: Thanks for having improved the readability of the question ;-) $\endgroup$ – Giorgio Camerani Dec 15 '11 at 16:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Shor Dec 15 '11 at 17:07
  • 2
    $\begingroup$ @WalterBishop: Let me ask one more question. How do you define $\alpha(G)$ if $G$ is disconnected? $\endgroup$ – Yoshio Okamoto Dec 16 '11 at 0:15
10
+200
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Giorgio Camerani Dec 19 '11 at 9:13
  • $\begingroup$ 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 $\endgroup$ – Diego de Estrada Dec 19 '11 at 13:14
  • $\begingroup$ 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" $\endgroup$ – Giorgio Camerani Dec 19 '11 at 14:51
  • $\begingroup$ ...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. $\endgroup$ – Giorgio Camerani Dec 19 '11 at 15:05
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer, that presentation has been very helpful. $\endgroup$ – Giorgio Camerani Dec 22 '11 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.