We are given universe ${1,...,n}$ and all its $r$-sized subsets. I want to find a family of bijections $\phi_{A,B}:A\mapsto B$ between every two $r$-sized subsets $A,B$, with the following property:

0) mappings are symmetric, i.e., $\phi_{B,A}$ is just reversed $\phi_{A,B}$,

1) for any two subsets $A,B$, if $e \in A \cap B$, then $\phi_{A,B}(e) = e$,

2) for any three subsets $A,B,C$ and $a\in A, b\in B, c\in C$, if $\phi_{C,A}(c) = a$ and $\phi_{C,B}(c) = b$, then $\phi_{A,B}(a) = b$.

It would be really easy to construct such a family if we would waive property 1 --- then just order all subsets in some arbitrary way, and map to each other all elements of the same number in the subset. Question is can we still have this transitivity property 2, if we insist on 1.

  • $\begingroup$ Ok, it's not true. With $n=4$ and $r=2$, after drawing all required from property 1 maps between intersecting subsets, one gets a beef with a mapping for $\{1,2\},\{3,4\}$, it cannot be $1 ~ 3$, because then pair $(\{3,4\},3)$ conflicts pair $(\{2,4\},4)$. By similar reason $1~4$ is not possible due to $\{2,3\}$ $\endgroup$ – Marek Adamczyk Sep 7 '15 at 12:24

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.