<p>Not sure whether I am missing something, but...</p>

<p>The Omega(n/log n) lower bound is from:</p>

<p>[PTC77] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10:239–251, 1977.</p>

<p>There is a strengthening of this to a non-deterministic version of the pebble game (so-called black-white pebbling) in:</p>

<p>[GT78] John R. Gilbert and Robert Endre Tarjan. Variations of a pebble game on graphs. Technical Report STAN-CS-78-661, Stanford University, 1978. Available at <a href="http://infolab.stanford.edu/TR/CS-TR-78-661.html" rel="noreferrer">http://infolab.stanford.edu/TR/CS-TR-78-661.html</a> .</p>

<p>And --- self-plug warning --- you find a somewhat careful exposition of the latter lower bound, together with some nice illustrations, in the survey <a href="http://www.csc.kth.se/~jakobn/research/PebblingSurveyTMP.pdf" rel="noreferrer">http://www.csc.kth.se/~jakobn/research/PebblingSurveyTMP.pdf</a> (see Section 7 starting on page 51).</p>

<p>Another good source on some classic pebbling stuff is Chapter 10 of:</p>

<p>[Sav98] John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley,1998. Available at <a href="http://www.modelsofcomputation.org" rel="noreferrer">http://www.modelsofcomputation.org</a> .</p>

CC BY-SA 4.0
2019-09-04T21:04:27.430Z
This is so perfect! Thank you!
exfret
CC BY-SA 4.0
2019-09-03T20:42:21.220Z
2019-09-03T20:42:21.220Z
Jakob Nordstrom
<p>A full proof (based on superconcentrators) can be found in chapter 24 <em>"The pebble game"</em> of the book</p>

<blockquote>
  <p>Uwe Schöning and Randall Pruim:<br>
  Gems of Theoretical Computer Science<br>
  Springer, 1998  </p>
  
  <p>ISBN 978-3-642-64352-1<br>
  <a href="https://link.springer.com/book/10.1007%2F978-3-642-60322-8" rel="noreferrer">https://link.springer.com/book/10.1007%2F978-3-642-60322-8</a></p>
</blockquote>

CC BY-SA 4.0
2019-08-28T14:04:36.767Z
As this answers my question, I will accept this answer. However, it would be nice to see a different source for those who don’t want to spend $30.
exfret
CC BY-SA 4.0
2019-09-01T05:20:31.707Z
Looks like the publishers of the book are fans of SETCS, they just raised the price to $109.00   ouch !  :-)
William Hird
CC BY-SA 4.0
2019-09-03T17:18:54.433Z
@WilliamHird I think that was the case before. I was referring to the price of the specific chapter referenced in the answer. That being said, someone wanting context for said chapter would indeed have to cough up the whole price!
exfret
CC BY-SA 4.0
2019-09-03T17:20:17.280Z
Also, for those whose universities don't subscribe to Springer and who don't wish to spend the money, I would recommend looking up "expander graphs". These seem to be canonical examples of "hard to pebble" graphs.
exfret
CC BY-SA 4.0
2019-08-28T13:55:43.090Z
2019-08-28T13:55:43.090Z
Gamow
<p>Out of curiosity, I tried finding the original paper showing that there are graphs that require <span class="math-container">$n/\log n$</span> pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (Which you can access here: <a href="http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/p332-hopcroft.pdf" rel="noreferrer">http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/p332-hopcroft.pdf</a>).</p>

<p>Sadly, this result is cited as “personal communication,” and any other lower bounds I could find use the different definition of pebbling in graph theory. Does anyone know where I could find a construction of a graph requiring <span class="math-container">$n/\log n$</span> pebbles?</p>

<cc.complexity-theory><graph-theory><space-time-tradeoff>
Lower bound on pebbling numbers
exfret
# Lower bound on pebbling numbers

(Asked by: username_0 on 2019-08-28)

Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (Which you can access here: <http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/p332-hopcroft.pdf>).

Sadly, this result is cited as “personal communication,” and any other lower bounds I could find use the different definition of pebbling in graph theory. Does anyone know where I could find a construction of a graph requiring $n/\log n$ pebbles?

**Tags:** cc.complexity-theory, graph-theory, space-time-tradeoff


---

## 2 answers

### Answer by username_2 on 2019-08-28. Score: 9 | Accepted answer

A full proof (based on superconcentrators) can be found in chapter 24 *"The pebble game"* of the book

> Uwe Schöning and Randall Pruim:  
> Gems of Theoretical Computer Science  
> Springer, 1998
>
> ISBN 978-3-642-64352-1  
> <https://link.springer.com/book/10.1007%2F978-3-642-60322-8>

> **Comments:**
> **username_0**: As this answers my question, I will accept this answer. However, it would be nice to see a different source for those who don’t want to spend $30.  
> **username_3**: Looks like the publishers of the book are fans of SETCS, they just raised the price to $109.00   ouch !  :-)  
> **username_0**: @WilliamHird I think that was the case before. I was referring to the price of the specific chapter referenced in the answer. That being said, someone wanting context for said chapter would indeed have to cough up the whole price!  
> **username_0**: Also, for those whose universities don't subscribe to Springer and who don't wish to spend the money, I would recommend looking up "expander graphs". These seem to be canonical examples of "hard to pebble" graphs.  

---

### Answer by username_1 on 2019-09-03. Score: 6

Not sure whether I am missing something, but...

The Omega(n/log n) lower bound is from:

[PTC77] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10:239–251, 1977.

There is a strengthening of this to a non-deterministic version of the pebble game (so-called black-white pebbling) in:

[GT78] John R. Gilbert and Robert Endre Tarjan. Variations of a pebble game on graphs. Technical Report STAN-CS-78-661, Stanford University, 1978. Available at <http://infolab.stanford.edu/TR/CS-TR-78-661.html> .

And --- self-plug warning --- you find a somewhat careful exposition of the latter lower bound, together with some nice illustrations, in the survey <http://www.csc.kth.se/~jakobn/research/PebblingSurveyTMP.pdf> (see Section 7 starting on page 51).

Another good source on some classic pebbling stuff is Chapter 10 of:

[Sav98] John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley,1998. Available at <http://www.modelsofcomputation.org> .

> **Comments:**
> **username_0**: This is so perfect! Thank you!  

---

