Pith. sign in

REVIEW 1 cited by

Equations in oligomorphic clones and the Constraint Satisfaction Problem for $\omega$-categorical structures

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1612.07551 v3 pith:ZXDFYM2O submitted 2016-12-22 cs.LO math.LO

classification cs.LOmath.LO
keywords structureequivalentidentitieslinearmodel-completenon-trivialclonecore
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain non-trivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being non-trivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that $\omega$-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking a different approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a non-trivial system of linear identities, and obtain non-trivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every $\omega$-categorical structure is homomorphically equivalent to a model-complete core.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms

    math.RA 2025-07 conditional novelty 7.0 of 10

    Every finite relation algebra with at most four atoms has a network satisfaction problem that is either in P or NP-hard, with the paper determining which.

Pith tools