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