Communication complexity example problem Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$.
G and H are isomorphic if there is a bijection f : V -> W such that:
$\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$
Considering the complexity class $ISO_{n}$ where Alice is given a graph G, Bob given graph H and they must decide if G and H are isomorphic.
How do you show that $D(ISO_{n}) \geq \Omega(n^{2})$
 A: First, let's consider a simpler problem; Alice and Bob are both given $n$-bit binary strings, and they must decide whether the two strings are the same. Let's call this problem $EQ_n$. It's a classical result in communication complexity that $D(EQ_n) \geq \Omega(n)$ (in fact, $D(EQ_n) = n$); you can see a proof here: http://en.wikipedia.org/wiki/Communication_complexity#Example:_EQ. More generally, if Alice and Bob both have elements of a set $S$ with size $|S| = 2^c$, deciding whether their elements are equal has deterministic communication complexity at least $c$ (you can biject elements in $S$ to $c$-bit strings).
Now let's consider the problem $ISO_n$. The first thing to notice is that $ISO_n$ is exactly the same problem as $EQ_n$, except instead of testing equality over the space of all $2^{n}$-bit long strings, Alice and Bob are testing equality over the space of all graphs up to isomorphism on $n$ vertices. How many such distinct graphs are there? Well, if we ignore isomorphism there are $2^{\binom{n}{2}}$ distinct graphs, and since each graph is isomorphic to at most $n!$ other graphs, there are at least $\frac{1}{n!}2^{\binom{n}{2}}$ different graphs up to isomorphism. This means that representing one such graph requires at least $\log\left(\frac{1}{n!}2^{\binom{n}{2}}\right) = \binom{n}{2} - \log n! = \frac{n^2}{2} - O(n\log n) = \Omega(n^2)$ bits. It follows that $D(ISO_n) = \Omega(n^2)$, as desired.
(This in fact shows that $D(ISO_n) = \Theta(n^2)$. Also, it should be noted that while there exists such a communication protocol, there's no guarantee that it is efficient for Alice or Bob to perform (and indeed, if we knew how to do this efficiently we would have an efficient algorithm for graph isomorphism)). 
