Equations in oligomorphic clones and the constraint satisfaction problem for omega-categorical structures

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10401295" target="_blank" >RIV/00216208:11320/19:10401295 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=nZU-WdxTTT" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=nZU-WdxTTT</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1142/S0219061319500107" target="_blank" >10.1142/S0219061319500107</a>

Result language

angličtina

Original language name

Equations in oligomorphic clones and the constraint satisfaction problem for omega-categorical structures

Original language description

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 nontrivial 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 nontrivial. 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 another 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 nontrivial system of linear identities, and obtain nontrivial 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

<a href="/en/project/GA13-01832S" target="_blank" >GA13-01832S: General algebra and its connections to computer science</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Mathematical Logic

ISSN

0219-0613

e-ISSN

—

Volume of the periodical

19

Issue of the periodical within the volume

2

Country of publishing house

SG - SINGAPORE

Number of pages

31

Pages from-to

1950010

UT code for WoS article

000488865700005

EID of the result in the Scopus database

2-s2.0-85066098751