## Monday, July 07, 2008

### Density of a regular pair is the average density of sub-pairs

$\{A_j\mid 1\leq j\leq l\}, \{B_j'\mid 1\leq j'\leq l\}$

$|A_1|=|A_2|=\ldots=|A_l|, \; |B_1|=|B_2|=\ldots=|B_l|$

$\sum\limits_{1\leq j,j'\leq l}d(A_j,B_{j'}) = \frac{\sum\limits_{1\leq j,j'\leq l}e(A_j,B_{j'})}{|A_1|\cdot |B_1|}$ .................... (*)

$d(A,B)=\frac{e(A,B)}{|A|\cdot |B|} = \frac{\sum\limits_{1\leq j,j'\leq l}e(A_j,B_{j'})}{|A|\cdot |B|}\\ = (*)\cdot\frac{|A_1|\cdot |B_1|}{|A|\cdot|B|}\\ =
\frac{\sum\limits_{1\leq j,j'\leq l}d(A_j,B_{j'})}{l^2}$

Theorem: Given a bipartite graph with classes A and B, then for all integers k < |A| and l < |B|, we have

$d(A,B) = \frac{\sum\limits_{X\subset A, Y\subset B,\\ |X| = k, |Y|=l} \quad d(X,Y)}{{|A|\choose k}{|B|\choose l}}$