Wqo-based decidability conjecture for the joint embedding property

At least 1 year old · documented by

Let (F,≤)(\mathcal{F},\le) be a well-quasi-order (wqo), and suppose there are algorithms for basic problems related to ≤\le, including deciding whether X≤YX\le Y and, given XX, finding all ZZ such that X≤ZX\le Z and there is no YY with X≤Y≤ZX\le Y\le Z other than XX and ZZ. For a finite set S⊆FS\subseteq\mathcal{F}, write Forb⁡≤(S)\operatorname{Forb}_\le(S) for the objects containing no member of SS under ≤\le. Wqo-based JEP conjecture. Under these assumptions, it should be decidable whether Forb⁡≤(S)\operatorname{Forb}_\le(S) has the joint embedding property (JEP). The conjecture is motivated by the possibility of extending the tree-automaton proof from wqo families of trees to more general wqo families, but the paper gives very low confidence in it and leaves the necessary additional assumptions unclear.

References

Primary source

Daniel Carter, “On the joint embedding property for cographs and trees”, arXiv:2409.06127 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.