Tag Archives: pseudorandom

Kopparty’s graph

Alon’s construction of optimal pseudorandom graphs from 1994 is useful for obtaining several interesting combinatorial results in various areas of mathematics, some of which are highlighted in this survey of Noga from last year (also see my previous post). In … Continue reading

Posted in Combinatorics, Extremal Combinatorics, Spectral Graph Theory | Tagged , , , , , | 3 Comments

Pseudorandom clique-free graphs

Pseudorandom graphs are graphs that in some way behaves like a random graph with the same edge density. One way in which this happens is as follows. In the random graph , with , a direct application of Chernoff bound … Continue reading

Posted in Combinatorics, Extremal Combinatorics, Spectral Graph Theory | Tagged , , | 5 Comments