<p>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 <a href="https://cstheory.stackexchange.com/a/71/168">know</a> that 3-regular expanders have linear treewidth, we are done.</p>

<p>See the construction of a tree decomposition given a BFS tree, it's slide 15 of this presentation: <a href="http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf" rel="nofollow noreferrer">http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf</a></p>

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

CC BY-SA 3.0
2011-12-22T14:26:46.737Z
Thanks for your answer, that presentation has been very helpful.
Giorgio Camerani
CC BY-SA 3.0
2011-12-19T17:10:05.083Z
2011-12-19T17:23:09.353Z
2017-04-13T12:32:28.053Z
didest
<p>The amplitude $\alpha(n) = \Theta(n)$  for expander graphs. A random 3-regular graph is asymptotically almost surely an expander graph <a href="http://en.wikipedia.org/wiki/Expander_graph#Examples_of_expanders">(see Wikipedia)</a>, 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$.</p>

<p>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 &lt; 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. </p>

<p>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.</p>

CC BY-SA 3.0
2011-12-19T09:13:20.147Z
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.
Giorgio Camerani
CC BY-SA 3.0
2011-12-19T13:14:23.250Z
with "empirical" you mean you actually ran tests? $\beta$ is about $0.1845$ for cubic random graphs, see ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf
didest
CC BY-SA 3.0
2011-12-19T14:51:06.363Z
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"
Giorgio Camerani
CC BY-SA 3.0
2011-12-19T15:05:29.767Z
...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.
Giorgio Camerani
CC BY-SA 3.0
2011-12-18T19:59:20.360Z
2011-12-18T22:02:27.457Z
2011-12-18T22:02:27.457Z
Peter Shor 
<p>Consider a connected <strong>random cubic</strong> graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined <a href="http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf" rel="nofollow">here</a>, i.e. $3n$ is even and any two graphs have the same probability). </p>

<p>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$. </p>

<p>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$. </p>

<p>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$. </p>

<p>Let us call $\alpha(G)$ the <i>amplitude</i> of $G$.</p>

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

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

CC BY-SA 3.0
2011-12-15T15:26:14.570Z
(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.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-15T15:41:41.520Z
@YoshioOkamoto: (1) From $G(n, 3$-reg$)$ as defined in http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf ($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.
Giorgio Camerani
CC BY-SA 3.0
2011-12-15T16:01:56.540Z
@SureshVenkat: Thanks for having improved the readability of the question ;-)
Giorgio Camerani
CC BY-SA 3.0
2011-12-15T17:07:57.057Z
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.
Peter Shor 
CC BY-SA 3.0
2011-12-15T18:02:47.420Z
@PeterShor: Of course I agree that, if such concentration results do exist, any of those values would be fine as well for answering the question.
Giorgio Camerani
CC BY-SA 3.0
2011-12-16T00:15:20.693Z
@WalterBishop: Let me ask one more question.  How do you define $\alpha(G)$ if $G$ is disconnected?
Yoshio Okamoto
CC BY-SA 3.0
2011-12-16T07:02:27.420Z
@YoshioOkamoto: You are right, I've edited the beginning of the question to clarify that I'm only interested in connected graphs.
Giorgio Camerani
CC BY-SA 3.0
2011-12-18T19:26:36.550Z
Perhaps first we can see what happens on families of 3-regular expander graphs with Cheeger constant $\geq h$
didest
<graph-theory><co.combinatorics>
Amplitude of Random Cubic Graphs
Giorgio Camerani
# Amplitude of Random Cubic Graphs

(Asked by: username_0 on 2011-12-15)

Consider a connected **random cubic** graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined [here](http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf), 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.

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_1**: (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.  
> **username_0**: @YoshioOkamoto: (1) From $G(n, 3$-reg$)$ as defined in http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf ($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.  
> **username_0**: @SureshVenkat: Thanks for having improved the readability of the question ;-)  
> **username_2**: 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.  
> **username_0**: @PeterShor: Of course I agree that, if such concentration results do exist, any of those values would be fine as well for answering the question.  
> **username_1**: @WalterBishop: Let me ask one more question.  How do you define $\alpha(G)$ if $G$ is disconnected?  
> **username_0**: @YoshioOkamoto: You are right, I've edited the beginning of the question to clarify that I'm only interested in connected graphs.  
> **username_3**: Perhaps first we can see what happens on families of 3-regular expander graphs with Cheeger constant $\geq h$  

---

## 2 answers

### Answer by username_2 on 2011-12-18. Score: 10 | Accepted answer

The amplitude $\alpha(n) = \Theta(n)$ for expander graphs. A random 3-regular graph is asymptotically almost surely an expander graph [(see Wikipedia)](http://en.wikipedia.org/wiki/Expander_graph#Examples_of_expanders), 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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: with "empirical" you mean you actually ran tests? $\beta$ is about $0.1845$ for cubic random graphs, see ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf  
> **username_0**: 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"  
> **username_0**: ...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.  

---

### Answer by username_3 on 2011-12-19. Score: 5

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](https://cstheory.stackexchange.com/a/71/168) 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.

> **Comments:**
> **username_0**: Thanks for your answer, that presentation has been very helpful.  

---

