# 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?

• Sorry, no good suggestions here. I am thinking of finite topologies, combinatorial designs, and enumeration of such structures. From a universal algebraic perspective, you are looking for special antichains in the lattice of equivalence relations on a finite set, in that exactly one member of the chain is over (greater than) any particular minimal member of the lattice (your C in P condition). However I do not know who in order theory has considered this. Gerhard "Not Quite Over My Head" Paseman, 2018.05.28. – Gerhard Paseman May 28 '18 at 17:42
• Note that for any klatsch K, if it does not have the discrete partition D in it, you can add D to preserve the condition. Apart from D, your condition induces a partition of the two element sets of A, so that there are at most A choose 2 many members of K that are not D, and much fewer if any member of K contains a large subset of (so lots of pairs from) A. It looks like a generalized tournament design. Gerhard "Sort Of Like Board-Gaming Night" Paseman, 2018.05.28. – Gerhard Paseman May 28 '18 at 17:48
• My best guess is enumeration of combinatorial structures. Based on the previous comment (that enumerating klatsches would solve some tournament design problems), I guess that there are many people who would like to have had such an algorithm in the past. Gerhard "Many May Still Want One" Paseman, 2018.05.28. – Gerhard Paseman May 28 '18 at 17:58
• Could you please clarify: you write that there is a single klatsch on three elements, but adding the discrete partition would produce another one. Are you excluding the discrete partition? – Martin Rubey May 28 '18 at 19:01
• You might like to check out Brendan McKay's papers on "isomorph-free exhaustive generation"; also go backward from there (especially Read and Faradzev) and forward (because I don't know what's more recent). If it leads you towards the "nauty" graph-labelling software (as it might), then make sure that you follow links to the most recent version, a collaboration with Adolfo Piperno (pallini.di.uniroma1.it). It's a very interesting area, though not easy. – Ed Wynn May 29 '18 at 6:51