kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2022-19-1-44-49kaz29-452Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ И ТЕХНИЧЕСКИЕ НАУКИPHYSICAL, MATHEMATICAL AND TECHNICAL SCIENCESАППРОКСИМАЦИИ РЕГУЛЯРНЫХ ГРАФОВAPPROXIMATIONS OF REGULAR GRAPHShttps://orcid.org/0000-0002-5088-0208МархабатовНурлан ДарханулыMarkhabatovNurlan Darkhanuly

Аспирант, ассистент кафедры алгебры и математической логики

Postgraduate Student, assistant, Chair of Algebra and Mathematical Logic

nur_24.08.93@mail.ruhttps://orcid.org/0000-0002-3268-9389СудоплатовСергей ВладимировичSudoplatovSergey Vladimirovich

Доктор физико-математических наук, ведущий научный сотрудник Математического институтаим. С.Л. Соболева; заведующий кафедрой алгебры и математической логики, Новосибирскийгосударственный технический университет,

Doctor of Physical and Mathematical Sciences, Leading Researcher, Sobolev Institute of Mathematics;Head of Algebra and Mathematical Logic Department, Novosibirsk State Technical University

sudoplat@math.nsc.ruНовосибирский государственный технический университетРоссияNovosibirsk State Technical UniversityRussian FederationМатематический институт им. С.Л. Соболева, Новосибирский государственный технический университетРоссияSobolev Institute of Mathematics, Novosibirsk State Technical UniversityRussian Federation2022310320221914449Copyright © Мархабатов Н.Д., Судоплатов С.В., 20222022Мархабатов Н.Д., Судоплатов С.В.Markhabatov N.D., Sudoplatov S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/452

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

The paper [11] raised the question of describing the cardinality and types of approximations fornatural families of theories. In the present paper, a partial answer to this question is given, and the studyof approximation and topological properties of natural classes of theories is also continued. We consider acycle graph consisting of one cycle or, in other words, a certain number of vertices (at least 3 if the graphis simple) connected into a closed chain. It is shown that an infinite cycle graph is approximated by finitecycle graphs. Approximations of regular graphs by finite regular graphs are considered. On the other hand,approximations of acyclic regular graphs by finite regular graphs are considered. It is proved that any infiniteregular graph is pseudofinite. And also, for any k, any k-regular graph is homogeneous and pseudofinite.Examples of pseudofinite 3-regular and 4-regular graphs are given.

регулярный графаппроксимация теориипсевдоконечная теорияregular graphapproximation of a theorypseudofinite theoryReferencesAx 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 .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 .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 .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 .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.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.Diestel R. Graph theory, New York: Springer, Heidelberg, 2005, 422 p.Diestel R. Graph theory, New York: Springer, Heidelberg, 2005, 422 p.Ershov Ju. L. Fields with a solvable theory. (Russian) Dokl. Akad. Nauk SSSR 174 (1967), pp.19–20.Ershov Ju. L. Fields with a solvable theory. (Russian) Dokl. Akad. Nauk SSSR 174 (1967), pp.19–20.Gardiner A. Homogeneous graphs, Combinatorial Theory (B), 20 (1976), pp. 94–102.Gardiner A. Homogeneous graphs, Combinatorial Theory (B), 20 (1976), pp. 94–102.Harary F. Graph Theory. Addison-Wesley, 1969, 274 p.Harary F. Graph Theory. Addison-Wesley, 1969, 274 p.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 .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 .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 .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 .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.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.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 .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 .Sudoplatov S.V., Ovchinnikova E.V. (2021) Diskretnaya matematika [Discrete mathematics]. – Moscow : Urait. – 280 p. (in Russian).Sudoplatov S.V., Ovchinnikova E.V. (2021) Diskretnaya matematika [Discrete mathematics]. – Moscow : Urait. – 280 p. (in Russian).

The authors declare that there are no conflicts of interest present.