sets of partitions associating any two elements exactly once

Question

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?

Answer 1

There may be a clever way to organize the work that will seem efficient. However, this strikes me as bordering on some hard problems both in computer science and in combinatorial enumeration. I make some observations below which seem to me to be fundamental in approaching the problem.

Since D, the discrete partition, can be added to or removed from K (my abbreviation for a klatsch) without affecting the key property, I will leave it out of the rest of the discussion. Now let us consider every other member P of K. If A is thought of as a complete graph, each non singleton member S of P can be thought of as a clique consisting of each edge with vertices in S. Your condition is that the non singleton members of all P in K form a partition of the edges of A. However, it is not just any partition of the edges of A, but a clique-partition. In particular, if a set S in some P has the edge ab in it, and the edge ac, then S also has the edge bc.

So one strategy towards forming K starts with a clique partition of A2, the edges of A. Other than brute force, I have no suggestions about enumerating clique partitions of A2. It should be clear though that isomorphic instances of K have isomorphic instances of a clique partition.

However, the enumeration does not stop there. Suppose you have two subsets of A, call them B and C, which are disjoint. Further, suppose B2 and C2 participate in a clique partition of A2. You can choose to put both B and C in one partition P of K, or keep them in different partitions. Thus for the subsets Bi associated to the members Bi2 of the clique partition A2, you get to decide whether disjoint Bi and Bj belong to the same or to different P in K. This is a kind of packing problem since you have to decide how to pack the different pieces into different bags. Again, nothing more than straightforward "try all possibilities" seems to suggest itself. The result may not take doubly exponential time (2^(2^n)), but I can see it being (2^(n^2)) time .

Gerhard "Looks Like A Long Project" Paseman, 2018.05.28.