Polynomial-time homomorphism-embedding CSPs for homogeneous Ramsey structures

About 1 year old · traced to

Let \strM\str M be a homogeneous Ramsey structure in a finite relational language. A homomorphism-embedding is a map that is a homomorphism and restricts to an embedding on every irreducible substructure; the corresponding homomorphism-embedding constraint satisfaction problem asks whether such a map exists from the finite input structure to the target.

Homomorphism-embedding CSP conjecture. There is a homogeneous Ramsey structure \strH\str H in a finite relational language, first-order bi-interpretable with \strM\str M, such that the homomorphism-embedding variant of the constraint satisfaction problem of \strH\str H is solvable in polynomial time.

The conjecture formalizes the observation that known Ramsey classes often admit polynomial-time algorithms through completion methods. The source presents it as open.

References

Primary source

Jan Hubička and Matěj Konečný, “Twenty years of Nešetřil's classification programme of Ramsey classes”, arXiv:2501.17293 (2025).

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.