Polynomial-time homomorphism-embedding CSPs for homogeneous Ramsey structures

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.