×

Rigid binary relations on a 4-element domain. (English) Zbl 1405.08001

Summary: An \(n\)-ary relation \(\rho\) on a set \(U\) is strongly rigid if it is preserved only by trivial operations. It is projective if the only idempotent operations in \(\mathrm{Pol}\rho\) are projections. I. Rosenberg [Rocky Mt. J. Math. 3, 631–639 (1973; Zbl 0274.08001)] characterized all strongly rigid relations on a set with two elements and found a strongly rigid binary relation on every domain \(U\) of at least 3 elements. B. Larose and C. Tardif [Mult.-Valued Log. 7, No. 5–6, 339–361 (2001; Zbl 1009.05121)] studied the projective and strongly rigid graphs and constructed large families of strongly rigid graphs. T. Łuczak and J. Nešetřil [J. Graph Theory 47, No. 2, 81–86 (2004; Zbl 1055.05131)] settled in the affirmative a conjecture of Larose and Tardif that most graphs on a large set are projective, and characterized all homogeneous graphs that are projective. T. Łuczak and J. Nešetřil [SIAM J. Comput. 36, No. 3, 835–843 (2006; Zbl 1120.68059)] confirmed a conjecture of Rosenberg that most relations on a big set are strongly rigid. In this paper, we characterize all strongly rigid relations on a set with at least three elements to answer an open question by Rosenberg [loc. cit.] and we classify the binary relations on the 4-element domain by rigidity and demonstrate that there are merely 40 pairwise nonisomorphic rigid binary relations on the same domain (among them 25 are pairwise nonisomorphic strongly rigid).

MSC:

08A02 Relational systems, laws of composition
08A40 Operations and polynomials in algebraic structures, primal algebras
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Post, E.L.: The two-valued iterative system of mathematical logic, Annals of Mathematical Studies 5, pp 1-122. Princeton University Press (1941) · Zbl 1088.08002
[2] Swierczkowski, S.: Algebras which are independently generated by every n elements. Fund. Math. 49, 93-104 (1960) · Zbl 0115.01201
[3] Geiger, D.: Closed systems of functions and predicates. Pacific J. Math. 27, 95-100 · Zbl 0186.02502
[4] Bodnarčuk, V.G., Kalužhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras I-II, Kibernetika, 3 (1969), pp. 1-10 and 5 (1969), pp. 1-9 (in Russian); Cybernetics, (1969), pp. 243-252, 531-539 (English version), 1969
[5] Rosenberg, I.G.: Strongly rigid relations. Rocky Mt. J. Math. 3, 631-639 (1973) · Zbl 0274.08001 · doi:10.1216/RMJ-1973-3-4-631
[6] Schaefer, T.J.: The complexity of the satisfiability problems. Proc. 10th ACM Symp. Theory Comput. (STOC) 15, 216-226 (1978) · Zbl 1282.68143
[7] Csákány, B.: All minimal clones on the three element set. Acta Cybernet. 6, 227-238 (1983) · Zbl 0537.08002
[8] Rosenberg, I.G.: Minimal clones I: the five types, Lectures in universal algebra (Szeged, 1983). Colloquia Mathematical Society Janos Bolyai, Janos Bolyai, 43, North-Holland, Amsterdam, 1986, pp. 405-427 · Zbl 0840.08004
[9] Szendrei, Á.: Clones in Universal Algebra. Presses de l’Université de Montréal, Montreal (1986) · Zbl 0603.08004
[10] Bang-Jensen, J., Hell, P.: The effect of two cycles on the complexity of colourings by directed graphs. Discret. Appl. Math. 26(1), 1-23 (1990) · Zbl 0697.05029 · doi:10.1016/0166-218X(90)90017-7
[11] Szczepara, B.: Minimal Clones Generated by Groupoids. Ph.D. Thesis, Université de Montréal, Montréal (1995) · Zbl 1009.05121
[12] Fearnley, A.: A strongly rigid binary relation. Acta Sci. Math. (Szeged) 61, 35-41 (1995) · Zbl 0840.08004
[13] Berman, J., Burris, S.: A computer study of 3-element groupoids. In: Logic and Algebra (Pontignano, 1994), Lecture Notes in Pure and Applied Mathematics, 180, pp 379-429, Dekker (1996) · Zbl 0858.08001
[14] Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput. 28(1), 57-104 (1998) · Zbl 0914.68075 · doi:10.1137/S0097539794266766
[15] Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theor. Comput. Sci. 200, 185-204 (1998) · Zbl 0915.68074 · doi:10.1016/S0304-3975(97)00230-2
[16] Bulatov, A., Jeavons, P., Krokhin, A.: Constraint satisfaction problems and finite algebras. In: Proceedings of 27th International Colloquim on Automata, Languages and Programming (ICALP00), vol. 1853, pp 272-282. Lecture Notes in Computer Science, Geneva, Switzerland (2000) · Zbl 0973.68181
[17] Larose, B., Tardif, C.: Strongly rigid graphs and projectivity. Mult.-Valued Log. 7(5-6), 339-362 (2001) · Zbl 1009.05121
[18] Bulatov, A., Jeavons, P., Krokhin, A.: The complexity of maximal constraint languages. In: Proceedings of the 33rd Annual ACM Simposium on Theory of Computing, pp 667-674. ACM Press, Crete, Greece (2001) · Zbl 1323.68294
[19] Łuczak, T., Nešetřil, J.: A note on projective graphs. J. Graph Theory 47, 81-86 (2004) · Zbl 1055.05131 · doi:10.1002/jgt.20017
[20] Csákány, B.: Minimal clones a minicourse. Algebra Univ. 54, 73-89 (2005) · Zbl 1088.08002 · doi:10.1007/s00012-005-1924-2
[21] Larose, B.: Taylor operations on finite reflexive structures. Int. J. Math. Comput. Sci. 1(1), 1-26 (2006) · Zbl 1100.08003
[22] Łuczak, T., Nešetřil, J.: A probabilistic approach to the dichotomy problem. SIAM J. Comput. 36(3), 835-843 (2006) · Zbl 1120.68059 · doi:10.1137/S0097539703435492
[23] Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci. 410(18), 1629-1647 (2009) · Zbl 1172.68024 · doi:10.1016/j.tcs.2008.12.048
[24] Barto, L., Kozik, M., 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), 1782-1802 (2009) · Zbl 1191.68460 · doi:10.1137/070708093
[25] Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp 595-603 (2009) · Zbl 1292.68088
[26] Barto, L., Stanovský, D.: Polymorphisms of small digraphs. Novi. Sad J. Math. 2(40), 95-109 (2010) · Zbl 1289.05446
[27] Machida, H., Rosenberg, I.G. Centralizing Monoids on a Three-Element Set: 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, pp 274-280 · Zbl 1236.08009
[28] Kazda, A.: Complexity of the homomorphism extension problem in the random case. Chic. J. Theor. Comput. Sci. 2013(9) (2013) · Zbl 1286.68198
[29] Jovanović, J.: On optimal strong Mal’cev conditions for congruence meet-semidistributivity in a locally finite variety. Novi Sad J. Math. 44(2), 207-224 (2014) · Zbl 1458.08004
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.