I’m trying to analyze the space complexity of using the coloring function $f$ which appears in “Colorful Triangle Counting and a MapReduce Implementation”, Pagh and Tsourakakis, 2011, https://arxiv.org/abs/1103.6073.

As far as I understand, $f:(n) rightarrow (N)$ is a hash function, that should be picked uniformly at random out of a pairwise independent hash functions family $H$. I have a few general questions:

- Does the space complexity required by $f$ is affected by the fact that $H$ is $k$-wise independent? Why? (If it does, then also- how?)
- What do we know about $|H|$? What if $H$ is $k$-wise independent?
- Is there a more space-efficient way to store $f$ than storing an $N times m$ matrix that maps each vertex to its color, using O($N m$) storage words?
- Does the total space complexity which is required in order to use $f$ as described in the paper is $|H| cdot O(text{space complexity of } f)$?

Best regards