On universal positive graphs. (English. Russian original) Zbl 1529.03223
Sib. Math. J. 64, No. 1, 83-93 (2023); translation from Sib. Mat. Zh. 64, No. 1, 98-112 (2023).
Summary: We study the existence of the universal computable numberings and the universal graphs for various classes of positive graphs. It is known that each \(\forall \)-axiomatizable class of graphs \(K\) can be characterized as follows: A graph \(G\) belongs to \(K\) if and only if for a given family of finite graphs \(\mathbf{F}\) no graph in \(\mathbf{F}\) is isomorphically embeddable into \(G \). If all graphs in \(\mathbf{F}\) are weakly connected; then, under additional effectiveness conditions, the corresponding class \(K\) has some universal computable numbering and universal positive graph. The effectiveness conditions hold for forests, bipartite graphs, planar graphs, and \(n \)-colorable graphs (for a fixed number \(n )\). If \(\mathbf{F}\) is a finite family of the graphs with weakly connected complement then the corresponding class \(K\) contains a universal positive graph (in general, a universal computable numbering for \(K\) may fail to exist).
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 03D30 | Other degrees and reducibilities in computability and recursion theory |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
computable reducibility; computable numbering; computably enumerable relation; positive graphReferences:
| [1] | Ershov Yu. L., Positive equivalences, Algebra Logic, 10, 6, 378-394 (1971) · Zbl 0276.02024 · doi:10.1007/BF02218645 |
| [2] | Ershov Yu. L., The Theory of Enumerations (1977), Moscow: Nauka, Moscow |
| [3] | Bernardi, C.; Sorbi, A., Classifying positive equivalence relations, J. Symb. Log., 48, 3, 529-538 (1983) · Zbl 0528.03030 · doi:10.2307/2273443 |
| [4] | Gao, S.; Gerdes, P., Computably enumerable equivalence relations, Stud. Log., 67, 1, 27-59 (2001) · Zbl 0981.03046 · doi:10.1023/A:1010521410739 |
| [5] | Andrews, U.; Lempp, S.; Miller, JS; Ng, KM; San Mauro, L.; Sorbi, A., Universal computably enumerable equivalence relations, J. Symb. Log., 79, 1, 60-88 (2014) · Zbl 1338.03076 · doi:10.1017/jsl.2013.8 |
| [6] | Badaev, S.; Sorbi, A., Weakly precomplete computably enumerable equivalence relations, Math. Log. Q., 62, 1, 111-127 (2016) · Zbl 1361.03043 · doi:10.1002/malq.201500057 |
| [7] | Bazhenov, N.; Kalmurzaev, B., On dark computably enumerable equivalence relations, Sib. Math. J., 59, 1, 22-30 (2018) · Zbl 1406.03057 · doi:10.1134/S0037446618010032 |
| [8] | Andrews, U.; Sorbi, A., Joins and meets in the structure of ceers, Computability, 8, 3, 193-241 (2019) · Zbl 1454.03048 · doi:10.3233/COM-180098 |
| [9] | Andrews, U.; Badaev, S., On isomorphism classes of computably enumerable equivalence relations, J. Symb. Log., 85, 1, 61-86 (2020) · Zbl 1452.03092 · doi:10.1017/jsl.2019.39 |
| [10] | Andrews, U.; Schweber, N.; Sorbi, A., The theory of ceers computes true arithmetic, Ann. Pure Appl. Logic, 171, 8, 102811 (2020) · Zbl 1442.03021 · doi:10.1016/j.apal.2020.102811 |
| [11] | Andrews U., Badaev S.A., and Sorbi A., “A survey on universal computably enumerable equivalence relations,” in: Computability and Complexity, Springer, Cham (2017), 418-451 (Lect. Notes Comput. Sci.; vol. 10010). · Zbl 1485.03146 |
| [12] | Kabylzhanova, D., Positive preorders, Algebra Logic, 57, 3, 182-185 (2018) · Zbl 1485.03113 · doi:10.1007/s10469-018-9491-8 |
| [13] | Badaev, S.; Kalmurzayev, B.; Kabylzhanova, D.; Abeshev K. Sh., Universal positive preorders, News of the National Academy of Sciences of the Republic of Kazakhstan: Physico-Mathematical Series, 322, 6, 49-53 (2018) |
| [14] | Badaev, S.; Bazhenov, N.; Kalmurzaev, B., The structure of computably enumerable preorder relations, Algebra Logic, 59, 3, 201-215 (2020) · Zbl 1462.03018 · doi:10.1007/s10469-020-09592-x |
| [15] | Badaev, S.; Kalmurzayev, B.; Mukash, N.; Khamitova, A., Special classes of positive preorders, Sib. Electr. Math. Reports, 18, 2, 1657-1666 (2021) · Zbl 1496.03167 |
| [16] | Soare, R., Turing Computability, Theory and Applications (2016), Berlin: Springer, Berlin · Zbl 1350.03001 |
| [17] | Tarski, A., Contributions to the theory of models I, II, Indag. Math., 16, 572-588 (1954) · Zbl 0058.24702 · doi:10.1016/S1385-7258(54)50074-0 |
| [18] | Maltsev, A., Universally axiomatizable subclasses of locally finite classes of models, Sib. Math. J., 8, 5, 764-770 (1967) · Zbl 0157.02703 · doi:10.1007/BF01040652 |
| [19] | Caicedo, X., Finitely axiomatizable quasivarieties of graphs, Algebra Universalis, 34, 2, 314-321 (1995) · Zbl 0837.08007 · doi:10.1007/BF01204787 |
| [20] | Asratian, A.; Denley T. M.J.; Häggkvist, R., Bipartite Graphs and Their Applications (1998), Cambridge: Cambridge University, Cambridge · Zbl 0914.05049 · doi:10.1017/CBO9780511984068 |
| [21] | Kuratowski, C., Sur le problème des courbes gauches en topologie, Fund. Math., 15, 1, 271-283 (1930) · JFM 56.1141.03 · doi:10.4064/fm-15-1-271-283 |
| [22] | Hopcroft, J.; Tarjan, R., Efficient planarity testing, J. Assoc. Comput. Mach., 21, 4, 549-568 (1974) · Zbl 0307.68025 · doi:10.1145/321850.321852 |
| [23] | Wagner, K., Fastplättbare Graphen, J. Comb. Theory, 3, 4, 326-365 (1967) · Zbl 0153.54101 · doi:10.1016/S0021-9800(67)80103-0 |
| [24] | Thomassen, C., Straight line representations of infinite planar graphs, J. Lond. Math. Soc., II. Ser., 16, 411-423 (1977) · Zbl 0373.05032 · doi:10.1112/jlms/s2-16.3.411 |
| [25] | De Bruijn, N.; Erdös, P., A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math., 13, 369-373 (1951) · Zbl 0044.38203 |
| [26] | Schmerl, J., Graph coloring and reverse mathematics, Math. Log. Q., 46, 4, 543-548 (2000) · Zbl 0963.03079 · doi:10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E |
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.
