Polynomial-time homomorphism-embedding CSPs for homogeneous Ramsey structures
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.
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
Sign in to submit a solution.
No solutions have been posted yet.