Complete minors in pseudorandom graphs

Authors
Thomason, A
Citation
A. Thomason, Complete minors in pseudorandom graphs, RAND STR AL, 17(1), 2000, pp. 26-28
Citations number
12
Categorie Soggetti
Mathematics
Journal title
RANDOM STRUCTURES & ALGORITHMS
ISSN journal
10429832 → ACNP
Volume
17
Issue
1
Year of publication
2000
Pages
26 - 28
Database
ISI
SICI code
1042-9832(200008)17:1<26:CMIPG>2.0.ZU;2-N
Abstract
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.