9
$\begingroup$

Suppose I want a necklace with $n$ beads labelled (bijectively) by $\{1, 2, \ldots n\}$, that is I want a cyclic order on $\{1, 2, \ldots, n\}$ (so for example $132$ is the same cyclic order as $321$ but different from $231$). Now suppose I know the cyclic order of some subsets of $\{1, 2, \ldots, n\}$ as they should appear in the necklace. I want to know what conditions on the subsets and their cyclic orders would make the necklace uniquely reconstructible, or given a set of subsets with orders how many compatible necklaces there are.

I feel like surely this is well studied (somewhere in the world of reconstructibility or elsewhere), but I'm not managing to find any results on it, so perhaps you can help me find where people have looked at this.

Thanks.

$\endgroup$
  • $\begingroup$ Are the subsets allowed to intersect? Or interleave? $\endgroup$ – მამუკა ჯიბლაძე Sep 26 '17 at 17:12
  • $\begingroup$ Does cyclic order come with direction? E.g., would cyclic orders 132 and 231 be considered the same? $\endgroup$ – Max Alekseyev Sep 27 '17 at 0:08
  • $\begingroup$ Yes, 132 and 231 are different (hence "necklace", but these things are not as standard as they might be, so I will clarify in the question). $\endgroup$ – Karen Yeats Sep 27 '17 at 18:32
  • $\begingroup$ In the application I have in mind the subsets would typically intersect and could potentially interleave. $\endgroup$ – Karen Yeats Sep 27 '17 at 18:36
2
$\begingroup$

This problem is NP-complete, thus there is no easily verifiable condition that would be necessary and sufficient. In fact, it is enough if only some of the triples are prescribed, see Cyclic ordering is NP-complete by Galil and Megiddo. Another, closely related problem is Betweenness.

$\endgroup$
  • $\begingroup$ Are there any special cases of the problem that people have studied that are better behaved? Say if my subsets are guaranteed to have some special properties? In the application I have in mind they would be triples, but if there are further conditions that would make the problem easy that could be very interesting when translated back into conditions for niceness in the original application. $\endgroup$ – Karen Yeats Sep 29 '17 at 13:36
  • $\begingroup$ Also, if I have as a hypothesis that there is a consistent order, but then want to know something about all the consistent orders (how many or construct them), does that end up being any easier? $\endgroup$ – Karen Yeats Sep 29 '17 at 13:41
  • $\begingroup$ @Karen I don't know anything about your first question, but knowing that there exists a consistent order certainly won't help. If it did, then you could "pretend" to know that there is one, and use your algorithm to count/construct (a) consistent order(s). If your "pretence" was false, you would run into a contradiction, so eventually you could turn this into an algorithm to decide whether there's a consistent order or not. $\endgroup$ – domotorp Sep 29 '17 at 19:14

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.