4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 28 '18 at 17:42
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 28 '18 at 17:48
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 28 '18 at 17:58
  • $\begingroup$ 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? $\endgroup$ – Martin Rubey May 28 '18 at 19:01
  • $\begingroup$ 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. $\endgroup$ – Ed Wynn May 29 '18 at 6:51
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This setup also generalizes partitioning a complete graph into disjoint matchings, or disjoint unions of triangles. I suggest seeing if there are algorithms to generate these special K, and see if citing literature does any thing more. Gerhard "Is Not Talking Breakfast Cereal" Paseman, 2018.05.28. $\endgroup$ – Gerhard Paseman May 28 '18 at 18:40
  • $\begingroup$ Thank you for your advice. I neglected to consider that the discrete partition can be added to any klatsch without invalidating the conditions, so my example is wrong in that there are actually two of them on a three element set up to isomorphism. (I ran into to this problem when trying to design asynchronous arbiter mesh networks, where the discrete partition would correspond to a layer that doesn't do anything.) $\endgroup$ – Lisa Vibbert May 30 '18 at 16:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.