Lower bound on pebbling numbers 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?
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