Skip to main content

Research Repository

Advanced Search

ω-categorical structures avoiding height 1 identities

Bodirsky, Manuel; Mottet, Antoine; Olšák, Miroslav; Opršal, Jakub; Pinsker, Michael; Willard, Ross

ω-categorical structures avoiding height 1 identities Thumbnail


Manuel Bodirsky

Antoine Mottet

Miroslav Olšák

Jakub Opršal

Michael Pinsker

Ross Willard


The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.


Bodirsky, M., Mottet, A., Olšák, M., Opršal, J., Pinsker, M., & Willard, R. (2021). ω-categorical structures avoiding height 1 identities. Transactions of the American Mathematical Society, 374(1), 327-350.

Journal Article Type Article
Online Publication Date Oct 14, 2020
Publication Date 2021
Deposit Date Sep 14, 2020
Publicly Available Date Jun 30, 2021
Journal Transactions of the American Mathematical Society
Print ISSN 0002-9947
Electronic ISSN 0002-9947
Publisher American Mathematical Society
Peer Reviewed Peer Reviewed
Volume 374
Issue 1
Pages 327-350
Related Public URLs


You might also like

Downloadable Citations