Polynomial-time homomorphism-embedding CSPs for homogeneous Ramsey structures
Let 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 in a finite relational language, first-order bi-interpretable with , such that the homomorphism-embedding variant of the constraint satisfaction problem of 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
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.