I wonder whether there is a simple algorithm to do this work:

Say I have a collection of objects $C$, and a binary relation $R: C\times C$ that is auto-reflective ($\forall c\in C: c R c$) , and symmetric ($\forall b,c\in C: b R c \implies c R b$). The relation is not necessarily transitive.

I want to find an integer function $$h: C\rightarrow \text{Integer}$$ so that $$\forall b,c\in C: h(b)\neq h(c) \implies R(b,c) $$

Example: Let $$C=\{1,2,3\}$$ $$R=\{(1,1), (2,2), (3,3), (1,2), (1,3), (2,1), (2,3)\}$$ $$h_1 = \{1\rightarrow 5, 2\rightarrow 6, 3\rightarrow 7\}$$ $$h_2 = \{1\rightarrow 5, 2\rightarrow 7, 3\rightarrow 7\}$$ then $h_2$ is a correct answer. $h_1$ is not, because $h_1(2)\neq h(3)$ yet $R(2,3)$ does not hold.

More concretely, my question comes from the following real concern: I have a collection of sets $C$, between some of them being disjoint. I want to find a hash function $h$ that is able to distinguish the sets by their disjointness, so that for any sets $b,c$ of $C$ belonging to different hash buckets, I can conclude that they are disjoint. This is motivating because the underlined $C$ may have a huge cardinal.

  • 2
    $\begingroup$ Use a constant function. $\endgroup$ – Yuval Filmus Sep 9 '12 at 14:34
  • $\begingroup$ Yes. That works. However, as the background here is to find a hash function, and it is known that constant function is a very bad hash function. It would be more interesting to have a hash function that, informally, "differs whenever it can, but are equal whenever it has to be". $\endgroup$ – zell Sep 9 '12 at 18:32
  • $\begingroup$ Is the collection of set fixed once and for all, or does it evolve? If it evolves, how (insertions, deletions, unions, splits, …)? How often do you have sets that are neither disjoint nor equal? $\endgroup$ – Gilles 'SO- stop being evil' Sep 25 '12 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.