A classic textbook example for communication complexity is when A and B both receive a subtree of a an $n$-node tree (that they both know), and they need to output whether their subtrees are disjoint or not. The textbook solution usually gives an algorithm with $2\log_2 n$ bits of communication. In Lovasz-Saks, however, there is a better algorithm, with $\log_2 n+\log_2 \log_2 n$ bits of communication. Where is the truth between this and the trivial $\log_2 n$ lower bound?
A natural idea is to consider the rank of the communication matrix, but this is $2n-1$ for any tree; the vertices and edges generate every subtree.