# Space complexity of using a pairwise independent hash family

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:

1. 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?)
2. What do we know about $$|H|$$? What if $$H$$ is $$k$$-wise independent?
3. 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?
4. 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 storing } f)$$?

Best regards