Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Varieties with few subalgebras of powers


Authors: Joel Berman, Paweł Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote and Ross Willard
Journal: Trans. Amer. Math. Soc. 362 (2010), 1445-1473
MSC (2000): Primary 08B05, 08B10, 08A30, 08A70, 68Q25, 68Q32, 68W30
Published electronically: October 19, 2009
MathSciNet review: 2563736
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Constraint Satisfaction Problem Dichotomy Conjecture of Feder and Vardi (1999) has in the last 10 years been profitably reformulated as a conjecture about the set $ \sf {SP}_{\sf fin}(\mathbf{A})$ of subalgebras of finite Cartesian powers of a finite universal algebra $ \mathbf{A}$. One particular strategy, advanced by Dalmau in his doctoral thesis (2000), has confirmed the conjecture for a certain class of finite algebras $ \mathbf{A}$ which, among other things, have the property that the number of subalgebras of $ \mathbf{A}^n$ is bounded by an exponential polynomial. In this paper we characterize the finite algebras $ \mathbf{A}$ with this property, which we call having few subpowers, and develop a representation theory for the subpowers of algebras having few subpowers. Our characterization shows that algebras having few subpowers are the finite members of a newly discovered and surprisingly robust Maltsev class defined by the existence of a special term we call an edge term. We also prove some tight connections between the asymptotic behavior of the number of subalgebras of $ \mathbf{A}^n$ and some related functions on the one hand, and some standard algebraic properties of $ \mathbf{A}$ on the other hand. The theory developed here was applied to the Constraint Satisfaction Problem Dichotomy Conjecture, completing Dalmau's strategy.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 08B05, 08B10, 08A30, 08A70, 68Q25, 68Q32, 68W30

Retrieve articles in all journals with MSC (2000): 08B05, 08B10, 08A30, 08A70, 68Q25, 68Q32, 68W30


Additional Information

Joel Berman
Affiliation: Department of Mathematics, University of Illinois at Chicago, Chicago, Illinois 60607
Email: jberman@uic.edu

Paweł Idziak
Affiliation: Department of Theoretical Computer Science, Jagiellonian University, Kraków, Poland
Email: idziak@tcs.uj.edu.pl

Petar Markovic
Affiliation: Department of Mathematics and Informatics, University of Novi Sad, Serbia
Email: pera@im.ns.ac.yu

Ralph McKenzie
Affiliation: Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240
Email: mckenzie@math.vanderbilt.edu

Matthew Valeriote
Affiliation: Department of Mathematics, McMaster University, Hamilton, Ontario, Canada L8S 4K1
Email: matt@math.mcmaster.ca

Ross Willard
Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 2G1
Email: rdwillar@uwaterloo.ca

DOI: http://dx.doi.org/10.1090/S0002-9947-09-04874-0
PII: S 0002-9947(09)04874-0
Keywords: Maltsev condition, variety, constraint satisfaction problem
Received by editor(s): February 5, 2008
Published electronically: October 19, 2009
Additional Notes: The second author was supported by grant no. N206 2106 33 of the Polish Ministry of Science, the third author was supported by grant no. 144011G of the Ministry of Science and Environment of Serbia, the fourth author was supported by a grant from the US National Science Foundation, no. DMS-0245622, and the last two authors were supported by the NSERC of Canada.
Article copyright: © Copyright 2009 American Mathematical Society