1
$\begingroup$

Preface. I am reading up on the Chung-Graham-Wilson results on quasi-random graphs, and the description I'm reading is applying an apparently obvious usage of Cauchy-Schwarz that I'm just not seeing. The notes I'm following are here: http://terrytao.wordpress.com/2008/02/15/luca-trevisan-checking-the-quasirandomness-of-graphs-and-hypergraphs/

The problem. Consider a graph $G=(V,E)$, where $|V|=n$, and consider the edge-indicator function $A:V \times V \rightarrow \{0,1\}$ where $A(x,y)=1$ if there is an edge and $0$ otherwise. Now, apparently by Cauchy-Schwarz: $[\sum_{x,y} A(x,y) ]^2 \le n \sum_{x,y,z} A(x,y)A(x,z)$

Tricks I've played with for using C-S: $A(x,y) = A(x,y)*A(x,y)$, and also $A(x,y) = A(x,y)*1$.

I'd very much appreciate it if someone could show me the intermediate steps.

  • 0
    Wha$t$ a cool ar$t$icle!2012-10-26

1 Answers 1

2

The trick is to apply C-S only to the sum with respect to one of the variables, as follows: $ \begin{split}&\left(\sum_x \sum_y A(x,y)\right)^2 \le \left(\sum_x 1^2\right) \left[\sum_x \left(\sum_y A(x,y)\right)^2\right] \\&= n \sum_x \left(\sum_y A(x,y)\right) \left(\sum_z A(x,z)\right)= n \sum_{x,y,z} A(x,y) A(x,z)\end{split} $