Loop conditions for strongly connected digraphs. (English) Zbl 1454.08006
Summary: We prove that every strongly connected (not necessarily finite) digraph of algebraic length 1, which is compatible with an operation \(t\) satisfying a non-trivial identity of the form \(t(\dots)\approx t(\dots)\), has a loop.
MSC:
| 08B05 | Equational logic, Mal’tsev conditions |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 08B20 | Free algebras |
| 08A70 | Applications of universal algebra in computer science |
References:
| [1] | Barto, L. and Kozik, M., Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Log. Methods Comput. Sci.8(1) (2012). · Zbl 1239.08002 |
| [2] | Barto, L. and Kozik, M., Absorption in universal algebra and CSP, in The Constraint Satisfaction Problem: Complexity and Approximability, eds. Krokhin, A. and Zivny, S., , Vol. 7 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, 2017), pp. 45-77. · Zbl 1482.68160 |
| [3] | Barto, L., Kozik, M., and Niven, T., The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Comput.38(5) (2008/09) 1782-1802. · Zbl 1191.68460 |
| [4] | Barto, L., Krokhin, A. and Willard, R., Polymorphisms, and how to use them, in The Constraint Satisfaction Problem: Complexity and Approximability, eds. Krokhin, A. and Zivny, S., , Vol. 7 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, 2017), pp. 1-44. · Zbl 1482.68161 |
| [5] | Barto, L. and Pinsker, M., The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, in Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science, , New York, NY, USA, , 2016 (ACM, 2016), pp. 615-622. · Zbl 1401.68108 |
| [6] | Bergman, C., Universal Algebra: Fundamentals and Selected Topics, , Vol. 301 (CRC Press, Boca Raton, FL, 2012). · Zbl 1229.08001 |
| [7] | Bergman, C., Maddux, R. D. and Pigozzi, D. (eds), Algebraic Logic and Universal Algebra in Computer Science, Conference, Ames, Iowa, USA, June 1-4, 1988, Proceedings, , Vol. 425 (Springer, 1990). · Zbl 0779.00012 |
| [8] | Bodirsky, M., Constraint satisfaction problems with infinite templates, in Complexity of Constraints (A Collection of Survey Articles), ed. Vollmer, H., , Vol. 5250 (Springer, 2008), pp. 196-228. · Zbl 1171.03320 |
| [9] | Bulatov, A., \(H\)-coloring dichotomy revisited, Theoret. Comput. Sci.349(1) (2005) 31-39. · Zbl 1086.68052 |
| [10] | Bulatov, A., A dichotomy theorem for nonuniform CSPs, in 2017 IEEE 58th Annual Symp. Foundations of Computer Science (FOCS) (Berkeley, California, 2017), pp. 319-330. |
| [11] | Bulatov, A., Jeavons, P. and Krokhin, A., Classifying the complexity of constraints using finite algebras, SIAM J. Comput.34(3) (2005) 720-742. · Zbl 1071.08002 |
| [12] | Feder, T. and Vardi, M., The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput.28 (1998) 57-104. · Zbl 0914.68075 |
| [13] | P. Gillibert, J. Jonušas and M. Pinsker, Pseudo-loop conditions, preprint (2018), arXiv:1812.00396. |
| [14] | Hell, P. and Nešetřil, J., On the complexity of \(H\)-coloring, J. Combin. Theory Ser. B48(1) (1990) 92-110. · Zbl 0639.05023 |
| [15] | Hobby, D. and McKenzie, R., The Structure of Finite Algebras, (American Mathematical Society, 1988). · Zbl 0721.08001 |
| [16] | A. Kazda, Taylor term does not imply any nontrivial linear one-equality Maltsev condition, preprint (2017), arXiv:1409.4601. · Zbl 1472.08007 |
| [17] | Kearnes, K. A. and Kiss, E., The Shape of Congruence Lattices, Vol. 1046 (American Mathematical Society, Providence, RI, 2013). · Zbl 1294.08002 |
| [18] | Kearnes, K., Marković, P. and McKenzie, R., Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties, Algebra Universalis72(1) (2014) 91-100. · Zbl 1305.08008 |
| [19] | Kiss, E. W., An Introduction to Tame Congruence Theory (Springer Netherlands, Dordrecht, 1997), pp. 119-143. · Zbl 0879.08001 |
| [20] | Maltsev, A., On the general theory of algebraic systems, Mat. Sb.77 (1954) 3-20. · Zbl 0057.02403 |
| [21] | M. Olšák, Loop conditions, preprint (2017), arXiv:1701.00260. · Zbl 1528.08009 |
| [22] | Olšák, M., The weakest nontrivial idempotent equations, Bull. London Math. Soc.49(6) (2017) 1028-1047. · Zbl 1414.08002 |
| [23] | Siggers, M. H., A strong Mal’cev condition for locally finite varieties omitting the unary type, Algebra Universalis64(1-2) (2010) 15-20. · Zbl 1216.08002 |
| [24] | Taylor, W., Some very weak identities, Algebra Universalis25(1) (1988) 27-35. · Zbl 0646.08004 |
| [25] | Zhuk, D., A proof of CSP dichotomy conjecture, in 2017 IEEE 58th Annual Symp. Foundations of Computer Science (FOCS) (Berkeley, California, 2017), pp. 331-342. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
