Skip to main content
edited tags
Link
Asaf Karagila
  • 39.8k
  • 8
  • 135
  • 283
Source Link

sets of partitions associating any two elements exactly once

There may be a theory that deals with problems like this but I'm not enough of a mathematician to know what it is. So far I've looked up braid groups, block design, and the recommended related posts to this one but the penny hasn't dropped yet.

Let's say I'm trying to organize a speed dating event for androgynous aliens whose "couples" can have arbitrarily many members. Suppose I call a set $K$ of partitions on a finite set $A$ of aliens a "klatsch" over $A$ if and only if for any distinct $a,b\in A$ there is a partition $P\in K$ containing exactly one class $C\in P$ containing both $a$ and $b$, and no such class in any other partition in $K$. For example, the set of three partitions $K=\{\{\{a,b\},\{c,d\}\},\{\{a,d\},\{b,c\}\},\{\{a,c\},\{b,d\}\}\}$ is a klatsch over $\{a,b,c,d\}$.

If two klatsches over $A$ are considered isomorphic to each other whenever a bijection from $A$ to $A$ transforms one to the other, then $\{\{\{a\},\{b,c\}\},\{\{b\},\{a,c\}\},\{\{c\},\{a,b\}\}\}$ is the only klatsch over a three element set up to isomorphism. My best efforts at an exhaustive search indicate 5 klatsches over a 4 element set up to isomorphism (of which one involves a triple), 18 over a 5 element set, 130 over a 6 element set, and so on. Is there an efficient algorithm for generating all klatsches over a given set up to isomporphism?