Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

$\omega$-categorical structures avoiding height 1 identities
HTML articles powered by AMS MathViewer

by Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Jakub Opršal, Michael Pinsker and Ross Willard PDF
Trans. Amer. Math. Soc. 374 (2021), 327-350 Request permission

Abstract:

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 $\omega$-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

References
Similar Articles
Additional Information
  • Manuel Bodirsky
  • Affiliation: Institute of Algebra, Technische Universität Dresden, Dresden, Germany
  • MR Author ID: 693478
  • ORCID: 0000-0001-8228-3611
  • Email: manuel.bodirsky@tu-dresden.de
  • Antoine Mottet
  • Affiliation: Department of Algebra, Charles University in Prague, Czech Republic
  • MR Author ID: 1135698
  • ORCID: 0000-0002-3517-1745
  • Email: mottet@karlin.mff.cuni.cz
  • Miroslav Olšák
  • Affiliation: Department of Algebra, Charles University in Prague, Czech Republic
  • ORCID: 0000-0002-9361-1921
  • Email: mirek@olsak.net
  • Jakub Opršal
  • Affiliation: Department of Computer Science, Durham University, Durham, United Kingdom
  • MR Author ID: 1104311
  • ORCID: 0000-0003-1245-3456
  • Email: jakub.oprsal@durham.ac.uk
  • Michael Pinsker
  • Affiliation: Institute of Discrete Mathematics and Geometry, Technische Universität Wien, Austria; and Department of Algebra, Charles University in Prague, Czech Republic
  • MR Author ID: 742015
  • ORCID: 0000-0002-4727-918X
  • Email: marula@gmx.at
  • Ross Willard
  • Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada
  • MR Author ID: 183075
  • ORCID: 0000-0002-3297-0453
  • Email: ross.willard@uwaterloo.ca
  • Received by editor(s): February 5, 2020
  • Received by editor(s) in revised form: April 7, 2020
  • Published electronically: October 14, 2020
  • Additional Notes: The first and fourth authors were supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No 681988, CSP-Infinity).
    The second author received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No 771005, CoCoSym).
    The third and fifth authors received funding from the Czech Science Foundation (grant No 13-01832S)
    The fourth author also received funding from the UK EPSRC (grant No EP/R034516/1).
    The fifth author received funding from the Austrian Science Fund (FWF) through project No P32337.
    The sixth author was supported by the Natural Sciences and Engineering Research Council of Canada.
    A conference version of this material appeared at the Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2019 \cite{TopologyIsRelevant}.
  • © Copyright 2020 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 374 (2021), 327-350
  • MSC (2010): Primary 08B05, 03C05, 08A70; Secondary 03C10, 03D15
  • DOI: https://doi.org/10.1090/tran/8179
  • MathSciNet review: 4188185