Pseudorandom Graphs

Tibor Szabó

Institute of Mathematics
Freie Universität Berlin

On the informal level, a graph is called pseudorandom if it resembles truly random graphs in some sense. What exactly this "some sense" is could be up for debate, but as it turns out a number of meaningful random-like properties are equivalent (see the works of Thomason and Chung, Graham and Wilson.)
One of the ways to measure randomness of a d-regular graph G is the so-called eigenvalue gap, i.e. how small the second eigenvalue of the adjacency matrix of G is compared to d. This is the approach considered in some of the following papers.
A very useful approach in proving graph theoretic statements for random graphs is to isolate appropriate pseudorandom properties which (1) hold for the random graph in question and (2) imply the graph theoretic statement in question.

Valid HTML 4.0! Last modified: Sun Jun 30 22:52:46 CEST 2013