# Pseudorandom clique-free graphs

Anurag Bishnoi wrote a post about a recently finished preprint on pseudorandom clique-free graphs written by me, Anurag, and Valentina Pepe. We (slightly) improve a construction by Alon and Krivelevich from 1997.

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 \$latex G(n, p)\$, with \$latex p = p(n) leq 0.99\$, a direct application of Chernoff bound implies that the probability of the following event approaches \$latex 1\$ as \$latex n\$ approaches infinity:

\$latex |e(S, T) – p|S||T|| = O(sqrt{pn |S||T|}\$

where \$latex S,T\$ are arbitrary subsets of vertices and \$latex e(S,T)\$ denotes the number of edges with one end vertex in \$latex S\$ and the other one in \$latex T\$.  Note that \$latex p|S||T|\$ is the expected number of edges between \$latex S\$ and \$latex T\$ in this model, and \$latex sqrt{p(1 – p)|S||T|}\$ is the standard deviation. Now let \$latex G\$ be a \$latex d\$-regular graph on \$latex n\$-vertices and let \$latex lambda\$ be the second largest…

View original post 804 more words