Random graphs have the smallest complete miners among all graphs of given o
rder and density. We show that, unlike random graphs, many well-known examp
les of pseudorandom graphs (such as Paley graphs) have very large miners. (
C) 2000 John Wiley & Sons, Inc.