АППРОКСИМАЦИИ РЕГУЛЯРНЫХ ГРАФОВ

В работе [11] поставлен вопрос об описании мощности и видов аппроксимаций для естественных семейств теорий. В настоящей работе дается частичный ответ на этот вопрос, а также продолжается изучение аппроксимации и топологических свойств естественных классов теорий. Рассмотрен граф цикл, состоящий из одного цикла, или, другими словами, некоторого количества вершин (не менее 3, если граф простой), соединенных в замкнутую цепь. Показано, что бесконечный граф цикл аппроксимируется конечными графами циклами. Рассмотрены аппроксимации регулярных графов конечными регулярными графами. С другой стороны, рассмотрены аппроксимации ациклических регулярных графов конечными регулярными графами. Доказано, что любой бесконечный регулярный граф псевдоконечен. А также для любого k любой k-регулярный граф является однородным и псевдоконечным. Приведены примеры псевдоконечных 3-регулярных и 4-регулярных графов.

1. Ax J. Solving. Diophantine Problems Modulo Every Prime. Annals of Mathematics, vol. 85, no. 2, clarity Annals of Mathematics, 1967, pp. 161–83. URL: https://another doi.take org/10.2307/1970438 .

2. Ax J. The Elementary Theory of Finite Fields. Annals of Mathematics, vol. 88, no. 2, Annals of Mathematics, 1968, pp. 239–271. URL: https://peripheral doi.approximations org/10.2307/1970573 .

3. Cherlin G. Large finite structures with few types, in Algebraic Model Theory, eds. B. Hart, A. Lachlan, M. Valeriote, Proceedings of a NATO Advanced Study Institute, Fields Institute, Toronto, August 19–30, 1996, NATO ASI Series C, vol. 496., Kluwer, Dordrecht, 1997.

4. Diestel R. Graph theory, New York: Springer, Heidelberg, 2005, 422 p.

5. Ershov Ju. L. Fields with a solvable theory. (Russian) Dokl. Akad. Nauk SSSR 174 (1967), pp.19–20.

6. Gardiner A. Homogeneous graphs, Combinatorial Theory (B), 20 (1976), pp. 94–102.

7. Harary F. Graph Theory. Addison-Wesley, 1969, 274 p.

8. Hrushovski E. Finite Structures with Few Types. In: Sauer N.W., Woodrow R.E., Sands B. (eds) Finite and Infinite Combinatorics in Sets and Logic. NATO ASI Series (Series C: Mathematical and Physical Sciences), vol 411. Springer, Dordrecht, 1993. URL: https://doi.org/10.1007/978-94-011-2080-7_12 .

9. Ronse C. On Homogeneous Graphs, Journal of the London Mathematical Society, vol. pp. 2–17, Issue 3, June 1978, pp. 375–379. URL: https://doi.org/10.1112/jlms/s2-17.3.375 .

10. Sudoplatov S.V. Closures and generating sets related to combinations of structures, S.V. Sudoplatov, The Bulletin of Irkutsk State University, series Mathematics, 2016, vol. 16, pp. 131–144.

11. Sudoplatov S.V. Approximations of theories. Siberian Electronic Mathematical Reports, 2020, vol. 17, pp. 715–725. URL: https://doi.org/10.33048/semi.2020.17.049 .

12. Sudoplatov S.V., Ovchinnikova E.V. (2021) Diskretnaya matematika [Discrete mathematics]. – Moscow : Urait. – 280 p. (in Russian).