I'm reading Alon and Spencers' "The probabilistic method". Chapter 9 is about Pseudorandomness and quasirandom graphs. For the following you do not have to know, what a Paleygraph is. :)
I have some properties which are all equivalent and I want to show, that Paleygraphs are quasirandom by the Property (P1):
$\sum \limits_{u,v \in V}$||N(u) $\cap$ N(v)|-$\frac{n}{4}$|=o($n^3$)
I have shown, that there are $\frac{p-3}{2}$ vertices y, so that (v,y) and (u,y) are either both edges or none of them is an edge. p is the number of vertices of my Paleygraph; it is $\frac{p-1}{2}$-regular. How can I show, that the property is satisfied?
In other books there was this property (P2): $\sum \limits_{u,v \in V}$|s(v,u)-$\frac{n}{2}$|=o($n^3$), where s(v,u) is the number of so that (v,y) and (u,y) are either both edges or none of them is an edge.
With property (P2) it is quite easy to show that the property is satisfied by Paleygraphs, but how can I do this by (P1)? Aloud the book the $\frac{p-1}{2}$-regualrity is needed.
Thank you very much for your help!